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.
Slide su C
Nel corso delle prime settimane di lezione verra presentato il linguaggio e le sue caratteristiche fondamentali. Questa è la collezione di tutte le slide. Settimana per settimana verranno indicati i numeri delle slide utili. Se necessario il file potrà essere aggiorante (fate riferimento alla data di ultimo aggiornamento indicata nella seconda slide.Prima settimana (30 settembre e 1 ottobre 2020) - INTRODUZIONE AL LINGUAGGIO C
- Introduzione a Linux: Lucidi
- Lezione:
- Esercizi assegnati:
- primi programmi: scheda da svolgere a casa e codice sorgente.
- Esercizi da svolgere in laboratorio: scheda e codice sorgente.
- Svolgimento degli esercizi
- ricerca dicotomica: video con commenti sull'esercizio 7
- concetto di "spazio occupato": video con commenti sugli eserizi 4 e 7 della "scheda per casa"
Seconda settimana (7 e 8 ottobre 2020) - DATI AGGREGATI
- Lezione:
- Esercizi:
- esercizi introduttivi su array, stringhe e strutture: scheda e codice sorgente.
- Scheda per l'esercitazione
- Video - funzionamento della scanf - da guardare DOPO aver svolto l'esercizio 7 della scheda della prima settimana!!
- Svolgimento di esercizi
- assegnamenti e incrementi/decrementi: video con commenti sull'esercizio 5 (divisioni)
- uso di vettore per contare le occorrenze: video con commenti sugli esercizi introduttivi 3 (cifre) e 4 (ripetizioni) + es 1 (istogramma) e 2 (anagrammi) dell'esercitazione in lab
- riordina i bit: video con commenti sull'esercizio 8
Terza settimana (14 e 15 ottobre 2020) - FUNZIONI e RICORSIONE
- Lezione:
- Esercizi:
- scheda e relativo codice sorgente (include anche i file libpsgraph.c e libpsgraph.h).
- Svolgimento di esercizi
- torri di Hanoi: video con svolgimento e commenti sull'esercizio 3.2
Quarta settimana (21 e 22 ottobre 2020 ) - PUNTATORI
- Lezione:
- Esercizi:
- scheda e relativo codice sorgente
- Svolgimento di esercizi
- Es 1.5 e 2.4: video con svolgimento e commenti
Quinta settimana (28 e 29 ottobre 2020) - ALLOCAZIONE DINAMICA DELLA MEMORIA
- Lezione:
- Lucidi pag 87-107
- Video 1 - introduzione all'allocazioe dinamica della memoria
- Video 2 - il puntatore nullo
- Video 3 - le funzioni malloc e calloc
- Video 4 - riallocazione della memoria con la funzione realloc
- Video 5 - lettura di una riga con allocazione dinamica
- Video 6 - allocazione dinamica di una matrice
- Video 7 - errori tipici relativi all'allocazione dinamica
- Esercizi:
- Scheda di esercizi introduttivi e relativo 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
Sesta settimana (4 e 5 novembre 2020) - LISTE CONCATENATE + PARADIGMA CLIENT/INTERFACCIA/IMPLEMENTAZIONE
Liste concatenate
- Lezione:
- Esercizi:
- Esercizi introduttivi sulle liste concatenate: scheda e codice sorgente
- Un esercizio sulle liste tratto da un tema d'esame: scheda e codice sorgente
Client/interfaccia/implementazione e tipi di dati astratti
- Lezione: Lucidi e video
- Esercizio su tipi di dati astratti (la pila): scheda e file con interfaccia stack.h
Settima settimana (11 e 12 novembre 2020) - LISTE BIDIREZIONALI, CODE E PILE, algoritmi di ordinamento
- Lezione:
- Video 1 - liste bidirezionali (o doppiamente concatenate)
- Video 2 - implementazione di una coda con array circolare; le animazioni usate nel video sono tratte dal progetto OpenDSA.
- 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 (18 e 19 novembre 2020) - ALBERI
- Lezione:
- 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 (25 e 26 novembre 2020) - RIPASSO
Per questa settimana non sono proposti argomenti nuovi, quindi avete occasione di recuperare terreno se siete rimasti indietro con gli esercizi!
Sono disponibili dei nuovi video con lo svolgimento di esercizi assegnati nelle settimane passate. Per maggior ordine, i video nuovi sono elencati sia qui che in alto nella pagina, in corrispondenza della settimana in cui sono stati assegnati.
- torri di Hanoi: video con svolgimento e commenti per l'esercizio 3.2 della scheda L03 su funzioni e la ricorsione
- puntatori (es dalla scheda L04)
- video con svolgimento e commenti per gli esercizi 1.5 e 2.4
- uso dei puntatori per simulare il passaggio per riferimento: svolgimento degli esercizi 2.3 e 2.5 della scheda L04: video per es 2.3 e video per es 2.5 (i video vanno visti in sequenza, poiché il secondo fa riferimento al primo).
Oggi è la Giornata internazionale per l'eliminazione della violenza contro le donne
Decima settimana (2 e 3 dicembre 2020) - Code di priorità, heap, algoritmi greedy
Code di priorità e heap
- Lezione:
- Esercizi:
- Scheda di esercizi.
Algoritmi greedy
- Un programma ricco di eventi:
- Scheda e strumento per fare esperimenti
- Video 1 - riassunto del compito assegnato
- Video 2 - controesempi (quali criteri non sono adatti, e perché)
- Video 3 - dimostrazione (dimostrazione di correttezza nel caso del criterio adatto
- Video 4 - considerazioni sugli algoritmi greedy
Undicesima settimana (9 e 10 dicembre 2020) - Programmazione dinamica
- Lezione:
- 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
- I più coraggiosi possono anche cimentarsi nell'esercizio Uffici postali, proposto alle Olimpiadi dell'Informatica nel 2000!
Dodicesima settimana (16 e 17 dicembre 2020) - Ancora algoritmi greedy + grafi
Ancora su algoritmi greedy
Nella sezione dedicata alla decima settimana sono stati pubblicati nuovi video relativi all'esercitazione "Un programma ricco di esempi".
Grafi
- Lezione
- Video 1 - esempi di situazioni modellabili con grafi
- Video 2 - implementazione di grafi
- 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.
- Esercitazione