 | |
Il progetto dsy.it è l'unofficial support site dei corsi di laurea del Dipartimento di Scienze dell'Informazione e del Dipartimento di Informatica e Comunicazione della Statale di Milano. E' un servizio degli studenti per gli studenti, curato in modo no-profit da un gruppo di essi. I nostri servizi comprendono aree di discussione per ogni Corso di Laurea, un'area download per lo scambio file, una raccolta di link e un motore di ricerca, il supporto agli studenti lavoratori, il forum hosting per Professori e studenti, i blog, e molto altro...
In questa sezione è indicizzato in textonly il contenuto del nostro forum |
[Trubian] Diario del Corso 04/05
Clicca QUI per vedere il messaggio nel forum |
| Bulma |
"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++. |
| Bulma |
Argomenti trattati nella lezione di oggi:
- Heap binomiali e alberi binomiali: proprietà e funzioni |
| Bulma |
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 |
| Bulma |
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 |
| Bulma |
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. |
| Bulma |
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 |
| Bulma |
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 |
| Bulma |
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. |
| Bulma |
Argomenti trattati nella lezione di oggi:
- Simulazione di algoritmi non deterministici tramite algoritmi deterministici
- Ottimizzazione combinatoria, branch and bound |
| Bulma |
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à |
| Bulma |
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 |
| Bulma |
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. |
| Bulma |
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 |
| Bulma |
Argomenti trattati nella lezione di oggi:
- Perfect matching, pfaffiano
- Schemi di approssimazione |
| Bulma |
Argomenti trattati nella lezione di oggi:
- Polinomi e Fast Fourier Transform |
| Bulma |
Argomenti trattati nella lezione di oggi:
- Il problema Max-Sat
- Derandomizzazione
- Classi NPO, APX, PTAS |
| Bulma |
Argomenti trattati nella lezione di oggi:
- Algoritmi di ricerca locale |
| Bulma |
Argomenti trattati nella lezione di oggi:
- Simulated Annealing |
| Bulma |
Argomenti trattati nella lezione di oggi:
- GRASP
- Ant Systems
Avviso: a meno che lo sciopero dei trasporti pubblici non venga revocato, la lezione di venerdì 20 non si terrà. |
| Bulma |
Argomenti trattati nella lezione di oggi:
- Gli algoritmi genetici |
| Bulma |
Argomenti trattati nella lezione di oggi:
- Gli algoritmi genetici (continuazione)
- Le reti neurali |
| Bulma |
Argomenti trattati nella lezione di oggi:
- Reti neurali: le reti di Hopfield e le macchine di Boltzmann
- Tabu Search
---
Quella di oggi è stata l'ultima lezione del corso. :ciao: |
|
|
|
|
