Corso di Sistemi per l'elaborazione dell'informazione I  

per il Corso di Laurea in Scienze dell'Informazione

 

Indicazioni per il progetto

L'obiettivo del progetto è quello di apprendere un secondo linguaggio di programmazione oltre al Pascal, un linguaggio più legato alla realtà concreta di lavoro e ai sistemi operativi. Quindi vanno bene C, C++ (Visual e no), objective C (ora defunto?), Java, C#.

Il progetto viene presentato in esecuzione (tipicamente su un portatile dello studente, oppure eseguito sulla macchina del docente, se ha un eseguibile sufficientemente standard) e accompagnato da una relazione (stendere una buona relazione è un utile esercizio in vista della tesi).

La valutazione del progetto viene fatta in data da concordare (via telefono o email), meglio se insieme con l'esame orale.

Il progetto può essere concordato con lo studente, sulla base di una breve presentazione scritta delle specifiche e dei motivi di interesse del progetto stesso, oppure può essere uno degli ultimi progetti presentati ufficialmente, le cui specifiche sono reperibili in forma cartacea presso il SILab (il Laboratorio di via Comelico, più precisamente al cosiddetto Acquario = stanza a vetri, dove vengono distribuite le password) o scaricate ai seguenti link:

·              progetto Othello

·              progetto Hilbert

Indicazioni per l'esame orale

Mi rammarico di dover suggerire per prima cosa di ripassare logaritmi e potenze, ma molti studenti non sanno calcolare approssimativamente log21.000.000: questo serve per esempio per stabilire quanti bit occorrono per indirizzare 1MB, e bisogna saperlo fare! Partire da 210 » 1000 = 103.

 

 1. Architettura di macchina

         • L'algoritmo di minimizzazione di Quine - Mc Cluskey

         • Reti combinatorie - reti sequenziali. Flip-flop. RAM e ROM

         • Struttura di un calcolatore    • Microprogrammazione   • I/O programmato, I/O da interruzione, DMA

Riferimento: F. Luccio, L. Pagli Reti logiche e calcolatore, Boringhieri, 1991 (seconda edizione: nella prima manca il capitolo finale sulle interruzioni e il DMA).

Obiettivo principale: arrivare a una piena comprensione del cap. 13, in particolare §13.2.

 

2. Strutture di dati e algoritmi

I primi 17 capitoli e i capitoli 29 e 42 del testo di R. Sedgewick  Algoritmi in C/C++, Addison-Wesley, 1993.

Si segnalano in particolare: tutti gli algoritmi di ordinamento e ricerca interni, di cui occorre conoscere la complessità in tempo e in memoria distinguendo i casi migliore, peggiore e medio (dimenticate le costanti e usate O grande!). Quali sono gli algoritmi migliori, in quali circostanze e per quale motivo? Non cercate di imparare a memoria i programmi, ma di capire gli algoritmi; un esempio: negli alberi 2-3-4, dove si fa l'inserimento, e come? Quali nodi si spezzano, e quando? Quanto sono bilanciati tali alberi? e i corrispondenti rosso-neri? Perché servono i legami rossi? Come si spezzano i nodi nella realizzazione rosso-nera?

 

3. Linguaggi e tecniche di analisi sintattica

         • Alfabeti, parole, linguaggi e grammatiche. Espressioni regolari

         • Grammatiche regolari e automi a stati finiti   

         • Grammatiche contestuali, libere e automi a pila

Obiettivi: abituarsi alla formalizzazione (che sembra dimenticata o non appresa dai corsi matematici). Esercizio: definire i vari tipi di grammatiche senza dire una parola, scrivendo solo espressioni simboliche.

Riferimenti. Consultare uno dei seguenti riferimenti, elencati in ordine dai più consigliati ai meno consigliati:

·              R.N.Moll, M.A.Arbib, A.J.Kfoury An Introduction to Formal Language Theory, capp. 1-3, Springer, 1988;

·              G.E.Révész Introduction to Formal Languages, Dover, 1991 (economico);

·              Linguaggi formali e compilatori, fotocopie per il corso omonimo (Prof. Sabadini — CLUED) del volume J. E. Hopcroft, J. D. Ullman Formal languages and their relation to automata, Addison-Wesley, 1969;

·              E.Damiani, O.D'Antona L'analisi sintattica dei linguaggi in Manuale di Informatica, cap. 10, Tecniche Nuove, 1989, o, degli stessi Autori, Ambienti esecutivi e di sviluppo dei linguaggi di programmazione, Addison-Wesley Masson, 1992, cap. 5 (attenzione: in quest'ultimo volume mancano le grammatiche contestuali!).