Scheda insegnamento
Laboratorio di Programmazione e Calcolo
| anno accademico: | 2016/2017 |
| docente: | Silvia Noschese |
| corso di laurea: | Matematica - DM 270/04 (triennale), I anno |
| tipo di attività formativa: | di base |
| crediti formativi: | 9 (84 ore di lezione) |
| lingua di insegnamento: | italiano |
| canale: | M-Z |
| periodo: | I sem (03/10/2016 - 13/01/2017) |
Frequenza: consigliata
Obiettivi del corso: L`obiettivo principale del corso è quello di avviare gli studenti ad un approccio costruttivo nella matematica anche attraverso l`uso dei calcolatori. Da questo punto di vista, il corso è complementare agli altri corsi del primo anno, nei quali è maggiormente enfatizzato l`approccio logico/deduttivo. La maggior parte del corso sarà dedicata alla soluzione di problemi, all`analisi degli algoritmi di base ed alla loro implementazione in C++.
Programma completo del corso:
Introduzione al linguaggio C++: tipi di variabili, conversione di tipo, variabili array, operatori logici (or, and, not), istruzioni di lettura e scrittura, istruzioni condizionali (if-else) e istruzioni di ciclo (for, while, do-while). Funzioni matematiche. Struttura di un programma C++. Funzioni. Passaggio delle variabili. Rappresentazione dei numeri interi e reali nel calcolatore. Propagazione degli errori nelle operazioni aritmetiche. Algoritmi stabili e algoritmi instabili: calcolo di pigreco. Calcolo del polinomio in un punto (algoritmo di Horner). Matrici, vettori e sistemi di equazioni lineari. Risoluzione numerica di sistemi di equazioni lineari: metodi di Gauss e di Jacobi. Uso della libreria grafica Gnuplot: grafico di una funzione. Metodi numerici per il calcolo degli zeri di una equazione non lineare: metodi della bisezione, di Newton e delle secanti. Uso della formula di Taylor per il calcolo di alcune funzioni matematiche. Interpolazione polinomiale. Metodi numerici per il calcolo di integrali definiti.
Contenuti svolti nella settimana 03-07/10/2016 (9 ore di lezione)
Struttura del corso. Introduzione alla programmazione. I numeri e la loro rappresentazione sui calcolatori. Reali e razionali. Numeri di macchina. Rappresentazione in virgola fissa e in virgola mobile. Singola e doppia precisione. Sistema floating point normalizzato. Approssimazione per troncamento e per arrotondamento. Overflow e underflow. L'aritmetica floating point. Errore assoluto e errore relativo. Precisione di macchina. Errore di roundoff. Linguaggio C++. Struttura di un programma. Uso di printf e scanf. Tipi di dato int, float, double. Operatori aritmetici. Operatori relazionali. Alternative (if - else).
Contenuti svolti nella settimana 10-14/10/2016 (4 ore di lezione + 2 ore di laboratorio)
Foglio di esercizi n.1. Cicli (for, while, do-while). Algoritmo per stimare la precisione di macchina. Esercizi sui numeri interi: numeri pari, classi resto, algoritmo di Euclide per M.C.D e m.c.m., algoritmi per il calcolo del fattoriale e del coefficiente binomiale. Divisione tra interi e conversione forzata (cast). Connettivi logici: operatori booleani AND, OR, NOT e operazioni sugli insiemi (intersezione, unione, sottrazione).
Contenuti svolti nella settimana 17-21/10/2016 (6 ore di lezione + 2 ore di laboratorio)
Foglio di esercizi n.2. Proprietà dei connettivi logici. Tipo di dato char. Alternative (switch).
Propagazione degli errori nelle operazioni aritmetiche: somma algebrica e cancellazione numerica, prodotto e divisione. Stabilità di un algoritmo. Risoluzione di una equazione di secondo grado e calcolo di pi greco con algoritmi stabili. Costo computazionale di un algoritmo: potenza intera di un numero reale e valutazione di un polinomio. Algoritmo di Horner.
Contenuti svolti nella settimana 24-28/10/2016 (2 ore di laboratorio)
Foglio di esercizi n.3.
Contenuti svolti nella settimana 31/10-04/11/2016 (4 ore di lezione)
Discussione sugli esercizi del foglio n. 3. Algoritmo per la somma della progressione geometrica. Algoritmo per il calcolo della media quadratica di n numeri. Gli array. Implementazione dell'algoritmo di Horner in C++. Algoritmo di conversione di un numero dalla base 10 alla base b e dalla base b alla base 10. Crivello di Eratostene.
Contenuti svolti nella settimana 07-11/11/2016 (6 ore di lezione + 2 ore di laboratorio)
Foglio di esercizi n.4. Successioni per ricorrenza. Algoritmo di Erone. Calcolo del numero di Nepero. Calcolo della massima componente di un vettore e della sua massima componente in valore assoluto (con relativi indici). Costruzione di vettori per ricorrenza. Ordinamento di un vettore con l'algoritmo di selezione (selection sort). Mediana di un vettore. Prodotto scalare. Gli array multidimensionali. Inserimento degli elementi di una matrice. Prodotto matrice-vettore. Esercizi di preparazione alla prima prova in itinere.
Contenuti svolti nella settimana 21-25/11/2016 (6 ore di lezione + 2 ore di laboratorio)
Foglio di esercizi n.5. Soluzione di sistemi lineari. Metodi diretti. Il caso di sistemi triangolari. Il metodo di Gauss. Complessità computazionale. Riordinamento pivotale. Calcolo del determinante di una matrice. Algoritmo di Gauss con riordinamento pivotale. Funzioni nel linguaggio C++. Passaggio di parametri per valore e per indirizzo. Passaggio di parametri di tipo array. Uso di typedef. Correzione degli esercizi della prima prova in itinere.
Contenuti svolti nella settimana 28/11-02/12/2016 (4 ore di lezione + 2 ore di laboratorio)
Foglio di esercizi n.6. Soluzione di sistemi lineari. Metodi iterativi. Il metodo di Jacobi. Convergenza del metodo di Jacobi. Un criterio di arresto a posteriori. Un criterio di arresto a priori. Confronto tra il costo del metodo di Jacobi e il costo del metodo di eliminazione di Gauss in termini di operazioni aritmetiche.
Implementazione in C++ degli algoritmi di Gauss con riordinamento pivotale e di Jacobi con criterio di arresto a priori o a posteriori. Istruzioni cin e cout.
Contenuti svolti nella settimana 05-09/12/2016 (2 ore di lezione + 3 ore di laboratorio)
Fogli di esercizi n.7 e n.7L. Soluzione numerica di equazioni non lineari. Localizzazione e separazione delle radici di una equazione. Il metodo di bisezione. Un criterio di arresto a priori. Iterazioni di punto fisso. Ordine di convergenza di un metodo di punto fisso. Teorema di convergenza locale.
Contenuti svolti nella settimana 12-16/12/2016 (6 ore di lezione + 3 ore di laboratorio)
Fogli di esercizi n.8 e n.8L. Iterazioni di punto fisso. Teorema di convergenza globale. Criteri di arresto a priori e a posteriori. Il metodo di Newton. Interpretazione grafica. Convergenza superlineare e convergenza quadratica. Estremo di Fourier e teoremi di convergenza monotona. Modifiche al metodo di Newton. Il metodo delle secanti. Esempi. Approssimazione di funzioni mediante polinomi. L'errore nell'approssimazione tramite la formula di Taylor. Esempi. Interpolazione. Esistenza e unicità del polinomio interpolatore. Errore nell'interpolazione.
Contenuti svolti nella settimana 19-23/12/2016 (2 ore di lezione + 3 ore di laboratorio)
Fogli di esercizi n.9 e n.9L. Come usare l'espressione dell'errore nell'interpolazione. Leggi di scelta dei nodi. Nodi di Chebyshev. Come rappresentare il polinomio interpolatore. Il polinomio interpolatore di Lagrange. Esempi.
Contenuti svolti nella settimana 09-13/01/2017 (4 ore di lezione + 3 ore di laboratorio)
Fogli di esercizi n.10 e n.10L. Formule di quadratura. Formule di quadratura interpolatorie. Formule di Newton-Cotes di tipo chiuso e di tipo aperto. Grado di precisione delle formule di Newton-Cotes. Formula del trapezio. Formula della parabola o di Simpson. Formula del rettangolo. Formule di quadratura composite. Formule di Newton-Cotes composite. Errore nelle formule di Newton-Cotes composite. Formula dei trapezi. Formula delle parabole o di Cavalieri-Simpson. Formula dei rettangoli. Esercizi di ricapitolazione.
Testo consigliato:
- Le note che saranno messe in rete;
- A. Quarteroni, R. Sacco, F. Saleri, P. Gervasio, Matematica numerica, Springer, 2014 (o ledizione del 2008 - dei primi tre autori). In alternativa può essere usato - se già posseduto - A. Quarteroni , Elementi di Calcolo Numerico, Progetto Leonardo, 1998 oppure J.F. Epperson, Introduzione all'analisi numerica, McGraw-Hill, 2003;
- Luis J. Aguilar, Fondamenti di programmazione in C++, McGraw-Hill, 2008 (o testo equivalente).
Modalità di erogazione: convenzionale
Risultati di apprendimento - Conoscenze acquisite: Gli studenti che abbiano superato l'esame avranno una conoscenza di base della programmazione e delle proprietà matematiche di semplici algoritmi. Gli studenti avranno anche acquisito le nozioni fondamentali su convergenza, ordine di convergenza, errore e complessità di algoritmi elementari.
Risultati di apprendimento - Competenze acquisite: Gli studenti che abbiano superato l'esame saranno in grado di scrivere un semplice codice C++ per scopi scientifici e di utilizzare alcuni algoritmi numerici di base per la soluzione di problemi. Saranno anche in grado di scegliere l`algoritmo più appropriato per la soluzione di semplici problemi quali la ricerca degli zeri, il calcolo di un integrale e la soluzione di un sistema lineare. Durante le esercitazioni in laboratorio impareranno ad usare un PC, gli strumenti grafici e una rete LAN.
Studio personale: la percentuale prevista di studio personale sul totale dell'impegno richiesto è del 65%