Informatica 1 per Matematica 2002/2003


Programma del Corso


  1. 20 Aprile 2004. Introduzione al corso e ai sussidi didattici. Breve Storia del Calcolatore. Abaco, Regolo, calcolatori meccanici ed elettromeccanici. Calcolatori di prima, seconda, terza e quarta generazione.
  2. 21 Aprile 2003. 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. Esempio: la Macchina di Turing.
  3. 27 Aprile 2004. Diagrammi di flusso. Sintassi e semantica intutiva. Esempi di algoritmo: massimo tra due numeri, scambio di variabili, 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.
  4. 28 Aprile 2004. Diagrammi strutturati e fortemente strutturati. Il Teorema di Böhm-Jacopini. Linguaggi di Programmazione: Panoramica generale. Compilazione ed Interpretazione.
  5. 29 Aprile 2004. La Programmazione Imperativa in C. Sintassi: Identificatori e Parole riservate. Commenti in C. Le istruzioni printf e scanf. L'istruzione di assegnamento.
  6. 4 Maggio 2004. Tipi di dato primitivi di C. Interi, Booleani, Floating Point e Caratteri. La codifica ASCII.
  7. 5 Maggio 2004. Vettori. Il ciclo for. Istruzione if-(then)-else.
  8. 6 Maggio 2004 (lab-3ore). Stesura, compilazione, ed esecuzione di semplici programmi C. Programmi per l'input e l'output. Esercizi per scoprire i valori ammissibili dei tipi primitivi. Massimo di due e tre numeri, calcolo del fattoriale e del MCD con l'algoritmo di Euclide. (Lezione con D. Ballis)
  9. 11 Maggio 2004. Conversioni di tipi e tipo puntatore. Funzioni e Procedure. Generalità e Sintassi. Definizione ed Uso.
  10. 12 Maggio 2004. Passaggio parametri e variabili locali e globali. Esempi.
  11. 13 Maggio 2004 (lab-3ore). Procedure di Accettazione di vettori e loro stampa. Funzione per il MCD di due numeri. Procedura di stampa di matrice bidimensionale e stampa di semplici figure. Funzioni di Aritmetica su Vettori di digits. (Lezione con D. Ballis)
  12. 18 Maggio 2004. Esercizi sul passaggio di parametri. Procedura di scambio tra interi. Definizioni ricorsive. Principi generali. Definizione ricorsiva in C del Fattoriale e della funzione di Fibonacci.
  13. 19 Maggio 2004. Descrizione ricorsiva del problema della torre di Hanoi e sua definizione in C. Studio dei valori e del numero di chiamate ricorsive della funzione di Fibonacci e della torre di Hanoi. Ottimizzazione del codice mediante memorizzazione di risultati parziali.
  14. 20 Maggio 2004 (lab-3 ore). Implementazione e studio di procedure ricorsive. (lezione con D. Ballis)
  15. 25 Maggio 2004. 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. Tempo per istruzioni if-else, for, e while. Esempi ed esercizi.
  16. 26 Maggio 2004. Calcolo della complessità di funzioni non ricorsive. Definizione della relazione di ricorrenza ed esempi di risoluzione per il calcolo della complessità di funzioni ricorsive. Esempio: Ricerca lineare e binaria di un elemento di un vettore.
  17. 27 Maggio 2004. (lab-3ore) Esempio: Ordinamento di un vettore: bubble sort e merge sort. Esempio. Raggiungibilità in un grafo. (Lezione con D. Ballis)
  18. 1 Giuno 2004. Rappresentazione 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.
  19. 3 Giugno 2004. Rappresentazione di numeri "reali": IEEE floating point. Limiti e errori. Rappresentazione di caratteri: codice ASCII e codice UNICODE. 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).
  20. 8 Giugno 2004. Rappresentazione di suoni. Campionatura e cenni sulla rappresentazione degli spartiti: MIDI. Compressione dell'Informazione: generalità e Teorema di Shannon.
  21. 9 Giugno 2004.Architettura del calcolatore: gerarchia di macchine astratte. 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.
  22. 9 Giugno 2004. Memoria Cache: memorizzazione ed accesso ai dati. La Memoria Secondaria. Dischi magnetici e Ottici. Principali caratteristiche. MATLAB. Modalità d'esame.

Testo di Riferimento

Altri testi o siti di appoggio e indice delle lezioni in cui sono rilevanti


Home page