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 Strutture Dati (elementi)

Docente: P. Bonizzoni, R. Leporati, C. Zandron

Crediti: 6

Modalità di esame: scritto + orale + esercitazione di laboratorio

Descrizione e Programma del corso

Obiettivi: Progettazione e analisi dell'efficienza di algoritmi; utilizzo delle strutture dati fondamentali. Durante il corso saranno affrontati i seguenti argomenti:

  • Nozioni fondamentali (algoritmo, problema, istanza); Pseudocodice e macchina RAM; Problema dell'ordinamento di un vettore (Algoritmo insertion sort)
  • Nozioni matematiche: Limiti asintotici inferiori e superiori; Il principio di induzione; Nozioni varie (base, tetto, sommatorie, approssimazioni, polinomi)
  • Analisi di algoritmi: Dimensione dei dati di un problema; Complessità computazionale; Valutazione dei tempi di esecuzione
  • Ricorsione: Definizioni ricorsive di insiemi; Algoritmi ricorsivi; Induzione
  • Approccio Divide-et-Impera: Definizione; Algoritmo Merge-Sort
  • Tempo di esecuzione di algoritmi ricorsivi (equazioni di ricorrenza): Definizioni; Metodo Sostituzione; Metodo Iterativo e alberi di ricorsione; Metodo Principale
  • Ordinamento in loco: Algoritmo Quick-sort; Quick-sort Randomizzato
  • Algoritmo di ordinamento Heapsort: Grafi e Alberi (nozioni fondamentali); Nozione di Heap; Heapsort
  • 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
  • Tipi astratti di dati e strutture dati (Introduzione): La nozione di tipo astratto (ADT); Insiemi dinamici; Operazioni fondamentali su insiemi dinamici
  • Liste concatenate: Liste semplici e doppie; Liste circolari; Uso di sentinelle; Operazioni fondamentali; Gestione di liste mediante array multipli
  • Pile (stack): Inserimento (push), cancellazione (pop); Implementazioni
  • Code (queue): Inserimento, cancellazione, attraversamento; Implementazioni
  • Insiemi: Definizioni e operazioni fondamentali; Realizzazione tramite liste; Realizzazione tramite vettori caratteristici
  • Alberi: Nozione di grafo e proprietà; Alberi generici: definizione ricorsiva; Nozioni generali (nodo, figlio, antenato, discendente, altezza...); Implementazione (record con puntatori; varianti)
  • 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)
  • Tabelle di hash: Indirizzamento diretto; Funzioni di hash; Risoluzione di collisioni tramite liste concatenate e indirizzamento aperto; Scansione lineare; Scansione quadratica; Doppio hashing

Vai al sito web del corso

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