Obiettivi

Il corso ha l’obiettivo generale di offrire agli studenti la possibilità di apprendere e sperimentare una serie di strumenti metodologici utili per l’analisi e per la progettazione di algoritmi.

Oltre a fornire nozioni basilari di teoria della complessità computazionale, come strumento per valutare l’efficienza degli algoritmi e la difficoltà dei problemi, il corso illustrerà sia i principali tipi di strutture dati in memoria principale, sia alcune tecniche fondamentali per la progettazione di algoritmi.

Prerequisiti

Conoscenza del linguaggio Java e dei rudimenti della programmazione orientata agli oggetti.

Crediti Didattici

Il modulo ha valore formativo pari a 5 crediti didattici e consta di 46 ore, suddivise in 33 ore di lezione, e 13 ore di esercitazione.

Programma

Le ore di lezione verteranno sulle tematiche seguenti:

1. Fondamenti della teoria della complessità computazionale

- Modelli di computazione.

- Notazioni asintotiche per la caratterizzazione delle funzioni di costo.

- Analisi dei casi possibili (medio, peggiore e migliore).

2. Richiamo di strutture dati e algoritmi fondamentali

- Vettori, liste, pile, code, matrici.

- Algoritmi iterativi di ordinamento e di ricerca e loro analisi di complessità.

3. Tecniche di progettazione degli algoritmi.

- Approccio Divide et Impera e ricorsione.

- Programmazione dinamica.

- Backtracking.

- Approccio goloso.

4. Alberi

- Alberi binari, memorizzazione e algoritmi di visita.

- Alberi binari di ricerca. Bilanciamento: alberi AVL.

- Alberi generali.

5. Dizionari e Code di Priorità

- Dizionari, vettori associativi, tabelle hash

- Code di priorità, heap, alberi di Fibonacci, vettori di code.

6. Grafi

- Proprietà matematiche.

- Metodi di rappresentazione e algoritmi di visita.

- Algoritmi per il calcolo di: alberi ricoprenti, componenti connesse, ordinamenti topologici, chiusura transitiva.

7. Grafi pesati

- Rappresentazione.

- Calcolo di minimi alberi ricoprenti e di distanze minime (con tecniche golose e di programmazione dinamica).

- Problemi di ricerca su grafi (con backtracking).

Nelle ore di esercitazione saranno ripresi ed approfonditi i principali aspetti del Java, con particolare riferimento ai costrutti utili per la programmazione orientata agli oggetti.

Particolare attenzione sarà dedicata agli aspetti concernenti la definizione di classi derivate, di classi astratte e di interfacce, ed al polimorfismo.

Saranno illustrate le librerie Java per la gestione di collezioni di dati (interfaccia Collection, vettori dinamici, liste concatenate, insiemi, mappe associative)

Infine saranno illustrati vari esempi di applicazione dei concetti e dei metodi appresi nelle lezioni.

Libro di Testo

C. Demetrescu, I. Finocchi, G. F. Italiano

Algoritmi e Strutture dati, 2° Edizione

McGraw-Hill, 2008

Testi Complementari

C. Demetrescu, U. Ferraro Petrillo, I. Finocchi, G. F. Italiano

Progetto di algoritmi e strutture dati in Java

McGraw-Hill, 2007

Altro materiale didattico

· Lucidi delle lezioni del corso

· Esercitazioni del corso

Modalità di esame

L'esame prevede lo svolgimento di una prova scritta e di una prova orale.