Algoritmi e Strutture Dati

Anno Accademico 2019-2020 (Cl. B)

Lucidi

I lucidi di ogni lezione saranno resi disponibili con congruo anticipo rispetto all'inizio della lezione stessa. Si raccomanda di controllare i lucidi anche dopo la lezione per eventuali modifiche richieste a lezione: correzioni, approfondimenti, ecc. I lucidi degli anni precedenti NON sono un riferimento. I lucidi di riferimento per l'esame saranno quelli esposti al termine del corso (giugno 2019).

- Introduzione
modalita' d'esame, generalita' del corso (lucidi ver. 2-up,)
- Fondamenti
ordini di grandezza, sommatorie, ricorrenze. (lucidi ver. 2-up, 1-up)
- Analisi asintotica
Complessita' computazionale, algoritmi ricorsivi (lucidi ver. 2-up, 1-up)
- Ordinamento, grafi e strutture dati astratte
Grafi, insertion sort, abstract data structures (lucidi ver. 2-up, 1-up)
- Ordinamento divide et impera, selezione
Divide et impera, introduzione ai grafi, mergesort, quicksort, mediano e selezione (lucidi ver. 2-up, 1-up)
- Heap
Heap, heapsort, code a priorita' (lucidi ver. 2-up, 1-up)
- Strutture dati elementari
pile, code, liste, alberi (lucidi ver. 2-up, 1-up)
- Hash
funzioni e tabelle hash (lucidi ver. 2-up, 1-up)
- Alberi binari
Mantenimento, ricerca, ordinamento (lucidi ver. 2-up, 1-up)
- Algoritmi elementari su grafi
visite in ampiezza e profondita', componenti connesse (lucidi ver. 2-up, 1-up)
- Ordinamento topologico
DAG, ordinamento topologico di grafi, precedenze (lucidi ver. 2-up, 1-up)
-Insiemi disgiunti
Relazioni di equivalenza, partizioni, up-tree. (lucidi ver. 2-up, 1-up)
-Algoritmi greedy
Selezione attivita', TSP, knapsack. (lucidi ver. 2-up, 1-up)
-Programmazione dinamica
Sottovettore massimo, knapsack01, allineamento di stringhe. (lucidi ver. 2-up, 1-up)
-Alberi di copertura minimi
algoritmi di Kruskal e di Prim. (lucidi ver. 2-up, 1-up)
- Cammini minimi su grafo
cammini minimi con singola sorgente, algoritmi di Dijkstra e Bellman-Ford, cammini minimi in un DAG. (lucidi ver. 2-up, 1-up)
- Cammini minimi su grafo, estensioni e applicazioni
cammini minimi tra tutte le coppie, algoritmo Floyd-Warshall. (lucidi ver. 2-up, 1-up)
flusso massimo, algoritmo di Ford-Fulkerson ed estensione di Edmonds-Karp (generalita', applicazione). . (lucidi ver. 2-up, 1-up)
-Cenni di complessita' computazionale
Le classi P e NP, riduzioni. (lucidi ver. 2-up, 1-up)

Modalita' d'esame (A.A. 2018 / 2019)

1) Consegnare il progetto di laboratorio secondo le modalita' definite dal docente del modulo (prof. Calderoni). La consegna verra' effettuata dalla pagina IOL del corso.

  if (not progetto approvato) goto 1

2) Appello scritto. Tre esercizi, uno a scelta multipla, uno teorico e uno soluzione di problema. Il voto finale sara' quello dello scritto che appare su AlmaEsami, registrabile inviandomi una mail dall'indirizzo unibo che specifica nome, cognome, matricola, appello e voto.

3) (opzionale) prova orale aggiuntiva. Il voto pua' crescere o calare rispetto a quello proposto al termine della prova scritta.

Per registrare inviarmi una mail dall'indirizzo studio.unibo.it che specifichi:

Testi consigliati

Risultati prove:

Risultati prove scritte e progetto

Esami passati:

Prova scritto esame

Prova scritto esame

Prova scritto esame

Prova scritto esame

Prova scritto esame

Prova scritto esame

Prova scritto esame

Prova scritto esame

Prova scritto esame

Prova scritto esame

Per esercitarsi

Domande a scelta multipla.

Dimostrazioni Fatte durante il corso. ATTENZIONE! Il file puo' essere integrato fino a giugno.

Esercizi e prove d'esame Corso prof. Marzolla (et al.), considerate solo gli argomenti coperti anche nel nostro corso.
Raccolta di esercizi compilata e resa pubblica dal prof. Marzolla

Link