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 (3 e 10 ottobre 2019)
- Introduzione a Linux: Lucidi
- Introduzione al linguaggio C (compilatore, tipi built-in, input/output): Lucidi
- Primi programmi in C: scheda da svolgere a casa e codice sorgente.
- Esercizi da svolgere in laboratorio: scheda e codice sorgente.
Seconda settimana (11 e 17 ottobre 2019)
- Dati aggregati: Lucidi
- Esercizi introduttivi su array, stringhe e strutture: scheda e codice sorgente
- Altri esercizi (incluso alcuni esercizi tratti da temi d'esame di appelli passati: scheda
Terza settimana (18 e 24 ottobre 2019)
- Funzioni: Lucidi
- Esercizi introduttivi sulle funzioni, da svolgere a casa: scheda e codice sorgente
- Esercizi sulle funzioni ricorsive: scheda. Per svolgere gli esercizi servono i file libpsgraph.c e libpsgraph.h come indicato nella scheda.
Quarta settimana (25 e 31 ottobre 2019 )
- Appunti sulla funzione scanf
- Introduzione ai puntatori: Lucidi
- Alcuni esercizi introduttivi sui puntatori, da svolgere a casa: scheda e codice sorgente
- Altri esercizi, anche sugli array frastagliati (incluso un esercizio tratto da un tema d'esame): scheda e codice sorgente
Quinta settimana (7 novembre 2019)
- 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).
Sesta settimana (8 e 14 novembre 2019)
- Allocazione dinamica della memoria: lucidi
- Esercizi introduttivi da svolgere a casa: scheda e codice sorgente.
- Registro di prenotazione: un esercizio un po' più articolato del solito, da svolgere in laboratorio
- Cristalli: un altro esercizio su allocazione dinamica e ricorsione
Settima settimana (15 e 21 novembre 2019)
- Implementazione in C di liste concatenate: lucidi
- Paradigma client-interfaccia-implementazione: lucidi
- Esercizi sulle liste concatenate da svolgere a casa: scheda e codice sorgente
- Un esercizio sulle liste tratto da un tema d'esame: scheda e codice sorgente
- Esercizio da svolgere in laboratorio su tipi di dati astratti (la pila): scheda e codice sorgente
Ottava settimana (22 e 28 novembre 2019)
- Lucidi su alberi binari di ricerca
- Alcuni quesiti giocosi tratti dal Kangourou dell'Informatica e dal Bebras dell'Informatica. I quesiti hanno difficoltà molto variabili 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).
- Esercizi sugli alberi
- Porzioni di codice relative all'implementazione di alberi binari di ricerca e relative note illustrate (NB: nelle illustrazioni, ci sono alcune differenze nei nomi dei parametri e delle variabili).
Nona settimana (5 dicembre 2019)
- Scheda su attività "Festival del cinema"
- Software di supporto
- definizione di problema di ottimizzazione e strategia greedy
- Scheda su "festival del cinema" compilata
Decima settimana (6 e 12 dicembre 2019)
- Estratti di alcuni progetti proposti in appelli passati e analizzati a lezione.
- Lucidi: preparati dal collega Prof. Stefano Aguzzoli, contengono una presentazione sull'implementazione di grafi di interi come array di liste di adiacenza e le visite in profondità e in ampiezza.
- Scheda di esercizi sull'implementazione dei grafi.
- Scheda di esercizi sull'uso dei grafi come modelli per analizzare e progettare soluzioni algoritmiche.
- Altri estratti di progetti da analizzare per esercizio.
Undicesima settimana (13 e 19 dicembre 2018)
- Lucidi: programmazione dinamica: scheduling di intervalli pesati e zaino
- 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
- I più coraggiosi possono anche cimentarsi nell'esercizio Uffici postali, proposto alle Olimpiadi dell'Informatica nel 2000!
Dodicesima settimana (20 dicembre 2019)
- Lucidi: code di priorità e heap.
- Scheda: esercizi su heap e code di priorità.
- Traccia per l'implementazione della strategia greedy per il problema dello scheduling
8 e 9 gennaio 2020
- Scheda su implementazione di un dizionario con tabella di hash.
- File di esempio: input_promessiSposi e output_promessiSposi.
- Potete provare a svolgere l'esercizio anche usando il linguaggio Go, usando opportunamente mappe e slice!