PROGRAMMAZIONE MOD. A
L'obiettivo del corso è quello di fornire allo studente competenze di base sulla rappresentazione delle principali strutture di dati e sui principali algoritmi per la loro gestione. Introduce inoltre sulle tecniche per la valutazione della complessità computazionale di un algoritmo e di un problema. Il corso introduce gli studenti al linguaggio Java.
nessuna
Modulo A
Introduzione alla programmazione in Java:
• Variabili, costanti e tipi di dato elementare.
• Assegnamento e statement composto.
• Input/output di base.
• Espressioni e operatori.
• Strutture di controllo: selezione e cicli.
• Metodi e classi.
• Array.
• Introduzione alla ricorsione.
Modulo B
Introduzione allo studio della complessità di un algoritmo.
Algoritmi ricorsivi, modalità di realizzazione e rientranza
Algoritmi di ordinamento:
• Definizione del problema e lower bound alla complessità del problema.
• Insertion sort - studio caso pessimo e caso ottimo.
• Merge sort - studio caso pessimo e caso ottimo.
• Heap sort - studio caso pessimo e caso ottimo.
• Quick sort - studio caso pessimo e caso medio.
• Random Quick sort.
Programmazione per oggetti (java):
• Ereditarietà
• Polimorfismo
• Incapsulamento e cenni sulle interfacce
Strutture dati elementari: Pile, Liste, alberi (cenni).
Esempi di calcolo con numeri costituiti da moltissime cifre (Pgreco, numeri primi, ecc)
• Uso della libreria “big integer” e “big decimal” in java
• Prototipazioni con Python
Libri di Testo:
• Introduction To Algorithms. Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, Clifford Stein. MIT Press.
• C. Thomas Wu: "Java. Fondamenti di Programmazione.". McGraw-Hill.
Appunti del docente: disponibili sul portale della didattica.