Laboratorio di Algoritmi e Strutture Dati - AA 2021/22
Corso di laurea in informatica


logo università milano

Materiale didattico

Il materiale didattico a supporto del laboratorio di algoritmi e strutture dati verrà messo a disposizione su questo sito. Indicativamente, il materiale sarà raggruppato per moduli settimanali.

Prima settimana (6 e 7 ottobre 2021) - INTRODUZIONE AL LINGUAGGIO C

Seconda settimana (13 e 14 ottobre 2021) - DATI AGGREGATI

Terza settimana (20 e 21 ottobre 2021) - FUNZIONI E RICORSIONE

Quarta settimana (27 e 28 ottobre 2021 ) - PUNTATORI

Quinta settimana (3 e 4 novembre 2021) - ALLOCAZIONE DINAMICA DELLA MEMORIA

Sesta settimana (10 e 11 novembre 2021) - LISTE CONCATENATE + PARADIGMA CLIENT/INTERFACCIA/IMPLEMENTAZIONE

Liste concatenate

Client/interfaccia/implementazione e tipi di dati astratti

Settima settimana (17 e 18 novembre 2021) - LISTE BIDIREZIONALI, CODE E PILE, algoritmi di ordinamento

  • Esercizi:
    • Scheda di esercizi sugli algoritmi di ordinamento per selezione (selectionsort) e per fusione (mergesort). Gli esercizi prevedono l'uso di funzioni ricorsive e array. Per un ripasso degli algoritmi potete fare riferimento a questa presentazione (usate la modalità a schermo intero per visualizzare le animazioni).
    • Esercizi di analisi sulle liste + implementazione di coda con array circolare: scheda e codice sorgente

Ottava settimana (24 e 25 novembre 2021) - ALBERI

  • Lezione: Lucidi su alberi binari e alberi binari di ricerca
  • Esercizi:
    • Scheda di esercizi. La scheda è composta da due parti: la prima parte propone di scrivere alcune funzioni per manipolare alberi binari; la seconda parte propone un esercizio di applicazione degli alberi binari di ricerca. Il codice per la manipolazione degli alberi binari di ricerca è fornito in una scheda a parte.
    • Scheda in cui sono presenta le funzioni fondamentali per gli alberi binari di ricerca, con relative note illustrate (NB: nelle illustrazioni, ci sono alcune differenze nei nomi dei parametri e delle variabili).
    • Alcuni quesiti giocosi tratti dal Kangourou dell'Informatica e dal Bebras dell'Informatica. I quesiti hanno difficoltà molto variabili (alcuni sono rivolti già ai bambini della scuola primaria) e sono raccolti qui perché fanno tutti riferimento in qualche senso alla struttura dati ad albero e possono offrire diversi spunti di riflessione. Nel contesto di questa esercitazione, non è interessante tanto risolvere i quesiti (ovvero trovare la risposta giusta) ma ragionare sui diversi contesti in cui gli alberi possono essere utilizzati per modellare situazioni concrete, su come problemi molto diversi possano essere formalizzati e affrontati mediante gli alberi, sulle proprietà dei vari tipi particolari di alberi (ad esempio: alberi di decisione, alberi binari di ricerca, alberi red-black, heap).

Nona settimana (1 e 2 dicembre 2021) - RAPPRESENTAZIONE E VISITE DI GRAFI

  • Lezione: confronto tra diverse rappresentazioni possibili per i grafi.

    NOTA: poichè buona parte della lezione è stata dedicata a rivedere gli esercizi assegnati sugli alberi, non sono riuscita (come avevo pianificato) a presentare per bene alcuni aspetti relativi all'implementazione dei grafi e soprattutto al loro uso per modellare situazioni reali. Riprenderemo il discorso in un'altra lezione (fra due settimane perché c'è il ponte); dunque, diversamente da quanto annunciato, la scheda di oggi riguarda solo l'implementazione di grafi (con matrice di adiancenza o con array di liste di adiacenza) e le visite di grafi.

  • Esercitazione
    • Scheda di esercizi sull'implementazione dei grafi.
    • Per dettagli sulla rappresentazione di grafi di interi come array di liste di adiacenza in C e le visite in profondità e in ampiezza, potete fare riferimento anche a questi Lucidi preparati dal collega Prof. Stefano Aguzzoli.

Decima settimana (9 e 10 dicembre 2021) - GRAFO COME MODELLO

  • Lezione: Lucidi sull'uso di grafi per modellare situazioni diverse
  • Esercitazione: Scheda di esercizi su modellazione con grafi.

Undicesima settimana (15 e 16 dicembre 2022) - PROGRAMMAZIONE DINAMICA

  • Lezione: Lucidi su programmazione dinamica con esempi di applicazione della tecnica
  • Esercizi:
    • Scheda: tutti gli esercizi sono risolubili con tecniche di programmazione dinamica; la parte difficile non è la scrittura del codice vero e proprio, ma l'analisi dei problemi, la loro riduzione a sottoproblemi, la costruzione di algoritmi efficienti; gli esercizi sono indipendenti tra loro, ma in ordine di difficoltià.
    • Segnalo infine questa dispensa sulla programmazione dinamica scritta da Sebastiano Vigna per le IOI, che ho usato ampiamente come fonte per le mie slide.
    • Jet points: un altro esercizio di programmazione dinamica tratto da un vecchio progetto d'esame

UN PROGRAMMA RICCO DI EVENTI

Un programma ricco di eventi: Scheda e strumento per fare esperimenti

Se avete svolto l'attività potete prendere visione dei video pubblicati nella scorsa edizione del corso:

Dodicesima settimana (12 e 13 gennaio 2022) - RIPASSo

Per questa ultima settimana vi propongo la traccia del tema d'esame assegnata nell'appello del 16 giugno 2021 (in presenza, in laboratorio).