|
Per l'anno accademico 2007/2008 sono assistente alla
didattica del Prof.
Alan
Bertossi
per il corso di
Algoritmi e Strutture Dati A-L (Informatica).
Esercitazioni svolte o da
svolgere:
- introduzione alle esercitazioni;
- introduzione al linguaggio Pascal;
- esempi semplici di programmazione Pascal;
- strumenti di sviluppo;
- complessita' ed esempi di programmazione: esercizi I.9 I.10 I.11
I.12 del libro di testo
- tipi enumerativi, record;
- puntatori;
- errori tipici nell'uso dei puntatori.
- Risorse utili:
- vari metodi di soluzione di un esercizio sulle liste, utilizzando
puntatori;
- Risorse utili:
- operatori su liste (del libro di testo): definizione e uso
- risoluzione con operatori dell'esercizio precedente
- esercizi d'esame sulle liste: es 2 del 19 febbraio 2003, es 3 del
13 gennaio 2004 e del 14 gennaio 2003.
- esercizi sugli alberi binari, implementazione con puntatori e con
operatori;
- visite di alberi binari;
- implementazione di visite per mezzo di una pila.
- Risorse utili:
- 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 giugno 2005;
- ottimizzazione scansione esterna, es. 6.6 pag 109
- ricerca binaria, es. 2 del 13 gennaio 2004
- alberi binari, es 5 esame del 13 gennaio 2004.
- Risorse utili:
- 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 (BFS);
- es 9.11 pag. 152 (cammini minimi in grafo non pesato)
- ordine di grandezza della complessitla'
- 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.
- Tecniche di progetto:
- Divide et impera (es. merge-sort, quick-sort, ricerca dicotomica);
- Backtrack (es. DFS, visita anticipata su alberi);
- Greedy (es. zaino reale e 0-1 (es. 13.1 e 13.2 a pag. 207-208));
- Programmazione dinamica (es. string matching approssimato);
- Ricerca locale (es. minimo albero di copertura).
- Non determinismo:
- es. 6, esame del 13 gennaio 2004;
- es. 6, esame del 14 gennaio 2003.
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, svolti dal Prof. Alan Bertossi):
Frequently Asked Questions:
-
Posso passare dal corso A-L a quello M-Z (o viceversa)?
E' necessario chiedere direttamente al docente.
-
Ci sono altre soluzioni disponibili dei vecchi appelli?
NO!
-
E' necessario iscriversi all'esame?
No, e' 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/
Si possono anche utilizzare i pacchetti di FPC
per Debian testing,
(ho provato con la versione 2.0.0-4).
-
Modalita' d'esame (prova scritta):
- Tempo disponibile 180 minuti (e' ammesso ritirarsi entro 90 minuti)
- Sono ammessi al massimo 3 scritti consegnati per A.A.
- Non possibile consultare appunti, libri o persone, ne' uscire dall'aula
- 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 complessita' (con equazioni di ricorrenza se necessario)
|
|
|
|
|
|
|
|
Prossimo
ricevimento
Su appuntamento, da concordare via e-mail.
home
Ultimo aggiornamento: 28 Febbraio,
2008 |
|
|
|
|
|