Programma 1998-99

Introduzione alla programmazione e al linguaggio Pascal.

Sintassi dei linguaggi di programmazione: grammatiche e diagrammi sintattici. Sintassi del Pascal. Le nozioni e i costrutti fondamentali della programmazione imperativa: dichiarazioni e istruzioni; valori, variabili, espressioni, e assegnazione; tipi di valori e di variabili; ingresso/uscita; istruzioni semplici e strutturate, istruzioni condizionali (if then else,case) e iterative (for,while,repeat) e loro semantica dettagliata. Il sistema dei tipi del Pascal: tipi semplici, tipi enumerati, tipi strutturati (array e record). Sottoprogrammi (procedure e funzioni), pila dei record di attivazione, parametri formali e argomenti effettivi, passaggio parametri per valore e per riferimento, variabili locali, visibilità e tempo di vita delle variabili, sottoprogrammi annidati. Stack e ricorsione (diretta e indiretta), semplici sottprogrammi ricorsivi. Strutturazione di un programma in corpo principale e sottoprogrammi.

Caratteristiche particolari del TurboPascal 7.0.

La valutazione ottimizzata degli operatori booleani. I tipi-stringa. La primitiva di interruzione di ciclo break, la primitiva di uscita da sottoprogramma exit. I tipi di file e l'ingresso/uscita da/su file. I moduli o unit .

Principi di sviluppo ed analisi di programmi iterativi.

Nozioni di base di logica. Il principio di induzione matematica e le dimostrazioni per induzione. Asserzioni in un programma: asserzioni iniziale e finale; condizione di uscita o di continuazione di un ciclo; invariante di ciclo e dimostrazioni per induzione. Progettazione - per mezzo dell' uso di asserzioni - di programmi e sottoprogrammi iterativi corretti. Terminazione, correttezza parziale e correttezza totale: dimostrazioni informali di correttezza. Terminazione, correttezza parziale e correttezza totale: dimostrazioni informali di correttezza. La sequenza di Collatz.
La notazione asintotica e gli ordini di infinito. Analisi della complessità temporale e spaziale di un algoritmo, nel caso peggiore, nel caso migliore, e nel caso medio.     

Progettazione ed analisi di algoritmi numerici.

Somma, massimo (o minimo), media, i due valori piú grandi, ecc. di una sequenza di numeri; fattoriale, esponenziale ingenuo e veloce, test di primalità. Numeri reali.

Progettazione ed analisi di algoritmi su vettori.

Input/output di vettori. Input/output di vettori da/su file. Costruzione di una unit per i vettori. Somma, massimo, media, ecc. degli elementi di un vettore. Rappresentazione grafica dell'invariante di ciclo per algoritmi su vettori. Massima sottosequenza crescente in un vettore. Ricerca sequenziale di un elemento in un vettore, con restituzione di un booleano oppure di un indice. Vettori di record, nozione di chiave. Ricerca in un vettore dell'indice del primo elemento uguale alla somma dei k precedenti. Ricerca di una stringa in un testo. Funzione a valore booleano che stabilisce se un vettore è ordinato. Inserimento ordinato. Algoritmi di ordinamento: ordinamento per inserimento, ordinamento per selezione, ordinamento a bolle. Ricerca binaria in un vettore ordinato. Fusione di due vettori ordinati in un terzo. Fusione di sottovettori di due vettori ordinati nel primo dei due. Rappresentazione di polinomi.
Ordinamento parziale: il problema della bandiera tricolore.
Nozione di tipo astratto di dato. Rappresentazione di insiemi per mezzo di vettori (ordinati e non): intersezione, ecc.
Rappresentazione di insiemi per mezzo di vettori di booleani: input/output, ricerca, intersezione, unione, ecc.

Progettazione ed analisi di algoritmi: matrici.

Input/output di matrici. Somma di matrici. Moltiplicazione di matrici. Matrice simmetrica.  bsp;

Semplici algoritmi su files.


 

Dove studiare:

Altri testi consigliati: