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).

Richiami di nozioni di relazione di equivalenza e d'ordine.

Insiemi parzialmente ordinati e reticoli.

Struttura della memoria durante l'esecuzione dei programmi e tipi di passaggio degli argomenti.

Tipi di Dato e Strutture Dati 

Vettori, Matrici, Matrici Simmetriche, Liste, Liste Ordinate, Pile, Code, Heap, Alberi Binari di Ricerca, Alberi Generali, Code di Priorita', Insiemi, Dizionari, Tabelle Hash, Grafi Orientati e Non Orientati, Grafi Pesati.

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

Heap Sort

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).

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, Generics, Interfacce) Implementazione delle strutture dati e degli algoritmi studiati in Java e studio di librerie standard di Java

Ultimo aggiornamento: 02-01-2025

• Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano, Algoritmi e strutture dati, McGraw-Hill.
• 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. Bertossi, Strutture, Algoritmi, Complessita', ECIG, Universita' di Pisa.
• Cay Horstmann, Concetti di informatica e fondamenti di Java, Apogeo.

Ultimo aggiornamento: 02-01-2025

Conoscenze e capacità di comprensione:

Gli studenti acquisiranno una conoscenza approfondita dei concetti fondamentali della computabilità, della complessità computazionale e delle strutture dati, con una comprensione critica delle tecniche di progettazione algoritmica e delle applicazioni pratiche nei linguaggi di programmazione object-oriented.

Capacità di applicare conoscenze e comprensione:

Gli studenti saranno in grado di applicare le conoscenze acquisite per progettare, implementare e ottimizzare algoritmi in Java, utilizzando correttamente strutture dati e tecniche di programmazione. Saranno in grado di risolvere problemi complessi in modo autonomo e rigoroso, integrando concetti teorici con la pratica.

Autonomia di giudizio:

Gli studenti svilupperanno la capacità di analizzare criticamente problemi computazionali, scegliendo e giustificando le soluzioni più adeguate in termini di complessità e risorse. Saranno in grado di valutare vantaggi e svantaggi di diverse tecniche e approcci, considerando scenari reali o ipotetici.

Capacità di comunicazione:

Gli studenti saranno in grado di comunicare chiaramente concetti complessi, soluzioni algoritmiche e strutture dati a interlocutori specialisti e non specialisti, utilizzando un linguaggio tecnico preciso e strumenti appropriati come diagrammi, pseudocodice e codice Java documentato.

Capacità di apprendimento:

Gli studenti acquisiranno competenze di apprendimento autonomo per approfondire ulteriormente le tematiche del corso e affrontare nuove tecnologie e paradigmi di programmazione. Saranno in grado di accedere a fonti scientifiche, analizzarle criticamente e integrarle nel loro processo di apprendimento continuo.

Ultimo aggiornamento: 02-01-2025

Conoscenza dei fondamenti della programmazione e conoscenza basilare del linguaggio Java e dell'ambiente di esecuzione Eclipse.

Ultimo aggiornamento: 02-01-2025

Lezioni frontali ed esercitazioni

Ultimo aggiornamento: 02-01-2025

Prova scritta che verte sulla soluzione in Java di problemi che necessitano l'uso corretto di strutture dati e prova orale che mira ad accertare le conoscenze acquisite su tutto il programma del corso.

Il punteggio, che tiene conto sia della prova scritta sia della prova orale, verrà attribuito secondo il seguente schema:

30 e lode: conoscenza completa, approfondita e critica degli argomenti, eccellente proprietà di linguaggio, completa ed originale capacità interpretativa, piena capacità di applicare autonomamente le conoscenze per risolvere i problemi proposti;

28 - 30: conoscenza completa e approfondita degli argomenti, ottima proprietà di linguaggio, completa ed efficace capacità interpretativa, in grado di applicare autonomamente le conoscenze per risolvere i problemi proposti;

24 - 27: conoscenza degli argomenti con un buon grado di padronanza, buona proprietà di linguaggio, corretta e sicura capacità interpretativa, buona capacità di applicare in modo corretto la maggior parte delle conoscenze per risolvere i problemi proposti;

20 - 23: conoscenza adeguata degli argomenti ma limitata padronanza degli stessi, soddisfacente proprietà di linguaggio, corretta capacità interpretativa, più che sufficiente capacità di applicare autonomamente le conoscenze per risolvere i problemi proposti;

18 - 19: conoscenza di base degli argomenti principali, conoscenza di base del linguaggio tecnico, sufficiente capacità interpretativa, sufficiente capacità di applicare le conoscenze di base acquisite;

<18 Insufficiente: non possiede una conoscenza accettabile degli argomenti trattati durante il corso.

Ultimo aggiornamento: 02-01-2025