Informatica 1 per Matematica 2001/2002


Programma del Corso

  1. 9 Aprile 2002. Breve Storia del Calcolatore. Strumenti per la rappresentazione dei numeri. Strumenti per il calcolo: abaco, regolo, macchina di Schickard, Pascal, Leibniz, macchine di Babbage. Integratore analitico di Lord Kelvin. Il 1900: Macchina di Hollerith, calcolatori elettromeccanici (Zuse, Stibitz-Williams, Harvard Mark I) e primi calcolatori a valvole (ABC, Colossus, ENIAC, EDVAC e EDSAC).
  2. 11 Aprile 2002. Calcolatori di prima, seconda, terza e quarta generazione. Evoluzione dei PC. Il concetto di Algoritmo. Etimologia del nome e definizione informale. I 10 punti caratterizzanti la nozione. Esempi di algoritmi.
  3. 12 Aprile 2002. Diagrammi di flusso. Sintassi e semantica intutiva. Esempi di algoritmo: massimo tra due numeri, scambio di variabili, algoritmo di Euclide. Strutture while, if e repeat. Simulazione delle ultime due mediante la prima. Diagrammi strutturati e fortemente strutturati.
  4. 18 Aprile 2002. Il Teorema di Böhm-Jacopini. Logica Digitale. Porte AND, OR, e NOT. Tabelle di verità e Assiomi dell'algebra Booleana. Porte NAND, NOR e equivalenze. RS-flip flop: alla base del bit. Semisommatori e sommatori completi.
  5. 19 Aprile 2002. Rappresentazione di numeri interi: senza segno e con modulo e segno. Aritmetica binaria: Funzioni (e circuiti) per la: complementazione di n bits, l'incremento del numero naturale rappresentato da n bits e la somma di due numeri di n bits. Moltiplicazione di numeri binari: principi e problemi. Rappresentazione in complemento a 2. Principi generali. Algoritmo di somma (e differenza) e dimostrazione di correttezza della regola dei riporti. Rappresentazione ad eccesso k.
  6. 23 Aprile 2002. Rappresentazione di numeri "reali": IEEE floating point. Limiti e errori. Rappresentazione di caratteri: codice ASCII e codice UNICODE. Rappresentazione di suoni. Campionatura. Esempi pratici.
  7. 26 Aprile 2002. Rappresentazione degli spartiti: MIDI. Rappresentazione di immagini. Bitmap: bianco e nero, livelli di grigio e colori RGB (red, green, blue). Compressione di immagini (formati GIF e JPG). Architettura del calcolatore: gerarchia di macchine astratte.
  8. 30 Aprile 2002. Architettura di Von Neumann e a Bus. La CPU: le sue parti principali e il ciclo "accedi, decodifica, esegui". La memoria principale. Composizionalità della memoria. Bus Dati e Bus Indirizzi. Memoria Cache: memorizzazione ed accesso ai dati.
  9. 2 Maggio 2002. La Memoria Secondaria. Dischi magnetici e Ottici. Principali caratteristiche. Un esempio di semplice Assembler. Insieme di istruzioni.
  10. 3 Maggio 2002. Esempi di programmazione in assembler. Linguaggi di Programmazione: Panoramica generale. Compilazione ed Interpretazione.
  11. 7 Maggio 2002. La Programmazione Imperativa usando Java. Sintassi: Parole riservate, Identificatori, Variabili, Tipi Primitivi, Costanti, Letterali.
  12. 9 Maggio 2002. Espressioni e istruzione di Assegnamento. Struttura di un programma Java. Alcuni metodi per l'I/O.
  13. 9 Maggio 2002. Esercitazione in laboratorio: stesura, compilazione, ed esecuzione di semplici programmi Java.
  14. 10 Maggio 2002. Commenti in Java. Strutture di controllo. Sequenza, blocco, istruzioni if-(then)-else, while. Esempi.
  15. 14 Maggio 2002. Esercitazione in laboratorio: Massimo e minimo di un numero, test di 'parità' di un numero intero, Somma e Media di una sequenza di numeri di lunghezza non nota a priori.
  16. 16 Maggio 2002. Stesura, usando il while, dell'algoritmo di Euclide in Java. Le istruzioni do-while e for. Esempi di cicli for. Test di Primalità. Vettori e matrici. Dichiarazione, allocazione ed uso. Esempi.
  17. 17 Maggio 2002. Sottoprogrammi, procedure, funzioni, Metodi. Definizione ed Uso dei metodi in Java. Parametri formali e parametri attuali. Passaggio parametri per valore.
  18. 21 Maggio 2002. Passaggio parametri per indirizzo. Esempi (metodo per il MCD) ed esercizi. Definizioni ricorsive. Principi generali. Definizione ricorsiva in Java del Fattoriale e dell'algoritmo di Euclide.
  19. 23 Maggio 2002. Descrizione ricorsiva del problema della torre di Hanoi e sua definizione in Java. Descrizione della successione di Fibonacci, sua definizione ricorsiva in Java. Studio dei valori e del numero di chiamate ricorive. Ottimizzazione del codice mediante memorizzazione di risultati parziali.
  20. 23 Maggio 2002. Esercitazione in laboratorio: Implementazione di Hanoi e Fibonacci. Test computazionali delle varie versioni. Varianti.
  21. 24 Maggio 2002. Test di valutazione. Criteri di valutazione degli algoritmi: comprensibilità, chiarezza, efficienza. Misura del tempo di esecuzione: benchmarking e analisi. Dipendenza dalla dimensione (e non dal valore!) dell'input. Confronto tra complessità lineare, n log n, quadratica e esponenziale. Effetti dell'evoluzione dell'HW sulle varie famiglie di algoritmi.
  22. 29 Maggio 2002. Limiti superiori al tempo d'esecuzione degli algoritmi. La notazione "O" grande. Principali risultati ed esempi. 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.
  23. 30 Maggio 2002. Calcolo della complessità di metodi non ricorsivi. Definizione della relazione di ricorrenza ed esempi di risoluzione per il calcolo della complessità di metodi ricorsivi. Esempio: Ricerca lineare e binaria di un elemento di un vettore.
  24. 31 Maggio 2002. Esempio: Ordinamento di un vettore: bubble sort e merge sort. Cenni su MATLAB con particolare riferimento al linguaggio di programmazione in esso incluso. Modalità d'esame.

Testo di Riferimento

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


Home page