Inizio della pagina -
Logo DISCO
|
Visita la Versione ad elevata leggibilità
|
Vai al Contenuto della pagina
|
Vai alla Fine dei contenuti
|
Vai al Menu Principale
|
Vai alla Barra di navigazione (sei in)
|
Vai al Menu di navigazione (albero)
|
Vai alla Lista dei comandi
|
Vai alla Lista degli approfondimenti
|
Vai al Menu inferiore
|
Logo Ateneo
   
Per gli Studenti
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.
Approfondimenti

Google Translate
Translate to English Translate to French Translate to German Translate to Spanish Translate to Chinese Translate to Portuguese Translate to Arabic
Translate to Albanian Translate to Bulgarian Translate to Croatian Translate to Czech Translate to Danish Translate to Dutch Translate to Finnish Translate to Greek Translate to Hindi
Translate to Hungarian Translate to Irish Translate to Japanese Translate to Korean Translate to Norwegian Translate to Polish Translate to Romanian Translate to Russian Translate to Serbian
Translate to Slovenian Translate to Swedish Translate to Thai Translate to Turkish

(C) Copyright 2016 - Dipartimento Informatica Sistemistica e Comunicazione - Viale Sarca, 336
20126 Milano - Edificio U14
redazioneweb@disco.unimib.it - ultimo aggiornamento di questa pagina 25/03/2011