| | | |  corso | | | | |
Algoritmica
| Codice: | AA006 | Crediti: | 9 | Semestre: | 1 | Sigla: | ALG | |
| |
| Settore disciplinare: | INF/01 - Informatica |
Docente
Fabrizio Luccio
Tel. 0502212720Prerequisiti
- Conoscenza di un linguaggio di programmazione (Pascal, C, C++ o Java).
- Dimestichezza con l'uso dei puntatori e della ricorsione.
- Nozioni matematiche: proprietà e limiti di funzioni, sommatorie, numeri di Fibonacci, permutazioni, coefficienti binomiali, aritmetica modulare, numeri primi, metodi di dimostrazione (per induzione, per assurdo, per casi).
Obiettivi di apprendimento
Definire formalmente la nozione di algoritmo e di modello di calcolo. Caratterizzare i dati da elaborare, organizzandoli e strutturandoli nel modo più opportuno al fine di agevolarne l'uso da parte degli algoritmi. Progettare algoritmi corretti (che risolvono cioè sempre e solo il problema a cui si è interessati) ed efficienti (cioè che lo risolvono il più velocemente possibile o usano il minor spazio di memoria possibile), attraverso l'esame di diversi paradigmi. Studiare le limitazioni inerenti dei problemi da risolvere, in particolare di quelli la cui soluzione richiede l'esame di tutte le possibilità.
Descrizione
Introduzione ai modelli di calcolo, all'analisi e alla complessità degli algoritmi. Algoritmi ricorsivi e relazioni di ricorrenza. Algoritmi di enumerazione. Strutture di dati elementari e avanzate. Problemi su sequenze, matrici, alberi e grafi. Problemi P, NP, RP, e NP-completi.
Programma
- Problemi computazionali
- Indecidibilità
- Trattabilità
- Complessità computazionale: limiti superiori e inferiori.
- Sequenze: array
- Ricerca di una chiave
- Problemi risolti ricorsivamente ("divide et impera")
- Problemi risolti per programmazione dinamica
- Sequenze: liste
- Alberi
- Alberi binari
- Visite
- Grafi
- Rappresentazione
- Algoritmi di ricerca e cammini in un grafo
- Pile e code
- Rappresentazione
- Applicazioni a diversi problemi
- Code con priorità: Heap e ordinamenti
- Dizionari
- Alberi AVL e B-alberi
- Tabelle hash
- Trie
- NP-completezza
- Le classi P, NP, NPC
- Riduzioni polinomiali
- Algoritmi di approssimazione
Bibliografia
- Dispense del docente depositate presso la sede di La Spezia.
- Testi consigliati per approfondimenti:
- C.Demetrescu, I.Finocchi, G.F.Italiano, Algoritmi e strutture dati, McGraw Hill 2004.
- P.Crescenzi, G.Gambosi, R.Grossi, Strutture di dati e algoritmi, Pearson-Addison Wesley 2006.
Modalità di esame
- L'esame consiste in una prova scritta e in una prova orale.
- Durante la prova scritta o le verifiche intermedie è vietato consultare libri o appunti.
- Il superamento di entrambe le verifiche intermedie consente l'esonero dalla prova scritta per la sola sessione invernale.
