.dsy:it. (http://www.dsy.it/forum/)
- Algoritmi e strutture dati II (http://www.dsy.it/forum/forumdisplay.php?forumid=208)
-- [Trubian] Diario del Corso 04/05 (http://www.dsy.it/forum/showthread.php?threadid=17727)

[Algoritmi II] Diario del Corso 04/05

"Algoritmi e Strutture Dati II" è un corso complementare per le lauree triennali e le specialistiche, strutturato in due moduli.
Seguono alcune informazioni generali sul corso:

Docente: M. Trubian

Orari delle lezioni:
martedì 12.00 - 14.30
venerdì 16.30 - 19.30

in aula Alfa (via Comelico).

Sito del corso:
Il sito del corso è questo.

Materiale didattico:
I testi utilizzati sono:

- A. Bertossi, Algoritmi e strutture di dati, UTET, 2000.

- T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduzione agli algoritmi, Jackson Libri, II edizione italiana 1999.


Modalità d'esame:
L'esame per il primo modulo consiste di un orale sugli argomenti trattati. Per chi segue entrambi i moduli, è previsto un orale sugli argomenti del primo modulo (meno approfondito) e lo svolgimento di un progetto in C o C++.

__________________
The man in black fled across the desert and the gunslinger followed.

Lezione del 01-03-05

Argomenti trattati nella lezione di oggi:

- Heap binomiali e alberi binomiali: proprietà e funzioni

__________________
The man in black fled across the desert and the gunslinger followed.

Lezione del 04-03-05

Argomenti trattati nella lezione di oggi:

- Heap di Fibonacci:
* Caratteristiche e proprietà
* Analisi ammortizzata
* Operazioni
- Treap:
* Caratteristiche e proprietà
* Il problema di esistenza
* Il problema del bilanciamento
* Operazioni
* Analisi

__________________
The man in black fled across the desert and the gunslinger followed.

Lezione del 08-03-05

Argomenti trattati nella lezione di oggi:

- Macchine parallele, algoritmi paralleli; modello SISD, MISD, SIMD, MIMD
- PRAM con memoria condivisa; modelli EREW, CREW, ERCW, CRCW; CW comune, arbitraria, a priorità, combinata
- Simulazione di CR con ER, di CW con EW
- Rete di interconnessione: mesh, n-cubo, albero, shuffle; algoritmi di broadcast
- Tempo, lavoro, efficienza
- Algoritmi paralleli elementari

__________________
The man in black fled across the desert and the gunslinger followed.

Lezione del 11-03-05

Argomenti trattati nella lezione di oggi:

- Circuiti combinatori; confrontatori; teorema del principio 0-1
- Rete di ordinamento bitonico, sequenza bitoniche, half-cleaner, teorema di Brent
- Sommatoria, somme prefisse, ordinamento su PRAM EREW



Sul sito del corso sono in pubblicazione le slide usate a lezione.

__________________
The man in black fled across the desert and the gunslinger followed.

Lezione del 15-03-05

Argomenti trattati nella lezione di oggi:

- Valutazione di polinomi su PRAM EREW con n processori
- Tecnica del salto del puntatore
- Tecnica del ciclo euleriano
- Algoritmi per reti di interconnessione: algoritmi di ordinamento con vettore lineare, sommatoria e massimo su mesh e ipercubo

__________________
The man in black fled across the desert and the gunslinger followed.

Lezione del 18-03-05

Argomenti trattati nella lezione di oggi:

- Sommatoria su shuffle
- Cube-Connected-Cycles, modello parallelo universale
- Algoritmi concorrenti: primitive di lock/unlock, problemi di dealock, esempi
- Algoritmi distribuiti: modello di calcolo, misura di complessità, topologie di rete

__________________
The man in black fled across the desert and the gunslinger followed.

Lezione del 22-03-05

Argomenti trattati nella lezione di oggi:

- Algoritmi distribuiti: eventi, tecnica del timestamping, mutua esclusione (tecnica del token, algoritmo di Lamport, algoritmo di Ricart-Agrawale), elezione del leader (algoritmo di Chang-Roberts)
- Algoritmi non deterministici: il non determinismo, esempi, misura di complessità

Avviso: La prossima lezione del corso di terrà martedì 5 Aprile.

__________________
The man in black fled across the desert and the gunslinger followed.

Lezione del 05-04-05

Argomenti trattati nella lezione di oggi:

- Simulazione di algoritmi non deterministici tramite algoritmi deterministici
- Ottimizzazione combinatoria, branch and bound

__________________
The man in black fled across the desert and the gunslinger followed.

Lezione del 08-04-05

Argoment trattati nella lezione di oggi:

- Branch & bound: bounding, rilassamenti; rilassamento per problemi di zaino, rilassamento per TSP; branch and bound per TSP simmetrico
- Algoritmi probabilistici; test di primalità

__________________
The man in black fled across the desert and the gunslinger followed.

Lezione del 12-04-05

Argomenti trattati nella lezione di oggi:

- Algoritmi probabilistici: commutatività di matrici, algoritmi con errori ai due lati
- Teoria della complessità: concetti principali, classe P e classe NP

__________________
The man in black fled across the desert and the gunslinger followed.

Lezione del 15-04-05

Argomenti trattati nella lezione di oggi:

- Teoria della complessità: riduzioni polinomiali, problemi Np-Completi; classi di complessità per algoritmi probabilistici e algoritmi paralleli

-----------------

Con questa lezione si chiude il primo modulo del corso. La prossima settimana ci sarà una pausa. La prossima lezione del corso sarà quindi Martedì 26 Aprile.

Chi volesse sostenere l'esame del primo modulo dovrà preparare l'orale sulle dispense scaricabili dal sito del corso.

__________________
The man in black fled across the desert and the gunslinger followed.

Lezione del 26-04-05

Argomenti trattati nella lezione di oggi:

- Il problema del perfect matching
- Algoritmi approssimati: algoritmi greedy, nearest neighbourhood e nearest insertion per TSP, euristiche con garanzia di approssimazione

__________________
The man in black fled across the desert and the gunslinger followed.

Lezione del 29-04-05

Argomenti trattati nella lezione di oggi:

- Perfect matching, pfaffiano
- Schemi di approssimazione

__________________
The man in black fled across the desert and the gunslinger followed.

Lezione del 03-05-05

Argomenti trattati nella lezione di oggi:

- Polinomi e Fast Fourier Transform

__________________
The man in black fled across the desert and the gunslinger followed.