Programma 1997-98
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 proposizionale e di logica dei predicati. 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.
Introduzione alla teoria assiomatica dei programmi, programmi annotati.
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, algoritmo
di Euclide per il MCD, calcolo della parte intera del logaritmo. 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. Il crivello di Eratostene per la generazione
dei numeri primi.
Progettazione ed analisi di algoritmi: matrici.
Input/output di matrici. Somma di matrici. Moltiplicazione di matrici.
Matrice simmetrica.
Dove studiare:
Altri testi consigliati:
-
Aho-Ullman, Fondamenti di Informatica, Zanichelli, lettura fortemente
consigliata,
pag. 1-33 e 35-50: induzione, proprietà di programmi;
pag. 81-117: compessità temporale di programmi iterativi.
-
G.Fiorentino e altri, Pascal Laboratorio di programmazione, McGrawHill,
1996.
-
M.Gori e altri, Pascal e C guida pratica alla programmazione, McGraw-Hill,
1996.
-
U. de' Liguoro, Note su Correttezza e terminazione di programmi Pascal
iterativi, 1996, disponibili in biblioteca e in copisteria.