Informatica 1 per Matematica 2006/2007
Programma del Corso
- 18 Aprile 2007.
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.
- 19 Aprile 2007.
Formalismi per la descrizione degli algoritmi.
I Diagrammi di flusso.
Sintassi e semantica intutiva. Esempi di algoritmo: massimo tra
due numeri, sommatoria, fattoriale.
Test di primalità.
Algoritmo naive
per il MCD e algoritmo di Euclide.
- 24 Aprile 2007.
Rappresentazione testuale dei diagrammi di flusso.Strutture while, if e repeat.
Simulazione delle ultime due mediante la prima.
Diagrammi strutturati e fortemente strutturati.
Il Teorema di Böhm-Jacopini.
Breve cenno alla
Macchina di Turing.
- 26 Aprile 2007.
Linguaggi di Programmazione: Panoramica generale.
Compilazione ed Interpretazione.
La Programmazione Imperativa in C.
Introduzione per esempi.
L'istruzione di assegnamento.
Commenti in C.
L'istruzione printf.
L'istruzione scanf.
L'istruzione if-(then)-else.
Il ciclo while ed
il ciclo for.
Esempio: test di primalità
- 2 Maggio 2007. (1h)
Identificatori e parole chiave.
Tipi di dati in C.
Rappresentazione binaria di numeri interi.
Numeri segna segno (unsigned) e in segno e modulo.
Tipi interi: valori e operazioni.
- 3 Maggio 2007.
Booleani,
Floating Point e Caratteri.
La codifica ASCII.
Vettori.
- 8 Maggio 2007.
(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.
- Si stampi la matrice della codifica ASCII
- 9 Maggio 2007.
Matrici.
Cenni alla compatibilità tra tipi
e alle funzioni di conversione.
Nesting di if..else.
Tipo puntatore.
- 10 Maggio 2007.
Funzioni e Procedure.
Generalità e Sintassi.
Definizione ed Uso di funzioni.
Passaggio parametri. Esempi.
- 15 Maggio 2007. (lab, con D. Breda)
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.
- Procedura che stampa i primi N numeri primi.
- 16 Maggio 2007.
Passaggio per `indirizzo' in C.
Variabili locali
e globali. Esempi.
- 22 Maggio 2007. (lab, con Dimitri Breda).
Introduzione a MATLAB (1).
Esercitazione in C:
- Procedura che stampa una matrice quadrata di caratteri.
- Procedura che inizializza matrici in modo da stampare
alcune figure disegnate alla lavagna.
- 23 Maggio 2007.
Definizioni ricorsive. Principi generali.
Definizione ricorsiva in C del Fattoriale e della
funzione di Fibonacci.
Cenni alla macchina astratta per la realizzazione
della ricorsione.
Funzione per il massimo comun divisore.
- 24 Maggio 2007.
Descrizione ricorsiva del problema
della torre di Hanoi e sua definizione in C.
Esercitazione (Stampa di figure ricorsive).
- 29 Maggio 2007. (lab, con Dimitri Breda)
Esercitazione.
Funzioni ricorsive: hanoi (codice che stampa i
risultati su file) e Fibonacci.
Codice C per
misurare i tempi di esecuzione.
Introduzione a MATLAB (2).
- 30 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.
Calcolo della complessità
degli algoritmi:
assunzione di tempo costante per assegnamenti,
input/output, e test in assenza di chiamate di
funzione.
- 31 Maggio 2007.
La notazione "O" grande.
Tempo per istruzioni if-else, for, e while.
Calcolo della complessità di funzioni non ricorsive.
Esempi.
- 5 Giugno 2007.
Esercitazione su MATLAB (3) (con Dimitri Breda)
- 6 Giugno 2007.
Definizione della relazione di ricorrenza ed esempi
di risoluzione per il calcolo della complessità di semplici funzioni ricorsive.
Soluzione di alcune equazioni di ricorrenza: log n, n, n log n, n^2, 2^n, fibo(n).
- 7 Giugno 2007.
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. Algoritmi quadratici.
- 12 Giugno 2007.
Ordinamento:
bubble sort e merge sort.
Esercitazione su operazioni su interi lunghi a piacere.
- 13 Giugno 2007.
Rapresentazione dell'Informazione.
Richiami sulla rappresentazione degli interi,
rappresentazione
in eccesso k.
Rappresentazione di numeri "reali":
IEEE floating point. Limiti e errori.
Rappresentazione di caratteri:
codice ASCII e codice UNICODE.
- 14 Giugno 2007.
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.
Valutazione del corso.
- 19 Giugno 2007.
Architettura del calcolatore:
Architettura di Von Neumann e a Bus.
La CPU: le sue parti principali e il ciclo
"accedi, decodifica, esegui".
Tipologia delle istruzioni assembler.
La memoria principale.
Bus Dati e Bus Indirizzi.
La Memoria Secondaria.
Supporti di memoria secondaria.
Testi di Riferimento
Altri testi o siti di appoggio
Home page