|
[
Sicurezza delle Reti |
Programmazione di Reti |
Appelli
]
Per l'anno accademico 2005/2006 sono stato assistente alla didattica del Prof.
Alan Bertossi
per il corso di
Algoritmi e Strutture Dati A-L (Informatica).
Note e comunicazioni varie:
-
NON sono più assistente di Algoritmi e Strutture dati: siete pregati di rivolgervi al nuovo assistente, il Dr.
Marco Vassura.
Esercitazioni svolte o da svolgere:
- Martedì 1 Febbraio 2006
- introduzione alle esercitazioni;
- introduzione al linguaggio Pascal;
- esempi di programmazione Pascal;
- Risorse utili:
- Mercoledì 22 Febbraio 2006
- tipi enumerativi, record;
- strumenti di sviluppo;
- puntatori;
- errori tipici nell'uso dei puntatori.
- Giovedì 23 Febbraio 2006: ANNULLATA.
- Giovedì 2 Marzo 2006
- vari metodi di soluzione di un esercizio sulle liste, utilizzando puntatori;
- Risorse utili:
- Giovedì 9 Marzo 2006
- operatori su liste (del libro di testo): implementazione con puntatori;
- risoluzione con operatori dell'esercizio della lezione precedente;
- esercizi d'esame sulle liste: es 2 del 19 febbraio 2003, es 3 del 13 gennaio 2004.
- Giovedì 16 Marzo 2006
- esercizi sugli alberi binari, implementazione con puntatori e con operatori;
- visite di alberi binari;
- implementazione di visite per mezzo di una pila.
- Risorse utili:
- Giovedì 30 Marzo 2006
- insiemi, es. 5.5 pag 92 (differenza simmetrica);
- dizionari, tabelle hash;
- scansione interna: es 3 esame del 14 luglio 2003;
- scansione esterna: es 5 esame del 14 liugno 2005;
- ottimizzazione di scansione esterna, es 6.6 pag 109;
- alberi binari, es 5 esame del 13 gennaio 2004.
- Risorse utili:
- Giovedì 6 Aprile 2006
- grafi, orientati e non orientati;
- specifica e varie implementazioni, vettori di adiacenza;
- esplorazione di grafi (visite): DFS, BFS;
- es 4 esame del 19 febbraio 2003 (DFS);
- es 4 esame del 13 gennaio 2004 (DFS);
- es 4 esame del 14 gennaio 2003 (BDS);
- struttura dati heap: esercizio 3 esame del 12 luglio 2005;
- operazione di invecchiamento su heap;
- alberi binari di ricerca, alberi bilanciati.
- Mercoledì 17 Novembre 2004
- ordine di grandezza della complessità
- esercizio 1, esame del 19 febbraio 2003;
- esercizio 1, esame del 16 giugno 2003;
- esercizio 1, esame del 14 luglio 2003;
- esercizio 1, esame del 14 gennaio 2003;
- esercizio 1, esame del 21 settembre 2004;
- esercizio 1, esame del 1 giugno 2004;
- esercizio 1, esame del 13 gennaio 2004.
- Mercoledì 26 Aprile 2006
- greedy: zaino reale e 0-1 (es. 13.1 e 13.2 a pag. 207-208);
- costo computazione dell'ordinamento basato su confronti, albero di decisione (pag. 72-73);
- counting-sort (es. 13.2 pag. 182);
- radix-sort;
- Giovedì 11 Maggio 2006
- Tecniche di progetto:
- Divide et impera (es. merge-sort, quick-sort, ricerca dicotomica);
- Backtrack (es. DFS, visita anticipata su alberi);
- Greedy (es. zaino reale, codici di Huffman);
- Programmazione dinamica (es. string matching approssimato);
- Ricerca locale (es. minimo albero di copertura).
- Ulteriori problemi interessanti:
- Stringhe con duplicati;
- Compressione: codici di Huffman.
- Giovedì 18 Maggio 2006
- Non determinismo:
- es. 6, esame del 13 gennaio 2004;
- es. 6, esame del 14 gennaio 2003.
- Macchine di Turing: es. 6, esame del 14 luglio 2003.
- Giovedì 25 Maggio 2006 ANNULLATA.
Testo di riferimento:
- Alan Bertossi. Algoritmi e Strutture di Dati. UTET-Libreria, Torino, 2000, 495 pp. ISBN 88-7750-611-3
Testi di esami e bozze di soluzioni (dal corso di Scienze di Internet e Informatica):
Frequently Asked Questions:
-
Posso passare dal corso A-L a quello M-Z (o viceversa)?
È necessario chiedere direttamente al docente.
-
Ci sono altre soluzioni disponibili dei vecchi appelli?
NO!
-
È necessario iscriversi all'esame?
No, è sufficiente presentarsi in aula.
-
Uso il Pascal sotto Windows, quando eseguo un programma la
finestra si chiude immediatamente dopo la fine e non faccio in tempo a
leggere l'output.
È sufficiente aggiungere un read() come ultima istruzione prima
della fine. In questo modo il programma rimane in attesa di un input
da tastiera.
-
Da dove scarico il Turbo Pascal?
Consiglio di usare il Free
Pascal, comunque Borland ha rilasciato gratis alcune versioni di vecchi
compilatori che sono scaricabili a partire dalla URL:
http://community.borland.com/museum/
-
C'è il Free Pascal Compiler (FPC) in Ubuntu Breezy?
No, ma c'è il Gnu Pascal Compiler (GPC). Un'altra soluzione è quella di utilizzare i pacchetti di FPC
per Debian testing,
(ho provato con la versione 2.0.0-4).
-
Modalità d'esame (prova scritta):
- Tempo disponibile 180 minuti (è ammesso ritirarsi entro 90 minuti)
- Sono ammessi al più 3 scritti consegnati per A.A.
- Non è possibile consultare appunti, libri o persone né uscire dall'aula
- Nella valutazione dello scritto ogni esercizio conta 6 punti (e quindi si
raggiunge 18 con 3 esercizi risolti correttamente e 30 con 5 esercizi risolti
correttamente)
- Le soluzioni degli esercizi devono:
- Spiegare a parole l'algoritmo usato (anche con eventuali disegni)
- Commentare l'eventuale procedura Pascal (dettagliando il significato delle variabili)
- Giustificare la correttezza di tutti i passaggi matematici
- Dimostrare la complessità (con equazioni di ricorrenza se necessario)
|
|
|
|
|
