Page begin -
Logo DISCO
|
Go to the Highly accessible area
|
Go to the Content page
|
Go to the End of content
|
Go to the Main menu
|
Go to the Navigation Bar (location)
|
Go to the Navigation menu (tree)
|
Go to the Commands list
|
Go to the Further readings
|
Go to the Bottom Menu
|
Logo Ateneo
   
Enrolled
Algoritmi e Programmazione

Docente: Paola Bonizzoni - Felice Cardone – Alessandra Agostini - Marco Antoniotti

Crediti: 13 CFU

Obiettivi dell'insegnamento:

L’insegnamento si propone di condurre lo studente ad approfondire le tecniche della programmazione orientata agli oggetti.
Lo studente acquisirà inoltre le metodologie fondamentali di progetto ed analisi degli algoritmi e delle strutture dati elementari, unitamente ai loro aspetti implementativi.

Descrizione e Programma dell'insegnamento:

Il corso si articola nei seguenti moduli:

  • Algoritmi e Strutture Dati 1: 8 CFU Paola Bonizzoni - Felice Cardone
  • Programmazione 3: 5 CFU Alessandra Agostini - Marco Antoniotti

Programma per Algoritmi e Strutture Dati 1

  1. Nozioni fondamentali (algoritmo, problema, istanza); Pseudocodice e macchina RAM; Problema dell'ordinamento di un vettore (Algoritmo insertion sort)
  2. Nozioni matematiche: Limiti asintotici inferiori e superiori; Il principio di induzione; Nozioni varie (base, tetto, sommatorie, approssimazioni, polinomi)
  3. Analisi di algoritmi: Dimensione dei dati di un problema; Complessità computazionale; Valutazione dei tempi di esecuzione
  4. Ricorsione: Definizioni ricorsive di insiemi; Algoritmi ricorsivi; Induzione
  5. Approccio Divide-et-Impera: Definizione; Algoritmo Merge-Sort
  6. Tempo di esecuzione di algoritmi ricorsivi (equazioni di ricorrenza): Definizioni; Metodo Sostituzione; Metodo Iterativo e alberi di ricorsione; Metodo Principale
  7. Ordinamento in loco: Algoritmo Quick-sort; Quick-sort Randomizzato
  8. Algoritmo di ordinamento Heapsort: Grafi e Alberi (nozioni fondamentali); Nozione di Heap; Heapsort
  9. Altri algoritmi di ordinamento: Selection sort; Bubble sort; Ordinamento in tempo lineare; Limite inferiore per ordinamenti basati su confronti; Counting sort; Concetto di stabilità; Radix sort
  10. Tipi astratti di dati e strutture dati (Introduzione): La nozione di tipo astratto (ADT); Insiemi dinamici; Operazioni fondamentali su insiemi dinamici
  11. Liste concatenate: Liste semplici e doppie; Liste circolari; Uso di sentinelle; Operazioni fondamentali; Gestione di liste mediante array multipli
  12. Pile (stack): Inserimento (push), cancellazione (pop); Implementazioni
  13. Code (queue): Inserimento, cancellazione, attraversamento; Implementazioni
  14. Insiemi: Definizioni e operazioni fondamentali; Realizzazione tramite liste; Realizzazione tramite vettori caratteristici
  15. Alberi: Nozione di grafo e proprietà; Alberi generici: definizione ricorsiva; Nozioni generali (nodo, figlio, antenato, discendente, altezza...); Implementazione (record con puntatori; varianti)
  16. Alberi binari: Attraversamento (ordine anticipato, simmetrico, posticipato); Alberi binari di ricerca e operazioni fondamentali (inserimento, cancellazione, ricerca, max, min, successore, predecessore)
  17. Tabelle di hash: Indirizzamento diretto; Funzioni di hash; Risoluzione di collisioni tramite liste concatenate e indirizzamento aperto; Scansione lineare; Scansione quadratica; Doppio hashing

Programma per Programmazione 3

  1. Approfondimenti sull’ereditarietà in Java
  2. Le interfacce
  3. Eccezioni
  4. Gestione Input/Output (I/O) in Java
    1. Classe Scanner
    2. Classe File
    3. I/O testuale
    4. I/O binario
  5. Vettori e Liste in Java
  6. Code e Pile in Java
  7. Programmazione Ricorsiva
  8. Definizione e utilizzo di strutture dati dinamiche ricorsive (alberi)
  9. “Generics” Java e polimorfismi
  10. Utilizzo di librerie standard Java: il “Collection Framework”
  11. Realizzazione d’interfacce grafiche ed introduzione alla programmazione ad eventi.

 

Modalità di esame: L'esame si articola in prove teorico-pratiche

Testi consigliati:

  • Walter Savitch, Java: An Introduction to Problem Solving & Programming, Fourth Edition,  Prentice Hall, 2005
  • Thomas H.Cormen, Charles E. Leireson, Ronald L. Rivest e Clifford Stei, Introduction to Algorithms (prima o seconda edizione), MIT Press e McGraw-Hill

Further readings
(C) Copyright 2016 - Dipartimento Informatica Sistemistica e Comunicazione - Viale Sarca, 336
20126 Milano - Edificio U14
redazioneweb@disco.unimib.it - last update of this page 25/03/2011