Dipartimento di Ingegneria dell'Informazione, delle Infrastrutture e dell'Energia Sostenibile - Università Mediterranea di Reggio Calabria - Didattica

Questo sito utilizza cookie tecnici e di terze parti. Se vuoi saperne di più o negare il consenso consulta l'informativa sulla privacy. Proseguendo la navigazione o cliccando su "Chiudi" acconsenti all'uso dei cookie. Chiudi

ALGORITMI E STRUTTURE DATI

Corso

Ingegneria dell'Informazione

Curriculum

Curriculum unico

Orientamento

Orientamento unico

Anno Accademico

2017/2018

Crediti

Settore Scientifico Disciplinare

ING-INF/05

Anno

Secondo anno

Unità temporale

Primo semestre

Ore aula

Attività formativa

Attività formative caratterizzanti

Canale unico

Docente

FRANCESCO ANTONIO BUCCAFURRI

Obiettivi

Comprensione e assimilazione del concetto di tipo di dato astratto come strumento di rappresentazione della realtà nonché dei principali algoritmi, con particolare riguardo agli algoritmi su grafi (ed alle applicazioni alle reti di computer), delle principali tecniche di programmazione e dell'analisi di complessità degli algoritmi. Capacità di applicare i concetti teorici assimilati nella risoluzione di problemi e opportuni casi d’uso. Acquisizione di un appropriato livello di autonomia nell’apprendimento delle tecniche di progetto di algoritmi e di implementazione che seguono il paradigma object-oriented (con riferimento a Java). Capacità di comunicare con adeguata competenza tecnica con altri partner in attività di gruppo di implementazione su larga scala. Capacità di apprendimento di nuove tecniche di programmazione e strutture dati più avanzate nonché di diversi linguaggi che seguono il paradigma object-oriented.

Programma

Introduzione
Problemi e algoritmi
Cenni sulla nozione di Calcolabilita’ e sulla tesi di Church-Turing.
Complessità computazionale di problemi ed algoritmi (notazione O, Omega, Theta)
Tipi di Dato e Strutture Dati
Vettori, Matrici, Liste,Liste Ordinate, Pile, Code, Heap, Alberi Binari di Ricerca, Alberi
Generali, Code di Priorita', Insiemi, Dizionari, Tabelle Hash, Vettori Associativi, Grafi
Orientati e Non Orientati, Grafi Pesati, Trie.
Algoritmi Fondamentali, Tecniche di Programmazione e Algoritmi su Grafi
Algoritmi di Base su Grafi (Raggiungibilita' di nodi in un grafo, Componenti Connesse,
Albero Ricoprente)
Tecniche di Ricerca e di Ordinamento
Divide et Impera (approf: Ricerca Binaria, Merge Sort, Tecniche Quadratiche di
Ordinamento, Calcolo del Fattoriale, Calcolo della Successione di Fibonacci)
Equazione di Ricorrenza per la definizione della complessita’ delle tecniche Divide et
Impera.
Tecniche Golose (Knapsack, Algoritmo di Dijkstra, Algoritmo di Prim, Implementazione con vettori e con heap indicizzato, cenni all’Algoritmo di Huffman per compressione lossless).
Esempi di Applicazione alle Reti di Computer degli Algoritmi su Grafi (routing, connettivita’,
etc.).
Programmazione OO in Java
Caratteristiche OO di Java (Incapsulamento, Ereditarietà, Polimorfismo, Template)
Implementazione delle strutture dati e degli algoritmi studiati in Java.

Testi docente

• Camil Demetrescu, Umberto Ferraro Petrillo, Irene Finocchi, Giuseppe F. Italiano,
Progetto di algoritmi e strutture dati in Java, McGraw-Hill.
• Cormen-Leiserson-Rivest: Introduzione agli algoritmi e strutture dati 2a ediz.,
McGrawHill.
• Ausiello, et al., Teoria e Progetto di Algoritmi Fondamentali, Franco Angeli.
• A.A., Bertossi, Strutture, Algoritmi, Complessita', ECIG, Universita' di Pisa.
• Cay Horstmann, Concetti di informatica e fondamenti di Java, Apogeo.
• Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano, Algoritmi e strutture dati
2/ed, McGraw-Hill.

Erogazione tradizionale

Sì

Erogazione a distanza

Frequenza obbligatoria

Valutazione prova scritta

Sì

Valutazione prova orale

Sì

Valutazione test attitudinale

Valutazione progetto

Valutazione tirocinio

Valutazione in itinere