Informatica 2008/09

Informatica (C.d.S. in Matematica) A.A.2008/09
Calendario Lezioni e Argomenti trattati

Lu.23/02/09, ore 11:00-13:00, aula Tonelli Lezione 1.
Introduzione al corso; form da scaricare, compilare e spedire; mappa concettuale del corso; concetto di algoritmo per calcolatore; esempio di algoritmo.
Me.25/02/09, ore 11:00-12:00, aula Tonelli Lezione 2.
Schema di Von Neumann di un calcolatore: Input, CPU, Memoria, Output. Area di memoria, indirizzo, nome logico per un'area, tabella delle corrispondenze; prime operazioni elementari; pseudolinguaggio per descrivere un algoritmo; istruzioni di assegnazione e sequenza.
Ve.27/02/09, ore 11:00-13:00, aula Tonelli Lezione 3.
Istruzione di scelta (espressioni miste aritmetiche, relazionali e logiche), lettura/scrittura, inizio/fine. Problema esempio: progettazione dell'algoritmo in pseudolinguaggio. Completato Problema esempio. Proprieta' degli algoritmi. Strutture fondamentali di controllo: alternativa, ciclo e sequenza; riformulato codice esempio; assegnati alcuni semplici esercizi (vedi Esercizi).
Lu.02/03/09, ore 11:00-13:00, aula Tonelli Lezione 4.
Fasi di risoluzione di un problema; Problema: max fra tre numeri; organizzazione dati in memoria e riformulazione algoritmo. Problema: quoziente intero della divisione N/D; metodo delle sottrazioni successive e simulazione di esecuzione; tecnica delle scomposizioni successive; Problema: MCD di due interi non negativi; metodo di Euclide; algoritmo; simulazione di esecuzione; struttura di controllo procedura;
Me.04/03/09, ore 11:00-12:00, aula Tonelli Lezione 5.
La procedura nel pseudolinguaggio usato; passaggio parametri per valore e per indirizzo; simulazione del funzionamento. Il passaggio parametri nei linguaggi Pascal, Fortran e C; esempi di esecuzione nei tre casi citati.
Ve.06/03/09, ore 11:00-13:00, aula Tonelli Lezione 6.
Procedura max fra due numeri e considerazioni; procedura div e suo utilizzo per l'MCD; lasciato come esercizio di progettare la procedura rem, di riscrivere il main per l'MCD e di simularne l'esecuzione; Strutture dati lista e tabella; allocazione statica della memoria. Problema: minimo fra gli elementi di una lista; progettazione di una procedura min_vect e di un main; simulazione di esecuzione.
Lu.09/03/09, ore 11:00-13:00, aula Tonelli Lezione 7.
Procedura min_vect con passaggio lista per indirizzo. Introduzione ai Sistemi Operativi ed in particolare al S.O. Linux. Interprete Comandi; File System; Gestione delle Periferiche; Gestione della Memoria; Gestione dei processi. Dettagli sulla Gestione dei Processi e sul File System. Linux: interfaccia grafica e interfaccia testuale, utilizzo della shell, comandi base per la gestione di file.
Ma/Me/Gi 10-12/03/09, ore 14:00-16:30, Laboratorio Linux.
ESERCITAZIONI IN LABORATORIO
Me.11/03/09, ore 11:00-13:00, aula Tonelli Lezione 8.
Problema: conversione di un intero positivo da base 10 a base B; fasi di soluzioni; progettazione dell'algoritmo, simulazione.
Ve.13/03/09, ore 11:00-13:00, aula Tonelli Lezione 9.
Introduzione al linguaggio C: esempio di programma C e descrizione delle sue componenti principali (direttive, identificatore main, parte dichiarativa, parte esecutiva); tipi di dati semplici predefiniti (int, char, float, double); strutture di controllo if e while; comandi di compilazione; comando di esecuzione.
Lu.16/03/09, ore 11:00-13:00, aula Tonelli Lezione 10.
Compilatore e Linker; cenno a compilatori vs interpreti; errori in compilazione, in linking, in esecuzione; opzioni di compilazione (gcc). Tipi di dati in C: i tipi int, char e float(double), allocazione di memoria, range dei valori, operazioni ammissibili, conversioni implicite ed esplicite (cast). Sui numeri finiti (float e double): forma normalizzata, rappresentazione (segno, esponente, mantissa), insieme F(beta, t, lambda, omega), F nel caso float(4byte) e double(8byte), esempio di F(2,3,-1,2), distribuzione sull'asse reale, underflow ed overflow, unita' di arrotondamento e precisione di calcolo U, aritmetica fra numeri finiti.
Ma/Me/Gi 17-19/03/09, ore 14:00-16:30, Laboratorio Linux.
ESERCITAZIONI IN LABORATORIO
Me.18/03/09, ore 11:00-13:00 Aula Tonelli Lezione 11.
Memorizzazione di una tabella; Problema: ordine alfabetico fra due parole; progettazione di una procedura compare con passaggio tabella per indirizzo.
Ve.20/03/09, ore 11:00-13:00, Aula Vitali Lezione 12.
Tipi strutturati: il costruttore array; dichiarazione di array mono e multidimensionali (direttiva define); gestione array mediante operazioni sugli elementi (cicli while e for). typedef per dichiarazione "nuovi tipi" (ridefinizione o enumerazione esplicita dei valori); Problema: determinare i numeri primi minori di un numero assegnato (Crivello di Eratostene);
Lu.23/03/09, ore 11:00-13:00, aula Tonelli Lezione 13.
Puntatore (operatore &), deferenziazione (operatore *), il costruttore puntatore, equivalenza fra array e puntatori. Problema: ordinare in senso crescente una lista di numeri; metodo selection sort e bubble sort.
Ma/Me/Gi 24-26/03/09, ore 14:00-16:30, Laboratorio Linux.
ESERCITAZIONI IN LABORATORIO
Me.25/03/09, ore 11:00-12:00, aula Tonelli Lezione 14.
Le procedure in C (funzioni): intestazione, parametri formali, valore di ritorno, corpo, ecc.; chiamata di funzioni, parametri attuali, ecc.; esempi di funzioni e chiamate;
Ve.27/03/09, ore 11:00-13:00, aula Tonelli Lezione 15.
Ridirezione dell'input e dell'output. Array monodimensionali e bidimensionali come parametri di funzioni; esempio di funzione stampa tabella; ambiente globale e locale; prototipo di funzioni; ambito di visibilita' delle variabili; durata delle variabili; variabili statiche e automatiche; funzioni time e rand. Conversione di un numero decimale da base 10 a base B<=16.
Lu.30/03/09, ore 11:00-13:00, aula Tonelli Lezione 16.
Main di esempio per conversione di un numero decimale da base 10 a base B<=16 (lasciato come esercizio la realizzazione delle due funzioni C). Dettagli su strutture di controllo (for, do while, switch, break). Costruttore struct: dichiarazione, dichiarazione con etichetta e typedef; inizializzazione e utilizzo di variabili struct (accesso ai suoi campi); puntatore a variabile struct, operatore "->" per accedere ai campi mediante puntatore; esempi di informazioni organizzate a struct: numeri complessi e polinomi.
Ma/Me/Gi 30/3-2/4/09, ore 14:00-16:30, Laboratorio Linux.
ESERCITAZIONI IN LABORATORIO
Me.1/04/09, ore 11:00-12:00, aula Tonelli Lezione 17.
esempi di informazioni organizzate a struct: lista linkata. Esempio di costruzione di una libreria di funzioni per gestire numeri complessi.
Ve.3/04/09, ore 11:00-13:00, aula Tonelli Lezione 18.
Gestione di file da programma C: puntatore alla struttura FILE, funzione fopen di apertura file, funzioni di lettura e scrittura, controllo e chiusura di un file. Alcuni esempi. Tipo e argomenti della funzione main. Alcuni esempi.
Me.15/04/09, ore 11:00-12:00, aula Tonelli Lezione 19.
Programmazione C su piu' file: dichiarazione e definizione di oggetti globali; dichiarazione extern, file header, direttive #include, #ifndef #endif, #ifdef #endif, #define, macro. Comandi di compilazione di piu' file; Commentati i file GCVec2dLib.c, GCVec2dLib.h, main1.c e main2.c presenti nel'archivio veclib0809.tgz.
Ve.17/04/09, ore 11:00-13:00, aula Tonelli Lezione 20.
Comando make e file Makefile; grafo delle dipendenze; costruzione di un Makefile; sintassi; target; macro. Makefile per la compilazione dei programmi presenti nell'archivio veclib0809.tgz. Allocazione dinamica della memoria: funzioni malloc e free.
Lu.20/04/09, ore 11:00-13:00, aula Tonelli Lezione 21.
Esempi di allocazione dinamica; memoria stack (LIFO) e heap; rischi dell'allocazione dinamica: garbage collection e dangling reference; funziono realloc; esempi di allocazione. Ricorsivita': esempi di funzioni ricorsive; gestione della ricorsione e memoria stack; esempio del fattoriale di un numero; lasciato come esercizio di scrivere una funzione ricorsiva per l'mcd.
Ma/Me/Gi 21-23/4/09, ore 14:00-16:30, Laboratorio Linux.
ESERCITAZIONI IN LABORATORIO
Me.22/04/09, ore 11:00-12:00, aula Tonelli Lezione 22.
Algoritmo di ordinamento quick-sort via ricorsione: progettazione di una funzione ricorsiva "quicksort" e di una funzione "cardine".
Ve.24/04/09, ore 11:00-13:00, aula Tonelli Lezione 23.
Progettazione non ricorsiva di una funzione ricorsiva mediante gestione di uno stack; esempio su algoritmo quicksort (implementazione non ricorsiva in C). Struttura dati STACK e sua gestione mediante array e puntatore. Il backtracking: generazione di permutazioni; soluzione del problema delle torri degli scacchi su una scacchiera nxn sia ricorsivamente che non.
Lu.27/04/09, ore 11:00-13:00, aula Tonelli Lezione 24.
Elaborazione Grafica: architettura per grafica interattiva; Frame Buffer, GPU, CRT; funzione put_pixel(); gestione dell'interattivita' tramite programmazione event-driven. Sistema XWindow. Problema esempio: disegno di un segmento in coord. schermo (algoritmo di Linea Incrementale). (vedi slide graph01a_0809.pdf)
Ma/Me/Gi 28-30/4/09, ore 14:00-16:30, Laboratorio Linux.
ESERCITAZIONI IN LABORATORIO
Me.29/04/09, ore 11:00-12:00, aula Tonelli Lezione 25.
Progettazione di algoritmi con rappresentazione grafica dei risultati; problema esempio: disegno di un poligono regolare in coord. floating point; (file polygonf.c); trasformazione window-viewport (vedi slide graph01b_0809.pdf).
Lu.04/05/09, ore 11:00-13:00, aula Tonelli Lezione 26.
Problema esempio: grafico di una funzione; discretizzazione in punti (tabulazione), determinazione window, mapping window-vieport con conservazione delle proporzioni, disegno; (file draw_fun.c). Introduzione alla libreria SDL e alle funzioni della libreria GCGraLib messe a disposizione per fare grafica interattiva con programmazione C (vedi slide graph02_0809.pdf).
Ma/Me/Gi 05-07/5/09, ore 14:00-16:30, Laboratorio Linux.
ESERCITAZIONI IN LABORATORIO
Me.06/05/09, ore 11:00-12:00, aula Tonelli Lezione 27.
Elementi di elaborazione di immagini: introduzione alle funzioni della libreria GCGraLib messe a disposizione per la visualizzazione di immagini. Programmi presenti in ambiente Linux: display e import.
Ve.08/05/09, ore 11:00-13:00, aula Tonelli Lezione 28.
Scala e rotazione di una immagine: trasformazioni di scala e rotazione; interpolazione componenti colore (nearest neighbor, bilinear interpolation e bicubic interpolation) (vedi slide graph02_0809.pdf). Visionato programma esempio rgb2gray.c per la conversione di una immagine a colori in livelli di grigio. Introduzione al linguagio LaTex ed al suo utilizzo; semplici esempi (vedi slide latex_0809.pdf).
Lu.11/05/09, ore 11:00-13:00, aula Tonelli Lezione 29.
Alberi generici: definizioni e rappresentazione in memoria; alberi binari: pieno, completo e heap; memorizzazione come lista; gestione di un heap (costruzione, inserimento, ordinamento, ricerca); heapsort.
Ma/Me/Gi 12-14/5/09, ore 14:00-16:30, Laboratorio Linux.
ESERCITAZIONI IN LABORATORIO
Me.13/05/09, ore 11:00-12:00, aula Tonelli Lezione 30.
Visita di un albero binario DepthFirst inorder, preorder, postorder. Generalizzazione per alberi generici. Ancora su LaTex: inclusione di immagini e disegni in un documento LaTex. Introduzione al gioco Forza4, oggetto del progetto d'esame.
Ve.15/05/09, ore 11:00-13:00, aula Tonelli Lezione 31.
Giochi a due finiti; definizioni e albero di gioco; algoritmo MinMax; funzione di valutazione per MinMax con profondità fissata; potatura alpha-beta dell'albero. Presentato e discusso il progetto d'esame (vedi file .pdf relativo).
Torna alla home page di Giulio Casciola