OBIETTIVI FORMATIVI

Ampliare le conoscenze e le capacità inerenti la programmazione in piccolo mediante linguaggi imperativi, fornendo le basi per progettare algoritmi corretti ed efficienti,  e sviluppare strutture dati che permettano un’organizzazione efficace ed efficiente delle informazioni.

OBIETTIVI FORMATIVI (DETTAGLIO) E RISULTATI DI APPRENDIMENTO

Al termine dell'insegnamento, lo studente sarà in grado di:

- calcolare la complessità di algoritmi notevoli (ordinamento, aggiunta, ricerca e modifica di elementi in una struttura dati) in modo da individuare l'algoritmo più efficiente

- progettare l'interfaccia di un tipo di dato

- implementare il tipo di dato con strutture dati diverse che comprendono strutture indicizzate e collegate

- apprezzare la differenza nella efficienza delle funzioni previste dal tipo di dato al variare della struttura dati utilizzata

MODALITA' DIDATTICHE

Tradizionale: Corso organizzato in lezioni frontali ed esercitazioni pratiche che si iniziano in laboratorio e si completano come compito per casa.

PROGRAMMA/CONTENUTO

Modelli di calcolo e metodologie di analisi degli algoritmi: criteri di costo, notazione asintotica, metodi di analisi, analisi di complessità  degli algoritmi ricorsivi. Esempi di sviluppo ed analisi di algoritmi.
Algoritmi di ordinamento: insertion sort, selection sort, bubble sort, mergesort, quicksort (con analisi di complessità)
Strutture dati elementari: array e liste, tipo di dato pila e coda, tipo di dato dizionario ed implementazione mediante liste, alberi, alberi binari, rappresentazioni indicizzate e collegate per alberi binari e non, alberi quasi completi, visite di alberi in profondità ed in ampiezza.
Alberi  di ricerca: Alberi binari di ricerca, alberi di ricerca come implementazione del tipo di dato dizionario, cenni ad alberi bilanciati.
Code con priorità: tipo di dato, implementazione mediante liste, heap, implementazione di code con priorità mediante heap binari.
Tabelle di hash: implementazione con liste di collisione e con indirizzamento aperto.
Grafi: definizioni, strutture dati, primitive per l'interrogazione e l'aggiornamento di grafi visite di grafi in profondità ed in ampiezza, esempi di applicazione degli algoritmi di visita di un grafo.
Laboratorio: esercitazioni in C++ relative agli argomenti del corso

TESTI/BIBLIOGRAFIA

Tutti gli argomenti previsti dal programma vengono trattati approfonditamente a lezione. Per la comprensione degli argomenti e la preparazione dell'esame è quindi indispensabile disporre delle slide preparate dai docenti e rese disponibili con ampio anticipo, e degli appunti presi durante le lezioni in aula.

Il codice C++ reso disponibile dai docenti è parte integrante del materiale didattico a disposizione degli studenti.