Informatica 1 per Matematica 2002/2003


Programma del Corso


Per materiale didattico e altre informazioni si consulti anche il sito del corso in questo portale.
  1. 10 Aprile 2003. 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. 11 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.
  3. 15 Aprile 2003. 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.
  4. 24 Aprile 2003. Strutture while, if e repeat. Simulazione delle ultime due mediante la prima. Diagrammi strutturati e fortemente strutturati. Il Teorema di Böhm-Jacopini. Linguaggi di Programmazione: Panoramica generale.
  5. 2 Maggio 2003. Compilazione ed Interpretazione. La Programmazione Imperativa usando Java. Sintassi: Parole riservate, Identificatori, Variabili, Tipi Primitivi, Costanti, Letterali.
  6. 6 Maggio 2003. LABORATORIO: Stesura, compilazione, ed esecuzione di semplici programmi Java. Programmi per l'input e l'output.
  7. 6 Maggio 2003. LABORATORIO: Massimo di due e tre numeri, calcolo del fattoriale e del MCD con l'algoritmo di Euclide.
  8. 8 Maggio 2003. Operatori ed Espressioni e loro tipi. Istruzione di Assegnamento. Struttura di un programma Java mediante grammatica BNF. Commenti in Java. Sequenza, blocco, istruzione if-(then)-else,
  9. 9 Maggio 2003. Istruzioni while e for. Esempi: Somma e Media di una sequenza di numeri di lunghezza non nota a priori. Test di Primalità. Vettori e matrici. Dichiarazione, allocazione ed uso. Esempi.
  10. 13 Maggio 2003. LABORATORIO. Test sui tipi delle espressioni e degli assegnamenti. Realizzazione dei due programmi visti nella lezione precedente (Somma e media e Primalità).
  11. 13 Maggio 2003. LABORATORIO. Esercizi con il ciclo for, stampa di semplici figure bidimensionali. Accettazione di vettori e loro stampa. Calcolo di massimo e minimo degli elementi di un vettore e/o di una matrice. Stampa di matrici bidimensionali. Integrazione con l'esercizio sopra di stampa figure bidimensionali.
  12. 15 Maggio 2003. Sottoprogrammi, procedure, funzioni, Metodi. Definizione ed Uso dei metodi in Java. Parametri formali e parametri attuali. Passaggio parametri per valore. Passaggio parametri per indirizzo. Esempi ed esercizi.
  13. 16 Maggio 2003. Esempio: metodo per il MCD. Variabili locali e globali (cenni). Definizioni ricorsive. Principi generali. Definizione ricorsiva in Java del Fattoriale e dell'algoritmo di Euclide. Descrizione ricorsiva del problema della torre di Hanoi e sua definizione in Java.
  14. 19 Maggio 2003. LABORATORIO. Realizzazione dei programmi visti a lezione nelle 2 lezioni precedenti. Due ulteriori esercizi:
  15. 20 Maggio 2003. Esercitazione. 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. Cenno di soluzione degli esercizi sui "quadrati ricorsivamente annidati". Algoritmi su interi "lunghi".
  16. 21 Maggio 2003.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. Limiti superiori al tempo d'esecuzione lgoritmi. La notazione "O" grande.
  17. 23 Maggio 2003. Principali risultati ed esempi della 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. Calcolo della complessità di metodi non ricorsivi.
  18. 26 Maggio. Esercitazione in Laboratorio.
  19. 27 Maggio. 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.
  20. 29 Maggio. Esempio: Ordinamento di un vettore: bubble sort e merge sort. Esempio. Raggiungibilità in un grafo. Questionario sulla didattica.
  21. 30 Maggio. 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. Rappresentazione di numeri "reali": IEEE floating point. Limiti e errori.
  22. 3 Giugno. Rappresentazione di caratteri: codice ASCII e codice UNICODE. Rappresentazione di suoni. Campionatura. Esempi pratici. Rappresentazione degli spartiti: MIDI. Rappresentazione di immagini. Bitmap: bianco e nero, livelli di grigio e colori RGB (red, green, blue).
  23. 5 Giugno. Cenni sulla compressione di immagini (formati GIF e JPG). 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". La memoria principale. Composizionalità della memoria. Bus Dati e Bus Indirizzi.
  24. 6 Giugno. Memoria Cache: memorizzazione ed accesso ai dati. La Memoria Secondaria. Dischi magnetici e Ottici. Principali caratteristiche. Modalità d'esame.

Testo di Riferimento

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


Home page