Algoritmi 2

Laurea in Informatica - Università di Padova
Anno Accademico 2009/2010
Vecchio ordinamento (590)

Paolo Baldan

Brent Venable

Annunci

Obiettivi del corso

L'obiettivo del corso è quello di sviluppare nello studente una sensibilità alla complessità dei metodi usati per risolvere vari problemi computazionali di interesse. Proseguendo il cammino intrapreso nel primo corso di algoritmi, si studieranno alcune tecniche avanzate per la progettazione e l'analisi di algoritmi, strutture dati avanzate di interesse in vari ambiti dell'informatica e algoritmi su grafi. Il corso dà luogo al conseguimento di 6 CFU.

Programma di massima del corso

  1. Tecniche avanzate per il progetto e l'analisi di algoritmi
    • Algoritmi golosi.
    • Complessità ammortizzata.
  2. Strutture dati avanzate
    • Strutture dati per insiemi dinamici: B-alberi, heap binomiali e di Fibonacci
    • Strutture dati per insiemi disgiunti.
  3. Algoritmi su grafi
    • visita in larghezza e in profondità
    • ordinamento topologico
    • componenti fortemente connesse e albero di connessione minimo
    • cammini minimi
    • reti di flusso.

Modalità d'Esame e Appelli

L'esame consiste in una prova scritta e in una verifica orale opzionale.

Per poter sostenere una determinata prova scritta è necessario inviare un messaggio di posta elettronica ai docenti. In assenza di segnalazioni, l'esame non si terrà

Durante l'esame non è possibile consultare testi, appunti o altro materiale. Chi copia o consulta bigliettini (o affini) vedrà annullato lo scritto corrente e non potrà sostenere l'appello successivo.

Alcuni esempi di vecchi esami si possono trovare qui.
Appello Data Orario Aule
I 26 Novembre 2009 10.00 - 13.00 1BC/45
II 22 Marzo 2010 9:30 - 13.00 P200
III 19 Luglio 2010 9.30 - 12.30 P200
VI Settembre 2010 -- --

Riferimenti bibliografici

Il libro adottato è o la corrispondente traduzione italiana:

Il seguente calendario delle lezioni contiene un programma dettagliato e le copie delle slide utilizzate durante le lezioni nell'ultimo anno nel quali si è tenuto il corso (A.A. 2007/2008). Si ringrazia il Prof. Colussi per aver fornito il materiale dal quale le slide che seguono sono state rielaborate.

Data Tema della lezione Lucidi
1 07/04/08 Introduzione. Algoritmi Golosi. Problema della selezione delle attività [PDF] [PPT]
2 08/04/08 Codici di Huffmann [PDF] [PPT]
3 11/04/08 Problema della programmazione dei lavori e matroidi [PDF] [PPT]
4 14/04/08 Continuazione dalla lezione precedente [---][---]
5 15/04/08 analisi ammortizzata [PDF] [PPT]
6 18/04/08 Esercizi [---][---]
7 22/04/08 Esercizi [---][---]
8 28/04/08 Tavole Dinamiche [PDF] [PPT]
9 29/04/08 B-Alberi [PDF] [PPT]
10 05/05/08 Continuazione dalla lezione precedente [---][---]
11 06/05/08 Heap Binomiali [PDF] [PPT]
12 09/05/08 Continuazione dalla lezione precedente [---][---]
13 12/05/08 Strutture dati per insiemi disgiunti [PDF] [PPT]
14 13/05/08 Funzione di Ackermann e complessità per insiemi disgiunti Libro, Paragrafo 21.4
15 16/05/08 Cont. dalla lezione precedente ed esercizi [---][---]
- 19/05/08 Fino alla fine del corso:
Lezioni della Dott.ssa Venable
[---][---]

Esercizi e problemi discussi in classe (la numerazione si riferisce al libro di testo):

Alcuni esercizi svolti (gentilmemete forniti dal prof. Colussi: [Parte 1] [Parte 2] [Parte 3]