Gabriele D'Angelo, PhD, ricercatore. Universita` di Bologna.   [For every complex problem, there is an answer that is short, simple and wrong] H. L. Mencken
english version        home       
 
contatti | università | pubblicazioni | attività | didattica | tesi
Ultimo aggiornamento:  16 Febbraio, 2007      
[ 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)



Altre edizioni del corso
Le pagine delle altre edizioni del corso (se disponibili) si trovano in questa pagina.
Orario di ricevimento
Su appuntamento, da concordare via e-mail.
Appelli
Lista completa dei prossimi appelli d'esame.
Screencast
Servizio di screencast delle lezioni.


empty spacer
1975 - 2020 Gd'A
Contattami! | Avviso