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
   
Didattica
Algoritmi e strutture dati

Codice insegnamento: E3101Q107

Conoscenze:
metodologie di base per progettare algoritmi e analizzarne l’efficienza; strutture dati fondamentali

Abilità:
progettare e implementare algoritmi efficienti, scegliendo in modo opportuno le strutture dati da utilizzare

Docente/i:
 
A. Leporati, C. Zandron

Programma:

Introduzione

  • 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
  • Complessita' computazionale: caso pessimo, ottimo e medio
  • Valutazione dei tempi di esecuzione

Ricorsione

  • Definizioni ricorsive di insiemi
  • Algoritmi ricorsivi
  • Induzione e ricorsione

Approccio Divide-et-Impera

  • Definizione
  • Ordinamento di un vettore con algoritmo Merge-Sort

Valutazione del 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 stabilita'
  • Radix sort

Tipi astratti di dati e strutture dati - Introduzione

  • La nozione di tipo astratto (ADT, Abstract Data Type)
  • 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: array, lista concatenata

Code (queue)

  • Inserimento (enqueue), cancellazione (dequeue), attraversamento
  • Implementazioni: array, lista concatenata

Insiemi

  • Definizioni e operazioni fondamentali
  • Realizzazione tramite liste
  • Realizzazione tramite vettori caratteristici

Alberi

  • Nozione di grafo e proprieta'
  • 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 (Cenni)

Tabelle di hash

  • Indirizzamento diretto
  • Funzioni di hash
  • Risoluzione di collisioni tramite liste concatenate
  • Risoluzione di collisioni tramite indirizzamento aperto
  • Scansione lineare: inserimento, ricerca, cancellazione
  • Scansione quadratica
  • Doppio hashing: inserimento, ricerca, cancellazione

Testi consigliati:

T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduzione agli Algoritmi, Ed. Jackson Libri

Modalità di esame:

Scritto + Orale

 


IN ITALIANO:

Titolo dell’insegnamento:
Algoritmi e strutture dati

Docenti:
Alberto Leporati, Claudio Zandron

Modalità dell’esame:
Esame scritto e orale

Obiettivi dell’insegnamento:
 Illustrare le metodologie di base per progettare algoritmi e analizzarne l’efficienza, presentare allo studente le strutture dati fondamentali

Programma:
 1. Introduzione e definizioni iniziali: algoritmo, problema, istanza

2. Problema dell’ordinamento di un vettore: insertion sort

3. Analisi della complessita’ computazionale di un algoritmo

4. Programmazione ricorsiva e approccio Divide-et-Impera

5. Algoritmi di ordinamento: Merge Sort, Quick Sort, Heap Sort, Counting Sort, Radix Sort

6. Tipi astratti di dati

7. Liste, Pile, Code, Grafi e Alberi

8. Tabelle Hash


IN INGLESE:

Title of the course:
Algorithms and Data Structures

Lecturers:
Alberto Leporati, Claudio Zandron          

Examination:
written + oral examination

Aims:
To provide the student with the basic techniques to develop algorithms and to analyse their efficiency, and to introduce the student to the use of fundamental data structures

Main topics:  

1. Introduction and basic definitions: algorithm, problem, instance

2. Array sorting: insertion sort

3. Computational complexity analysis of algorithms

4. Recursive programming, Divide-and-Conquer technique

5. Sorting algorithms: Merge Sort, Quick Sort, Heap Sort, Counting Sort, Radix Sort

6. Abstract data types

7. Linked Lists, Stack, Queue, Graphs and Trees

8. Hash Tables

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 11/11/2013