Algoritmi E Strutture DATI 2014-15 PDF

Preview

Summary

Nome insegnamento: ALGORITMI, STRUTTURE DATI Articolazione in moduli: NO Settore Scientifico Disciplinare: ING-INF/05 Docente responsabile: FLESCA SERGIO Crediti formativi universitari: 6 Numero ore lezioni: 36 Numero ore riservate attività didattiche assistite: 57 Numero ore esercitazioni: 21 Numer...

Description

Nome insegnamento: ALGORITMI, STRUTTURE DATI Articolazione in moduli: NO Settore Scientifico Disciplinare: ING-INF/05 Docente responsabile: FLESCA SERGIO Crediti formativi universitari: 6 Numero ore lezioni: 36 Numero ore riservate attività didattiche assistite: 57 Numero ore esercitazioni: 21 Numero ore attività di laboratorio: 0 Tipologia di attività formativa (TAF): CARATTERIZZANTE Lingua di insegnamento: Italiano Anno di corso e Periodo didattico di erogazione: II ANNO, I SEMESTRE Insegnamento/i Propedeutico/i: FONDAMENTI DI INFORMATICA Risultati d’apprendimento previsti e competenze da acquisire: Il corso è finalizzato ad acquisire e sperimentare le tecniche di base per la valutazione della complessità di problemi e algoritmi e per la progettazione e realizzazione di strutture dati e algoritmi. La realizzazione degli algoritmi e delle strutture dati seguirà i principi della programmazione orientata agli oggetti e verrà utilizzato il linguaggio Java. Competenze da acquisire:    

comprensione dei concetti legati alla complessità dei problemi e degli algoritmi abilità ad impostare la risoluzione di problemi mediante algoritmi e valutare l’efficienza degli algoritmi realizzati abilità di verificare e dimostrare la correttezza di un algoritmo abilità di utilizzare strutture dati ed algoritmi noti in letteratura per la risoluzione di problemi

Argomenti delle lezioni: 1. COMPLESSITÀ DI PROBLEMI E ALGORITMI: Modelli di computazione (macchina di Turing, macchine RAM e RASP), analisi di complessità (temporale e spaziale) di algoritmi e problemi, funzioni di costo, notazione di rappresentazione delle funzioni di costo, casi possibili (medio, peggiore e migliore). 2. RICHIAMO DI ALGORITMI FONDAMENTALI: algoritmi di ordinamento e di ricerca iterativi, algoritmi su matrici e risoluzione di sistemi di equazioni. Analisi di complessità. 3. RICORSIONE E ALGORITMI DI TIPO DIVIDE ET IMPERA: La tecnica Divide et Impera e calcolo di complessità. Moltiplicazione efficiente di interi e di matrici. Algoritmi efficienti di ricerca e ordinamento. Algoritmi efficienti per il calcolo del k-mo maggiore. Ricorsione e tecnica divide et impera. Divide et Impera senza ricorsione. 4. ALBERI: Alberi binari, algoritmi di visita e progetto di iteratori. Alberi binari di ricerca: ricerca e bilanciamento. Alberi generali. B-Alberi. 5. DIZIONARI E CODE DI PRIORITÀ: Dizionari, vettori associativi, tabelle hash, code di priorità, heap, e loro applicazioni. 6. STRINGHE: definizioni preliminari, distanza fra stringhe, massima sottosequenza comune, string matching. 7. GRAFI: Proprietà e realizzazioni. Algoritmi di visita, alberi ricoprenti componenti connesse, ciclicità, chiusura transitiva, componenti fortemente connesse. 8. GRAFI PESATI: La rappresentazione di grafi pesati. Minimi alberi ricoprenti e distanze minime da un

nodo sorgente e loro computazione con tecniche golose. Calcolo delle distanze minime con tecniche di programmazione dinamica. BACKTRACKING e cenni alle classi di complessità di problemi decisionali. Argomenti delle esercitazioni: Progettazione e implementazione di strutture dati e algoritmi Modalità di erogazione della didattica: lezioni frontali Metodi di valutazione: esame scritto e orale Criteri di valutazione dell’apprendimento: Ci si aspetta che lo studente abbia acquisito le seguenti abilità: 1. Comprendere i concetti legati alla complessità dei problemi e degli algoritmi 2. Impostare la risoluzione di problemi mediante algoritmi e valutare l’efficienza degli algoritmi realizzati 3. Verificare e dimostrare la correttezza di un algoritmo 4. Utilizzare strutture dati ed algoritmi noti in letteratura per la risoluzione di problemi Criteri di misurazione dell’apprendimento: voto finale Criteri di attribuzione del voto finale: Il voto finale è attribuito valutando le abilità conseguite dallo studente Testi di riferimento e materiale didattico utilizzato e consigliato: Algoritmi e Strutture dati 2° Edizione Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano McGraw-Hill Orario e aule lezioni: Calendario prove valutazione:

http://www.dimes.unical.it/index.php/didattica...