|
|
|
|
| |
|
Bulma |
[Algoritmi II] Diario del Corso 04/05 |
01-03-2005 17:50 |
|
|
Bulma |
.grande:maestro.
Registered: Jun 2002
Posts: 1706 (0.21 al dì)
Location: Rondinera City
Corso: Specialistica in Informatica
Anno: Dott. Mag.
Time Online: 72 Days, 20:00:05: [...]
Status: Offline
Edit | Report | IP: Logged |
[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.
|
01-03-2005 17:50 |
|
|
| |
|
Bulma |
Lezione del 01-03-05 |
01-03-2005 17:53 |
|
|
Bulma |
.grande:maestro.
Registered: Jun 2002
Posts: 1706 (0.21 al dì)
Location: Rondinera City
Corso: Specialistica in Informatica
Anno: Dott. Mag.
Time Online: 72 Days, 20:00:05: [...]
Status: Offline
Edit | Report | IP: Logged |
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.
|
01-03-2005 17:53 |
|
|
| |
|
Bulma |
Lezione del 04-03-05 |
05-03-2005 14:53 |
|
|
Bulma |
.grande:maestro.
Registered: Jun 2002
Posts: 1706 (0.21 al dì)
Location: Rondinera City
Corso: Specialistica in Informatica
Anno: Dott. Mag.
Time Online: 72 Days, 20:00:05: [...]
Status: Offline
Edit | Report | IP: Logged |
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.
|
05-03-2005 14:53 |
|
|
| |
|
Bulma |
Lezione del 08-03-05 |
08-03-2005 17:22 |
|
|
Bulma |
.grande:maestro.
Registered: Jun 2002
Posts: 1706 (0.21 al dì)
Location: Rondinera City
Corso: Specialistica in Informatica
Anno: Dott. Mag.
Time Online: 72 Days, 20:00:05: [...]
Status: Offline
Edit | Report | IP: Logged |
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.
|
08-03-2005 17:22 |
|
|
| |
|
Bulma |
Lezione del 11-03-05 |
13-03-2005 15:10 |
|
|
Bulma |
.grande:maestro.
Registered: Jun 2002
Posts: 1706 (0.21 al dì)
Location: Rondinera City
Corso: Specialistica in Informatica
Anno: Dott. Mag.
Time Online: 72 Days, 20:00:05: [...]
Status: Offline
Edit | Report | IP: Logged |
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.
|
13-03-2005 15:10 |
|
|
| |
|
Bulma |
Lezione del 15-03-05 |
15-03-2005 17:14 |
|
|
Bulma |
.grande:maestro.
Registered: Jun 2002
Posts: 1706 (0.21 al dì)
Location: Rondinera City
Corso: Specialistica in Informatica
Anno: Dott. Mag.
Time Online: 72 Days, 20:00:05: [...]
Status: Offline
Edit | Report | IP: Logged |
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.
|
15-03-2005 17:14 |
|
|
| |
|
Bulma |
Lezione del 18-03-05 |
19-03-2005 19:45 |
|
|
Bulma |
.grande:maestro.
Registered: Jun 2002
Posts: 1706 (0.21 al dì)
Location: Rondinera City
Corso: Specialistica in Informatica
Anno: Dott. Mag.
Time Online: 72 Days, 20:00:05: [...]
Status: Offline
Edit | Report | IP: Logged |
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.
|
19-03-2005 19:45 |
|
|
| |
|
Bulma |
Lezione del 22-03-05 |
22-03-2005 16:32 |
|
|
Bulma |
.grande:maestro.
Registered: Jun 2002
Posts: 1706 (0.21 al dì)
Location: Rondinera City
Corso: Specialistica in Informatica
Anno: Dott. Mag.
Time Online: 72 Days, 20:00:05: [...]
Status: Offline
Edit | Report | IP: Logged |
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.
|
22-03-2005 16:32 |
|
|
| |
|
Bulma |
Lezione del 05-04-05 |
05-04-2005 17:04 |
|
|
Bulma |
.grande:maestro.
Registered: Jun 2002
Posts: 1706 (0.21 al dì)
Location: Rondinera City
Corso: Specialistica in Informatica
Anno: Dott. Mag.
Time Online: 72 Days, 20:00:05: [...]
Status: Offline
Edit | Report | IP: Logged |
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.
|
05-04-2005 17:04 |
|
|
| |
|
Bulma |
Lezione del 08-04-05 |
09-04-2005 15:21 |
|
|
Bulma |
.grande:maestro.
Registered: Jun 2002
Posts: 1706 (0.21 al dì)
Location: Rondinera City
Corso: Specialistica in Informatica
Anno: Dott. Mag.
Time Online: 72 Days, 20:00:05: [...]
Status: Offline
Edit | Report | IP: Logged |
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.
|
09-04-2005 15:21 |
|
|
| |
|
Bulma |
Lezione del 12-04-05 |
12-04-2005 16:49 |
|
|
Bulma |
.grande:maestro.
Registered: Jun 2002
Posts: 1706 (0.21 al dì)
Location: Rondinera City
Corso: Specialistica in Informatica
Anno: Dott. Mag.
Time Online: 72 Days, 20:00:05: [...]
Status: Offline
Edit | Report | IP: Logged |
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.
|
12-04-2005 16:49 |
|
|
| |
|
Bulma |
Lezione del 15-04-05 |
16-04-2005 13:02 |
|
|
Bulma |
.grande:maestro.
Registered: Jun 2002
Posts: 1706 (0.21 al dì)
Location: Rondinera City
Corso: Specialistica in Informatica
Anno: Dott. Mag.
Time Online: 72 Days, 20:00:05: [...]
Status: Offline
Edit | Report | IP: Logged |
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.
|
16-04-2005 13:02 |
|
|
| |
|
Bulma |
Lezione del 26-04-05 |
26-04-2005 15:59 |
|
|
Bulma |
.grande:maestro.
Registered: Jun 2002
Posts: 1706 (0.21 al dì)
Location: Rondinera City
Corso: Specialistica in Informatica
Anno: Dott. Mag.
Time Online: 72 Days, 20:00:05: [...]
Status: Offline
Edit | Report | IP: Logged |
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.
|
26-04-2005 15:59 |
|
|
| |
|
Bulma |
Lezione del 29-04-05 |
02-05-2005 12:43 |
|
|
Bulma |
.grande:maestro.
Registered: Jun 2002
Posts: 1706 (0.21 al dì)
Location: Rondinera City
Corso: Specialistica in Informatica
Anno: Dott. Mag.
Time Online: 72 Days, 20:00:05: [...]
Status: Offline
Edit | Report | IP: Logged |
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.
|
02-05-2005 12:43 |
|
|
| |
|
Bulma |
Lezione del 03-05-05 |
10-05-2005 17:32 |
|
|
Bulma |
.grande:maestro.
Registered: Jun 2002
Posts: 1706 (0.21 al dì)
Location: Rondinera City
Corso: Specialistica in Informatica
Anno: Dott. Mag.
Time Online: 72 Days, 20:00:05: [...]
Status: Offline
Edit | Report | IP: Logged |
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.
|
10-05-2005 17:32 |
|
|
| |
|
All times are GMT. The time now is 04:10. |
|
|
|
|
|
|
|
| |
Forum Rules:
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
|
HTML code is OFF
vB code is ON
Smilies are ON
[IMG] code is ON
|
|
|
|
|
|