Questo insegnamento ha lo scopo di illustrare le principali tecniche di progettazione di algoritmi e di descrivere ed analizzare gli algoritmi di base più diffusi e le strutture dati in essi utilizzate, con particolare…
Scheda dell'insegnamento
Obiettivi formativi
Questo insegnamento ha lo scopo di illustrare le principali tecniche di progettazione di algoritmi e di descrivere ed analizzare gli algoritmi di base più diffusi e le strutture dati in essi utilizzate, con particolare riferimento agli aspetti di complessità computazionale.
Conoscenza e capacità di comprensione: Lo studente acquisirà: consapevolezza dell'importanza della progettazione efficiente degli algoritmi; le conoscenze fondamentali per l'analisi delle risorse computazionali richieste da un algoritmo; i principali algoritmi e strutture dati in grado di risolvere problemi di base di natura computazionale. Conoscenza e capacità di comprensione applicate: Lo studente acquisirà le metodologie proprie dell'analisi e della progettazione algoritmica. In particolare sarà in grado di progettare una serie di algoritmi classici (ordinamento, ricerca, ecc.) operanti su strutture dati differenti (array, liste, alberi e grafi) ed analizzarne la complessità computazionale. La capacità di applicare queste tecniche verrà sviluppata ed affinata nelle esercitazioni di laboratorio dove una serie di algoritmi verranno analizzati, elaborati ed implementati in linguaggio C. Autonomia di giudizio: Lo studente sarà in grado di applicare le metodologie proprie dell'algoritmica per la comprensione e la risoluzione di nuovi problemi di natura computazionale. Le discussioni critiche in aula e le esercitazioni serviranno a stimolare e sviluppare l'autonomia di giudizio dello studente. Abilità comunicative: Lo studente acquisirà la capacità di esprimere i concetti fondamentali propri degli algoritmi e delle strutture dati con terminologia appropriata e rigorosa. Imparerà a descrivere i problemi inerenti l'analisi e la progettazione di algoritmi efficienti e le metodologie adottate per la loro soluzione. Capacità di apprendere : Lo studente acquisirà la capacità di studiare ed apprendere tecniche algoritmiche e strutture dati fondamentali. Imparerà a riconoscere l'importanza delle risorse computazionali (in particolare spazio e tempo) in modo da poter sviluppare autonomamente soluzioni per nuove problematiche inerenti la progettazione efficiente di programmi.
Programma
01. Introduzione agli algoritmi e alle strutture dati: 01.01 Algoritmi e loro tipologie 01.02 Correttezza di un algoritmo rispetto ad un problema 01.03 Complessità di un algoritmo rispetto all'uso di risorse 01.04 Strutture dati e loro tipologie 02. Classi di problemi: 02.01 Problemi decidibili e indecidibili 02.02 Problemi trattabili e intrattabili 02.03 Teorema di Cook 02.04 NP-completezza 03. Complessità degli algoritmi: 03.01 Notazioni per esprimere la complessità asintotica 03.02 Calcolo della complessità di algoritmi non ricorsivi 03.03 Calcolo della complessità di algoritmi ricorsivi 04. Algoritmi per array: 04.01 Array: definizioni di base e problemi classici 04.02 Algoritmo di visita per array 04.03 Algoritmo di ricerca lineare per array 04.04 Algoritmo di ricerca binaria per array ordinati 04.05 Criteri di confronto per algoritmi di ordinamento per array 04.06 Insertsort 04.07 Selectsort 04.08 Bubblesort 04.09 Mergesort 04.10 Quicksort 04.11 Heapsort 05. Algoritmi per liste: 05.01 Liste: definizioni di base e problemi classici 05.02 Algoritmi di visita, ricerca, inserimento e rimozione per liste 05.03 Algoritmi di inserimento e rimozione per code 05.04 Algoritmi di inserimento e rimozione per pile 06. Algoritmi per alberi: 06.01 Alberi: definizioni di base e problemi classici 06.02 Algoritmi di visita e ricerca per alberi binari 06.03 Algoritmi di ricerca, inserimento e rimozione per alberi binari di ricerca 06.04 Criteri di bilanciamento per alberi binari di ricerca 07. Tabelle hash: 07.01 Dizionari, array associativi, mappe: funzioni di base e realizzazione con array, liste, alberi 07.02 Tabelle ad accesso diretto 07.03 Funzioni hash 07.04 Risoluzione delle collisioni: liste di collisione, indirizzamento aperto 08. Algoritmi per grafi: 08.01 Grafi: definizioni di base e problemi classici 08.02 Algoritmi di visita e ricerca per grafi 08.03 Algoritmo di ordinamento topologico per grafi diretti e aciclici 08.04 Proprietà del percorso più breve 08.05 Algoritmo di Bellman-Ford 08.06 Algoritmo di Dijkstra 09. Tecniche algoritmiche: 09.01 Tecnica del divide et impera 09.02 Programmazione dinamica 09.03 Tecnica golosa 09.04 Tecnica per tentativi e revoche 10. Attività di laboratorio: 10.01 Elementi di linguaggio C: richiami, editing, compilazione, debugging 10.02 Valutazione sperimentale della complessità degli algoritmi: timing e contatori 10.03 Generatori di numeri pseudocasuali: funzioni rand e srand 10.04 Confronto sperimentale degli algoritmi di ordinamento per array 10.05 Implementazione di algoritmi per liste 10.06 Implementazione di algoritmi di visita e ricerca per alberi binari 10.07 Implementazione di algoritmi su grafi: visita in ampiezza e profondità di un grafo
Non vi sono propedeuticità obbligatorie. Si suggerisce di sostenere l'esame di Algoritmi e Strutture Dati dopo aver sostenuto gli esami di Programmazione Procedurale e Analisi Matematica 1 e prima di sostenere gli esami di Sistemi Operativi, Basi di Dati, Programmazione e Modellazione a Oggetti e Programmazione Logica e Funzionale.
Il materiale didattico predisposto dalla/dal docente in aggiunta ai testi consigliati (come ad esempio diapositive, dispense, esercizi, bibliografia) e le comunicazioni della/del docente specifiche per l'insegnamento sono reperibili all'interno della piattaforma Moodle › blended.uniurb.it
Lezioni teoriche ed esercitazioni di laboratorio.
Modalità d'esame
Prova scritta e prova orale. Tale modalità di accertamento delle conoscenze acquisite è dovuta, in particolare, alla volontà di verificare le capacità di conoscenza e comprensione applicate, con particolare riferimento al problem solving e all' uso efficiente delle risorse computazionali e, al contempo, alla volontà di verificare sia la capacità di sintesi dello studente che le abilità comunicative ed espressive. La prova scritta (della durata di 2 ore) consiste in un esercizio di programmazione (da svolgere al calcolatore) e in una serie di domande a risposta chiusa; tale prova viene valutata in trentesimi ed è ritenuta sufficiente se il relativo voto, che rimane valido per il solo appello in cui viene sostenuta, è di almeno 18/30. Se previsto dal calendario accademico, nel periodo di sospensione delle attività didattiche del semestre in cui si tiene l'insegnamento viene svolta una prova scritta intermedia, a cui può partecipare solo chi è al primo anno, che consiste in 20 domande a risposta chiusa cui rispondere in 50 minuti. Essa è superata se il voto è di almeno 12/20 su un massimo di 20/20, nel qual caso si ottiene l'esonero dalle domande della prova scritta relative alle sezioni del programma oggetto della prova intermedia; il voto rimane valido solo per gli appelli della prima sessione d'esame successiva al semestre in cui si svolge la prova intermedia. La prova orale, che può essere sostenuta solo previo superamento della prova scritta, consiste in domande sul programma dell'insegnamento. Se superata, comporta un aggiustamento per eccesso o per difetto di al più 5/30 del voto della prova scritta, determinando così il voto finale. Nel periodo di sospensione delle attività didattiche previsto dal calendario accademico verranno svolte delle prove intermedie.
Testi di riferimento
Cormen, Leiserson, Rivest, Stein, "Introduzione agli Algoritmi e alle Strutture Dati", McGraw-Hill, 2023. (Cormen, Leiserson, Rivest, Stein, "Introduction to Algorithms", MIT Press, 2022.) Demetrescu, Finocchi, Italiano, "Algoritmi e Strutture Dati", McGraw-Hill, 2008. Crescenzi, Gambosi, Grossi, "Strutture di Dati e Algoritmi", Pearson/Addison-Wesley, 2012. Sedgewick, "Algoritmi in C", Pearson, 2015. (Sedgewick, "Algorithms in C", Addison-Wesley, 1998.)
Codice insegnamento 271804