CORSO DI SISTEMI PER LA ELABORAZIONE DELLA INFORMAZIONE I (EDIZIONE SERALE)
Corso di laurea in Informatica
Università degli Studi di Milano
Ho tenuto questo corso a partire dal 1983 fino al 1995. Questo è il programma delle ultime edizioni.
PROGRAMMA
Parte I: Il sistema Unix
I.1 Generalità sul sistema Unix
Questa parte del Corso ha l’obbiettivo di fornire una conoscenza generale della filosofia, delle funzioni e della architettura del sistema operativo Unix. I principali argomenti di questa parte sono:
- Caratteristiche generali del sistema Unix
- File system: struttura logica e struttura fisica
- Primitive di input/output
- Gestione dei processi
- Primitive per il controllo dei processi
- La shell
Più in particolare, il programma di questa parte del corso è costituita dall’intero contenuto del testo di Le Van Huu (rif.[2], vedi più oltre).
I.2 Principali comandi del sistema Unix
Oltre a quanto sopra, lo studente dovrà acquisire una conoscenza teorica e pratica dei principali comandi Unix, e delle caratteristiche principali di un linguaggio di shell (sh, csh, o altro, a scelta dello studente).
In particolare, lo studente dovrà essere in grado di usare correttamente almeno i seguenti comandi:
- cat, cc, cd, chmod, cmp, cp, date, diff, du, echo, kill, ln, lp, ls, mail, man, mkdir, mv, passwd, pg, ps, pwd, rm, rmdir, sh (o csh), sleep, sort, test, time, touch, uniq, wc, who.
Per questa parte del programma, lo studente potrà fare riferimento direttamente al manuale di Unix, o a uno dei tanti libri di introduzione a Unix disponibili. Inoltre, per acquisire la necessaria esperienza pratica, ogni studente dovrà esercitarsi liberamente sull’uso di tutti i comandi indicati, presso i sistemi Unix disponibili nel Laboratorio del Dipartimento. Per le slides, si veda il corso di Sistemi Operativi (modulo Unix), su questo sito.
Parte II: Algoritmi e strutture dati
Questa parte ha l’obbiettivo di fornire un inquadramento teorico e pratico delle principali strutture di dati e di alcuni dei principali algoritmi che si incontrano nella pratica della programmazione.
Particolare enfasi viene data all’analisi delle prestazioni degli algoritmi studiati.
Questa parte del corso costituisce il logico approfondimento di quanto sviluppato nel Corso di Teoria e Applicazione delle Macchine Calcolatrici, che ne costituisce l’indispensabile prerequisito.
I principali argomenti di questa parte del programma sono:
- Strutture dati elementari: array, liste, stack, code; tipi di dati astratti
- Alberi, alberi binari; visita di alberi binari
- Ricorsione; rimozione della ricorsione
- Analisi degli algoritmi
- Algoritmi elementari di ordinamento: selezione, inserzione, bubble sort, shell sort
- Quicksort
- Code con priorità; heapsort
- Algoritmi elementari di ricerca: ricerca sequenziale e binaria; ricerca con alberi di ricerca
- Ricerca con alberi bilanciati: alberi 2-3-4, alberi rosso-neri
- Ricerca con techniche hash: separate chaining, linear probing, double hashing
- Ricerca esterna: indexed-sequential access methods; B-alberi
Facendo riferimento al testo di Sedgewick (rif.[3]), il programma di questa parte del corso è costituita dal contenuto dei primi 21 capitoli, con esclusione dei capitoli 10, 12, 17.
L’ESAME
Generalità
L’esame si compone di due parti:
- Visione del progetto di esame. Il programma realizzato dovrà essere dimostrato al calcolatore. Dovrà essere inoltre mostrata la relativa documentazione.
- Esame orale. L’esame orale viene effettuato dopo la visione del progetto di esame, normalmente nello stesso giorno.
Il progetto d’esame
Il progetto di esame ha lo scopo di permettere agli studenti di effettuare una esperienza completa di progettazione di un sistema di software applicativo di dimensioni non banali. Ogni progetto di esame può essere realizzato singolarmente, o da gruppi di lavoro composti da due o tre studenti. In questo caso, ogni studente dovrà discutere con gli altri studenti del gruppo la impostazione generale del progetto, e curarne personalmente la realizzazione di una parte. Il lavoro di gruppo è fortemente incentivato; pertanto i temi proposti per l’esame sono dimensionati per essere più agevolmente realizzabili da gruppi di tre studenti.
I testi dei progetti di esame vengono distribuiti a cadenza fissa, secondo un calendario fissato con largo anticipo per permettere agli studenti di pianificare meglio le proprie attività. I testi dei progetti sono comuni ai tre corsi di Sistemi I. Ogni progetto dovrà essere presentato all’esame entro i termini indicati sul tema del progetto (normalmento, un anno e mezzo dalla data di distribuzione del testo). Dopo questo periodo, il tema si considera scaduto, e non può essere più utilizzato per l’esame.
Ogni singolo progetto viene seguito da un docente (indicato come “Docente Responsabile”), al quale gli studenti possono far riferimento per eventuali problemi e chiarimenti durante la realizzazione. Ogni tema di esame viene illustrato agli studenti dal Docente Responsabile in un incontro che viene fissato qualche giorno dopo la distribuzione del testo.
Il progetto di esame può essere realizzato presso i sistemi Unix del Laboratorio Didattico di via Comelico 39. In alternativa, gli studenti che lo desiderano potranno realizzare il progetto su proprio personal computer (con sistema operativo Unix o Windows).
Si tenga presente che, poichè al momento dell’esame il progetto realizzato dovrà essere dimostrato al calcolatore, il sistema necessario dovrà essere trasportato (se non già disponibile) presso la sede dell’esame, in Aula V10 in via Venezian, a cura dello studente.
Per i progetti di esame possono essere utilizzati i linguaggi C, C++ o Java.
Al momento dell’esame, il progetto deve essere dimostrato al calcolatore. Alla dimostrazione è richiesta la presenza dell’intero gruppo di lavoro: ogni studente del gruppo presenterà personalmente la parte da lui realizzata.
All’esame dovrà essere inoltre presentato il listato del codice realizzato, e un documento composto di due parti:
- un sintetico manuale d’uso del sistema realizzato
- una sintetica descrizione della sua architettura (principali strutture dati, principali componenti software, eventuali algoritmi particolari utilizzati).
A seguito della dimostrazione in sede di esame, il docente compila una scheda di valutazione del progetto, che viene consegnata agli studenti.
Tale scheda riporta una valutazione complessiva del progetto, che si basa sui seguenti aspetti:
- interfaccia utente: facilità d’uso e qualità complessiva dell’interfaccia utente.
- funzionalità: completezza e coerenza delle funzioni realizzate, in relazione agli obbiettivi posti nel testo di descrizione del progetto, e a quanto discusso nell’incontro con il Docente Responsabile.
- Architettura: adeguatezza della struttura interna del sistema realizzato (strutture dati, algoritmi particolari, decomposizione in componenti, …), in relazione ai requisiti posti.
- Prestazioni: efficienza complessiva del sistema risultante, in termini d tempi di calcolo e di risposta.
- Documentazione: qualità e completezza della documentazione presentata. Il giudizio potrà tenere conto anche della qualità del codice sorgente.
Nella valutazione complessiva del progetto si terrà conto, ovviamente, anche della numerosità del gruppo di lavoro che lo ha realizzato.
E’ possibile presentare, come progetto di esame, un progetto di propria scelta. In questo caso non esistono scadenze temporali. Il tema del progetto deve in ogni caso essere preventivamente approvato.
LIBRI DI TESTO
I libri di testo adottati sono i seguenti:
| [1] | Brian W.Kernighan, Dennis M.Ritchie “The C Programming Language – Second Edition” Edizione americana: Prentice-Hall, 1988 |
| Questo libro è il riferimento principale utilizzato nel corso per il linguaggio C. Il libro è il riferimento classico per il linguaggio C, scritto dall’autore del linguaggio. E’ un libro compatto, ricco di esempi ma di non facile lettura. Si noti che questo libro descrive il C Standard ISO/ANSI: è in circolazione una versione precedente del libro, senza la dicitura “Second Edition” nel titolo, che descrive il linguaggio nella versione precedente allo Standard ANSI, e che quindi non va utilizzato. La traduzione italiana è stata pubblicata dal Gruppo Editoriale Jackson nel 1989, con il titolo “Linguaggio C – Seconda Edizione”. |
|
| [2] | Le Van Huu, “Introduzione alla struttura interna di Unix” Editore: Unicopli, 1990 |
| Questo libro, scritto appositamente per questo Corso, è il riferimento principale per la parte del corso che riguarda le Generalità sul sistema Unix (Parte I.1). Il libro non contiene, invece, la descrizione dei comandi Unix (Parte I.2). Per questa parte, lo studente potrà riferirsi ai manuali Unix o a uno dei molti libri disponibili sul mercato. |
|
| [3] | Robert Sedgewick “Algorithms in C” Edizione americana: Addison-Wesley, 1990 |
| Questo libro è il riferimento principale per la parte del corso che riguarda Algoritmi e strutture dati (Parte II). Ne esiste una versione italiana. | |
Libri consigliati per approfondire:
| [4] | Maurice J.Bach “The Design of the Unix Operating System” Edizione americana: Prentice-Hall, 1986 |
| E’ il riferimento classico sulla struttura interna del sistema Unix. E’ un libro molto ampio e completo, che è meglio consultare dopo avere già acquisito i concetti generali sull’architettura di Unix, per un approfondimento. Il libro è stato tradotto in italiano dal Gruppo Editoriale Jackson, con il titolo: “Unix – Architettura di sistema” | |
| [5] | N.Wirth “Algoritmi + Strutture Dati = Programmi” Edizione italiana: Tecniche Nuove, 1987 |
| E’ un libro classico sugli algoritmi e sulle strutture di dati, scritto nel 1976. Il libro, che utilizza il Pascal per gli esempi di programmi, è ancora oggi molto valido, e può essere consultato con profitto per la preparazione di alcuni argomenti che in [1] sono trattati in modo eccessivamente succinto, ad esempio: B-Alberi. | |
