Informatica 1 per Matematica 2005/2006
Programma del Corso
- 19 Aprile 2006.
Introduzione al corso e ai
sussidi didattici.
Il concetto di Algoritmo.
Etimologia del nome e definizione informale.
I 10 punti caratterizzanti la nozione. Esempi
di algoritmi. Utilizzo del teorema di Cantor per
evidenziare limiti della nozione.
- 20 Aprile 2006.
Formalismi per la descrizione degli algoritmi.
La Macchina di Turing. Breve descrizione modellistica e esempi.
I Diagrammi di flusso.
Sintassi e semantica intutiva. Esempi di algoritmo: massimo tra
due numeri, sommatoria.
- 26 Aprile 2006.
Test di primalità.
Algoritmo naive
per il MCD e algoritmo di Euclide.
Rappresentazione
testuale dei diagrammi di flusso.Strutture while, if e repeat.
Simulazione delle ultime due mediante la prima.
Diagrammi strutturati e fortemente strutturati.
- 27 Aprile 2006.
Il Teorema di Böhm-Jacopini.
Esercizio: Lo scambio di variabili.
Linguaggi di Programmazione: Panoramica generale.
Compilazione ed Interpretazione.
- 2 Maggio 2006.
La Programmazione Imperativa in C.
Introduzione per esempi.
L'istruzione di assegnamento.
Commenti in C.
L'istruzione printf. Cenni sui formati.
Rappresentazione binaria di numeri interi.
Numeri segna segno (unsigned), in segno e modulo
ed in complemento a due.
- 3 Maggio 2006.
L'istruzione if-(then)-else.
Il ciclo while ed
il ciclo for.
L'istruzione scanf.
Idenitificatori e parole chiave.
- 4 maggio 2006.
Tipi di dati in C.
Interi.
Floating Point e Caratteri. La codifica ASCII.
Vettori.
- 9 Maggio 2005. (lab, con Dimitri Breda)
Stesura, compilazione, ed esecuzione di semplici programmi C.
Esercizi svolti:
- Si scriva un programma che accetta in input due valori
int
e stampa in output il massimo dei due.
- Si scriva un programma che accetta in input un numero e
stabilisca se esso sia o meno primo. Si provi con input "grandi"
- Si scriva un programma che accetta in input un vettore di
10 valori e stampa in output lo stesso vettore, la somma di tutti
i valori e la media.
- Si scoprano sperimentalmente
i valori ammissibili dei tipi primitivi.
- 10 Maggio 2006.
Matrici.
Tipi definiti dall'utente enum e struct.
Tipo puntatore.
Funzioni e Procedure. Generalità e Sintassi.
- 11 Maggio 2006.
Definizione ed Uso di funzioni.
Passaggio parametri. Esempi.
- 16 Maggio 2006. (lab)
Realizzazione di semplici programmi con funzioni:
- Procedura che accetta un vettore e che stampa un vettore.
- Funzione booleana che stabilisce se un numero e' primo.
- Funzione per il massimo comun divisore.
- Procedura che stampa una matrice quadrata di caratteri.
- Procedura che inizializza matrici in modo da stampare
alcune figure disegnate alla lavagna.
- 17 Maggio 2006.
Variabili locali
e globali. Esempi.
Definizioni ricorsive. Principi generali.
Definizione ricorsiva in C del Fattoriale e della
funzione di Fibonacci.
Cenni alla macchina astratta per la realizzazione
della ricorsione.
- 18 Maggio 2006.
Descrizione ricorsiva del problema
della torre di Hanoi e sua definizione in C.
Esercitazione (Funzioni di Aritmetica su Vettori di digits).
- 23 Maggio Maggio 2005. (lab)
Introduzione a MATLAB (1) (dispensa).
A cura del dr Dimitri Breda.
- 24 Maggio 2006.
Criteri di valutazione degli algoritmi:
comprensibilità, chiarezza, efficienza.
Misura del tempo di esecuzione: benchmarking e analisi.
Confronto tra complessità
lineare, n log n, quadratica e esponenziale.
Effetti dell'evoluzione dell'HW sulle varie
famiglie di algoritmi.
Limiti superiori al tempo d'esecuzione
lgoritmi. La notazione "O" grande.
Calcolo della complessità degli algoritmi:
assunzione di tempo costante per assegnamenti,
input/output, e test in assenza di chiamate di funzione.
- 25 Maggio 2006.
Tempo per istruzioni if-else, for, e while.
Calcolo della complessità di funzioni non ricorsive.
Esempi.
Definizione della relazione di ricorrenza ed esempi
di risoluzione per il calcolo della complessità di
semplici funzioni ricorsive.
- 30 Maggio 2006.
Esercitazione su MATLAB (2) (con Dimitri Breda)
Esercitazione "libera" di programmazione in C.
Funzioni ricorsive: hanoi (codice che stampa i
risultati su file) e Fibonacci.
Codice C per
misurare i tempi di esecuzione.
- 31 Maggio 2006.
Soluzione di alcune equazioni di ricorrenza: log n, n, n log n, n^2, 2^n, fibo(n).
- 1 Giugno 2006.
Esempi: Ricerca lineare e binaria di un elemento di un vettore.
Analisi del caso peggiore e cenni a quella del caso medio.
Ordinamento di un vettore:
bubble sort e merge sort.
- 6 Giugno 2006.
Esercitazione su MATLAB (3) (con Dimitri Breda)
- 7 Giugno 2006.
Rapresentazione dell'Informazione.
Richiami sulla rappresentazione degli interi (si veda lezione 2 Maggio),
rappresentazione
in eccesso k.
Rappresentazione di numeri "reali":
IEEE floating point. Limiti e errori.
Rappresentazione di caratteri:
codice ASCII e codice UNICODE.
- 8 Giugno 2006.
Rappresentazione di immagini.
Bitmap: bianco e nero, livelli di grigio e
colori RGB (red, green, blue).
Cenni sulla compressione di immagini (formati GIF e JPG).
Rappresentazione di suoni.
Campionatura e cenni
alla compressione per il formato MP3.
Architettura del calcolatore:
Architettura di Von Neumann e a Bus.
La CPU: le sue parti principali e il ciclo
"accedi, decodifica, esegui".
- 13 Giugno 2006. Esercitazione in laboratorio.
- 14 Giugno 2006.
Tipologia delle istruzioni assembler.
La memoria principale.
Bus Dati e Bus Indirizzi.
La Memoria Secondaria.
Supporti di memoria secondaria.
Valutazione del corso.
Testi di Riferimento
Altri testi o siti di appoggio
Home page