• 086065 - ALGORITMI E PRINCIPI DELL'INFORMATICA (MOD 2 - INFORMATICA 3)

Obiettivi

Il corso di Informatica 3 costituisce il secondo modulo del corso integrato Algoritmi e Principi dell'Informatica (API), alla cui scheda si rimanda per una sua presentazione di carattere generale. In circostanze particolari i due moduli sono fruibili separatamente, tuttavia nella grande maggioranza dei casi è previsto che gli studenti seguano integralmente il corso di API.
L'obiettivo principale di questo modulo del corso integrato è fornire allo studente la capacità di risolvere problemi combinando i due aspetti fondamentali della programmazione: le strutture di dati, che riflettono il modo con cui le informazioni possono essere organizzate, e gli algoritmi, che rappresentano il modo con cui l'informazione viene manipolata. Dopo una breve analisi teorica della complessità degli algoritmi verranno trattate le strutture dati fondamentali ed avanzate, quali liste, pile, code, alberi, grafi e loro varianti. Per quanto riguarda gli algoritmi verranno presentati i principali algoritmi di ordinamento, ricerca, indicizzazione e alcuni algoritmi legati ad applicazioni specifiche avanzate (per esempio legate alla grafica, all'elaborazione dei segnali, ecc.).

Programma dettagliato delle lezioni ed esercitazioni

1.1 Nozioni e notazioni fondamentali per l’analisi di complessità
1.2. I modelli di calcolo e le relazioni tra le loro complessità computazionali

1.2.1 Definizione di complessità spaziale e temporale per macchina di Turing deterministica

1.2.2 Astrazioni e notazione asintotica

1.2.3 Complessità di automi a stati finiti, a pila e macchina di Turing a nastro singolo

1.2.4. Accelerazione lineare

1.3 La macchina RAM

1.3.1. Valutazione di complessità con criterio del costo costante
1.3.2  Il criterio logaritmico

1.4 Il teorema di correlazione polinomiale
1.5 Gerarchie di complessità

1.6 Cenni all'NP-completezza

2. Strutture dati e algoritmi fondamentali

2.1 Algoritmi di ricerca e ordinamento
2.2 Strutture dati elementari (pile, code, liste): rappresentazione, algoritmi di ricerca e gestione

2.3Tabelle hash: funzioni di hash, indirizzamento aperto.

2.4 Alberi e loro gestione

2.4.1 Alberi binari

2.4.2 Algoritmi di visita e gestione

2.4.3Alberi rosso-neri

2.5 Grafi, loro rappresentazione e gestione (cenni)

Prerequisiti

Il corso richiede una buona conoscenza degli argomenti trattati negli insegnamenti di Fondamenti di informatica e di Informatica teorica, ossia il primo modulo del corso integrato. Le conoscenze di base sugli aspetti fondamentali dell'architettura dei calcolatori possono essere utili.

Verranno svolte 2 prove in itinere durante lo svolgimento del corso integrato. La prima di queste copre il programma del primo modulo e naturalmente la seconda copre gli argomenti del presente modulo.

Verranno poi svolti appelli regolari secondo le regole della scuola sia per i due moduli separati che per il coprso integrato.

Il testo oltre a coprire l'intero programma del primo modulo del corso integrato, tratta la parte Teoria della complessità del presente modulo.

Il testo copre la parte Strutture dati e algoritmi fondamentali del modulo. Esso è suggerito in alternativa, ma preferibile, al testo Di Bertossi e Montresor.

Il testo può surrogare il testo principale di Cormen et al.

Il testo è un eserciziario che tratta gli argomenti del programma del primo modulo del corso integrato e della parte Teoria della complessità del presente modulo.