Informatica 1 per Matematica 2004/2005


Programma del Corso


  1. 19 Aprile 2005. 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.
  2. 20 Aprile 2005. 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, scambio di variabili, test di primalità.
  3. 21 Aprile 2005. 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. Il Teorema di Böhm-Jacopini.
  4. 26 Aprile 2005. Linguaggi di Programmazione: Panoramica generale. Compilazione ed Interpretazione. La Programmazione Imperativa in C. Introduzione per esempi. Le istruzioni printf e scanf.
  5. 27 Aprile 2005. Sintassi: Identificatori e Parole riservate. Commenti in C. Rappresentazione binaria di numeri interi. Numeri segna segno (unsigned) ed in complemento a due. Tipi di dato primitivi di C. Interi. L'istruzione di assegnamento. Cenni sulla sintassi formale con BNF.
  6. 28 Aprile 2005. Booleani. L'istruzione if-(then)-else. Il ciclo while ed il ciclo for. Esempio: test di primalità.
  7. 3 Maggio 2005. (lab, con Dimitri Breda) Stesura, compilazione, ed esecuzione di semplici programmi C. Programmi per l'input e l'output. Esercizi per scoprire i valori ammissibili dei tipi primitivi. Test di primalità.
  8. 4 Maggio 2005. Floating Point e Caratteri. La codifica ASCII. Vettori. Tipo puntatore.
  9. 5 Maggio 2005. Funzioni e Procedure. Generalità e Sintassi. Definizione ed Uso.
  10. 10 Maggio 2005. (lab) Realizzazione di semplici programmi con funzioni. Funzione che conta i primi minori o uguali a n dato e sua ottimizzazione. Funzione per il massimo comun divisore.
  11. 11 Maggio 2005. Passaggio parametri e variabili locali e globali. Esempi.
  12. 12 Maggio 2005. Definizioni ricorsive. Principi generali. Definizione ricorsiva in C del Fattoriale e della funzione di Fibonacci. Cenni alla macchina astratta per la realizzazione della ricorsione. Descrizione ricorsiva del problema della torre di Hanoi e sua definizione in C.
  13. 17 Maggio 2005. (lab) Funzione di Stampa di vettori e matrici. Funzioni ricorsive: hanoi (codice che stampa i risultati su file) e Fibonacci. Codice C per misurare i tempi di esecuzione.
  14. 18 Maggio 2005. Esercitazione in C. Stampa di semplici figure ricorsive. Funzioni di Aritmetica su Vettori di digits.
  15. 19 Maggio 2005. 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.
  16. 24 Maggio 2005. Introduzione a MATLAB (1) (dispensa). A cura del dr Dimitri Breda.
  17. 25 Maggio 2005. 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. Tempo per istruzioni if-else, for, e while. Calcolo della complessità di funzioni non ricorsive. Esempi.
  18. 26 Maggio 2005. Definizione della relazione di ricorrenza ed esempi di risoluzione per il calcolo della complessità di funzioni ricorsive. Esempi: Ricerca lineare e binaria di un elemento di un vettore. Ordinamento di un vettore: bubble sort e merge sort.
  19. 31 Maggio 2005. Esercitazione su MATLAB (2) (con Dimitri Breda)
  20. 1 Giugno 2005. Rapresentazione dell'Informazione. Rappresentazione di numeri interi: senza segno, con modulo e segno, in complemento a due ed in eccesso k. Esempi di operazioni in complemento a 2. Rappresentazione di numeri "reali": IEEE floating point. Limiti e errori. Rappresentazione di caratteri: codice ASCII e codice UNICODE.
  21. 7 Giugno 2005. Esercitazione su MATLAB (3) (con Dimitri Breda)
  22. 8 Giugno 2005. 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 sulla rappresentazione degli spartiti: MIDI. 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.
  23. 9 Giugno 2005. La memoria principale. Bus Dati e Bus Indirizzi. La Memoria Secondaria. Dischi magnetici e Ottici. Principali caratteristiche. Valutazione del corso.
  24. 14 Giugno 2005. (con Dimitri Breda) Esercitazione C e Matlab in laboratorio.

Testi di Riferimento

Altri testi o siti di appoggio


Home page