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
   
Education
Algoritmi e Programmazione

Docente: Paola Bonizzoni - Felice Cardone - Francesco Tisato - Marco Antoniotti

Crediti: 13 CFU

Descrizione e Programma del corso

Il corso si articola nei seguenti moduli:

  • Algoritmi e Strutture Dati 1: 8 CFU Paola Bonizzoni - Felice Cardone
  • Programmazione 3: 5 CFU Francesco Tisato - 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); Questioni di bilanciamento (Alberi AVL)
  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. Ereditarietà: definizione. Ereditarietà singola e multipla. Ereditarietà in Java
  2. La classe Object
  3. Le visibilità per attributi e metodi
  4. Costruttori
  5. Override di metodi
  6. Il casting
  7. Le classi astratte e i metodi astratti
  8. Polimorfismo
  9. Le interfacce
  10. Definizione e utilizzo di strutture dati dinamiche

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

Testi consigliati:

  • Walter Savitch, Java: An Introduction to Computer Science & Programming, Prentice Hall, 1998
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein Introduction to Algorithms (seconda o prima 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