FONDAMENTI DI INFORMATICA 1B
(Diploma Universitario)

OBIETTIVI E ORGANIZZAZIONE DEL CORSO

Obiettivo del corso e' approfondire le conoscenze del linguaggio C attraverso il suo utilizzo nella progettazione di strutture dati e algoritmi fondamentali nonché introdurre alcuni concetti di base relativi ai sistemi operativi e alle reti di calcolatori. Propedeutici allo studio di algoritmi e di strutture dati sono lo studio della ricorsione, di alcuni meccanismi di astrazione tipici della programmazione ad oggetti (in particolare, incapsulamento e informating hiding) e delle classiche notazioni e modelli di computazione per l'analisi di efficienza di algoritmi e problemi. Le strutture dati analizzate sono liste, code, pile e code di priorità, descritti in maniera astratta nonostante le limitazioni del linguaggio C; gli algoritmi fondamentali studiati comprendono varie tecniche di ordinamento e di ricerca veloce. Per quanto riguarda i sistemi operativi, sono illustrate le funzionalità di massima con particolare riferimento alla gestione dei processi e della memoria; inoltre vengono presentate alcune nozioni di base di sistemi operativi di rete nonché di varie architettuire di reti e dei servizi disponibili.

Il corso comprende circa 30 ore di lezioni e 20 di esercitazioni più varie sedute di laboratorio assistite.
 

CONTENUTI DEL CORSO

1. Approfondimento del linguaggio C

Puntatori e vettori, file. Realizzazione di liste con puntatori.
 
2. Ricorsione

Confronto tra ricorsione e iterazione. Esempi di programmi ricorsivi. La ricorsione in C: record di attivazione per ogni funzione e gestione dei record di attivazione durante l'esecuzione di un programma.
 
3. Complessità di problemi e algoritmi

Complessità temporale e spaziale, casi peggiore, migliore e medio, misure di complessità di algoritmi e problemi, la notazione 'teta'.
 
4. Algoritmi di ordinamento e di ricerca

Algoritmi quadratici (selezione, inserimento, a bolle) e algoritmi veloci (quicksort, mergesort) di ordinamento di vettori. Ricerca di un elemento di un vettore ordinato e non, ricerca binaria e ricerca uniforme.
 
5. Strutture dati

Pile, Code, Code di priorità: definizioni e vari tipi di realizzazione secondo i meccanismi di astrazione della programmazione ad oggetti (incapsulamento, information hiding, genmeralizzazione).
 
6. Elementi di Sistemi operativi

Struttura e funzioni di un sistema operativo, gestione dei processi e meccanismi di comunicazione e sincronizzazione (semafori), gestione della memoria (rilocazione, paginazione), gestione dei file. Presentazione del sistema operativo MiniUnix.
 
7. Reti di calcolatori

Cenni sui sistemi operativi di rete. Presentazione delle architetture di rete ISO/OSI e TCP/IP. Mezzi trasmissivi, codifica dei dati e topologie di collegamento: commutazione di pacchetto, circuito, cella. Tipologie delle reti locali (Ethernet, Token Ring e FDDI) e delle reti geografiche (MAN, WAN, vari tipi di collegamento dei nodi: linee commutate, dedicate, ISND, Frame Relay e ATM). Servizi INTERNET: posta elettronica, file transfer, terminale virtuale, WEB e conunicazione fra utenti.

Programmi in C. Sviluppo di un interprete di una macchina con memoria a stack (per la gestione della ricorsione) e del relativo assemblatore.
 

ESAME

L'esame consiste di una prova pratica di circa 60 minuti (scrittura e compilazione di un programma in C) ed una prova orale sui vari argomenti del corso.
 
 
 

ORARIO DEL CORSO

LIBRI DI TESTO

1. S. Ceri, D. Mandrioli, L. Sbattella, Informatica Istituzioni, linguaggio di riferimento ansi C, McGraw-Hill, 1994.
   
   
2. P. Tosoratti, Introduzione all'Informatica, Casa Editrice Ambrosiana, 1998.