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: Alessandra Agostini - Marco Antoniotti – Gianluigi Ciocca - Davide Ciucci – Giorgio De Michelis – Alberto Dennunzio

Crediti: 12 CFU

Obiettivi dell'insegnamento:

Lo studente acquisirà le metodologie fondamentali di progetto ed analisi degli algoritmi e delle strutture dati elementari. L’insegnamento si propone inoltre di approfondire alcune tecniche avanzate di programmazione orientata agli oggetti in Java utili nell’implementazione degli algoritmi e strutture dati elementari.

Descrizione e Programma dell'insegnamento:

Il corso si articola nei seguenti moduli:

  • Algoritmi e Strutture Dati 1: 8 CFU Davide Ciucci – Giorgio De Michelis – Alberto Dennunzio
  • Programmazione 3: 4 CFU Alessandra Agostini - Marco Antoniotti– Gianluigi Ciocca

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.       Eccezioni

3.       Gestione Input/Output (I/O) in Java

a.       Classe Scanner

b.       Classe File

c.       I/O testuale

d.       I/O binario

4.       Vettori e Liste in Java

5.       Code e Pile in Java

6.      Programmazione Ricorsiva

7.       Definizione e utilizzo di strutture dati dinamiche ricorsive (alberi)

8.       “Generics” Java e polimorfismi

9.       Utilizzo di librerie standard Java: il “Collection Framework”

 

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

Testi consigliati:

  • Walter Savitch, Absolute Java, Second Edition, Addison-Wesley Pub. Co., 2005
  • 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