Informatica di base - Teoria (2005/2006)

Obiettivi formativi

Il corso propone un syllabus di concetti dell’informatica in cui si ponga in primo piano l’aspetto scientifico di tale disciplina. Il corso parte da un’analisi della nozione di calcolo che, prendendo le mosse dalla usuale valutazione di espressioni algebriche, introduce la differenza tra calcoli simbolici e calcoli in cui i dati fluiscono da una memoria verso un agente e da questo verso una memoria.
In questa prospettiva si presentano gli algoritmi, gli automi, i programmi, i tipi e le strutture di dati, le caratteristiche fondamentali dell’informazione digitale, i linguaggi formali e le idee di base che sovrintendono l’organizzazione di sistemi di calcolo complessi (sistemi operativi e reti).

1. Operazioni e Algoritmi
Classi, Sequenze, Relazioni, Operazioni, Funzioni, Predicati.
Diagrammi operatori. Calcoli e Algoritmi.
Fonti: cap. 1 del libro di testo. Le pag. 23-24 (notazione polacca e postfissa) sono facoltative.

2. Espressioni e Comandi
Espressioni operatorie e calcoli di valutazione. Espressioni condizionali, lambda-espressioni. Comandi e costrutti di controllo.
Fonti: cap. 2 del libro di testo.

3. Istruzioni e Programmi
Spazi di dati. Calcolo simbolico e calcolo imperativo. Programmi, Macchine e Automi. Programmi a registri. Linguaggi procedurali ad alto livello.
Fonti: cap. 3 del libro di testo. Le pag. 46-47 (linguaggi procedurali) sono facoltative.

4. Circuiti e Macchine
Funzioni booleane e circuiti combinatori. Circuiti sequenziali. Circuiti di trasferimento e sincronizzazione. Struttura di una macchina von Neumann e ciclo di esecuzione.
Fonti: cap. 4 del libro di testo.

5. Dati e Tipi
Grafi e alberi. Stringhe, Vettori e Liste. Memorie indirizzabili e memorie sequenziali. File. Record e Puntatori.
Fonti: cap. 5 del libro di testo.

6. Simboli e Codici
Caratteristiche dell'informazione digitale. Misure informative. Codici e alberi di codifica. Codice ASCII e UNICODE. Codici istantanei.
Entropia informativa.
Fonti: cap. 6 del libro di testo. Parte della pag. 80 (Distanza di Hamming) e' facoltativa.

7. Automi e Linguaggi
Linguaggi e operazioni su linguaggi. Automi a stati finiti. Espressioni
regolari. Calcolabilita', semidecidibilita' e decidibilita'. Macchine di Turing, tesi di Church e indecidibilita'. Complessita' di calcolo.
Fonti: cap. 7 del libro di testo. Le pag. 91-92 (paragrafo 7.4) e le pag. 97-102 (paragrafo 7.6) sono facoltative.

8. Sistemi operativi (facoltativo)
Livelli di programmazione. Funzioni e struttura di un sistema operativo.
Nucleo di sistema. Struttura di un file system. Linguaggi di comandi.
Applicazioni di base. Interfacce grafiche.
Fonti: cap. 8 del libro di testo.

9. Reti e Servizi (facoltativo)
Livelli di rete. Risorse e Indirizzi. Servizi e Protocolli. Modello
Client-server (HTTP, SMTP). Testi, Formati, Ipertesti. Modalita' di accesso
e di uso dei servizi. Sistemi di autenticazione e di protezione.
Fonti: cap. 9 del libro di testo.

Prova scritta composta da 10 domande (due ore di tempo, testi e appunti non consultabili):

4 risoluzioni di esercizi (valutazione di espressioni con lamba e combinatori, programma a registri, automa e/o espressione regolare, macchina di Turing);

2 definizioni;

1 shell script;

3 domande su comandi Linux.