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 – 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

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