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

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