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 (4 e 10 ottobre 2018)

• Lucidi: introduzione a Linux
• Lucidi: introduzione al linguaggio C (compilatore, tipi built-in, input/output)
• Scheda: primi programmi da scrivere a casa
• Scheda: esercizi da svolgere in labratorio

Seconda settimana (17 ottobre 2018)

• Lucidi: dati aggregati
• Scheda: esercizi introduttivi su array, stringhe e strutture
• Scheda: altri esercizi

Terza settimana (18 e 24 ottobre 2018)

• Lucidi: funzioni
• Scheda: esercizi introduttivi sulle funzioni, da svolgere a casa
• Scheda: esercizi sulle funzioni ricorsive; per svolgere gli esercizi servono i file libpsgraph.c e libpsgraph.h come indicato nella scheda.

Quarta settimana (25 e 31 ottobre 2018)

• Lucidi: Introduzione ai puntatori
• Scheda: alcuni esercizi introduttivi sui puntatori, da svolgere a casa
• 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).

Quinta settimana (5 e 7 novembre 2018)

• Lucidi: puntatori e array
• Scheda: alcuni esercizi introduttivi sui puntatori, da svolgere a casa
• Lucidi: array frastagliati e argomenti da linea di comando
• Scheda: esercizi su array frastagliaati e argomenti da linea di comando, da svolgere in laboratorio

Sesta settimana (8 e 13 novembre 2018)

• Lucidi: allocazione dinamica della memoria.
• Scheda: esercizi su allocazione dinamica della memoria.
• Registro di prenotazione: un esercizio un po' più articolato del solito, da svolgere in laboratorio

Settima settimana (15 e 21 novembre 2018)

• Lucidi: implementazione in C di liste concatenate
• Scheda: liste per gestire insiemi dinamici di elementi.
• Appunti sulla funzione scanf

Ottava settimana (22 e 28 novembre 2017)

• Lucidi su alberi binari di ricerca
• 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).
• 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).

Nona settimana (29 novembre e 5 dicembre 2018)

• Lucidi: code di priorità e heap.
• Scheda: esercizi su heap e code di priorità.
• Scheduling
  • Scheda su attività "Festival del cinema"
  • Software di supporto
  • Traccia per l'implementazione della strategia greedy per il problema dello scheduling
  • definizione di problema di ottimizzazione e strategia greedy
  • Scheda su "festival del cinema" compilata

• Estratti di alcuni progetti proposti in appelli passati e analizzati a lezione.
• Lucidi: preparati dal collega Prof. Stefano Aguzzoli, contengono una presentazione sull'implementazione dei grafi come liste di adiacenza e le visite in prfondità 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à.

Dodicesima settimana (8 e 9 gennaio 2019)

• Scheda su implementazione di un dizionario con tabella di hash.
• File di esempio: input_promessiSposi e output_promessiSposi.
• Svolgimento

16 gennaio 2019