Il corso tratta i principi e la pratica della programmazione
imperativa e le nozioni fondamentali della programmazione a oggetti.
Scopo del corso è consentire allo studente di costruire e
comprendere programmi di piccole e medie dimensioni, individuare errori
e valutare la correttezza degli algoritmi rispetto alle loro
specifiche.
Alla conclusione del corso lo studente deve inoltre poter affrontare l'apprendimento di altri linguaggi di programmazione imperativi e di approfondire la conoscenza della programmazione a oggetti.
Il corso viene svolto in 64 ore di lezioni ed esercitazioni in aula distribuite in due periodi.
Introduzione. Cenni storici. Le origini. Problemi. Descrizione rigorosa dei problemi. Le specifiche. Macchine astratte. Definizione matematica di una macchina semplificata. Algoritmi. Descrizione rigorosa delle soluzioni. Nozione di algoritmo come ``programma'' eseguibile da un particolare esecutore. Tesi di Church.
Il linguaggio di programmazione. Macchina astratta, interprete e compilatore. Variabili, espressioni e tipi. Identificatori, variabili, espressioni. Tipi di dati base: interi, reali, booleani, caratteri. Definizione di ambiente e di stato. Dichiarazione di variabili e loro valutazione. Comandi. Nozione di comando. Assegnamento: sintassi e valutazione. Comandi strutturati: sequenza, blocco, condizionale e iterazione. Valutazione dei comandi. Tipi di dati strutturati. Strutture dati a dimensione prefissata (vettori, array, record) e non (sequenze, file, ...): caratteristiche generali, tecniche di accesso, criteri per l'uso. Puntatori. Nozione di puntatore; aritmetica dei puntatori. Sottoprogrammi. Nozione di sottoprogramma; procedure e funzioni. Parametri formali e attuali; passaggio per valore e per riferimento. Stack di ambienti. Variabili locali; visibilità, tempo di vita.
Tipi di Dati Astratti. I tipi di dati come strutture algebriche e relazionali. I tipi di dati strutturati rivisitati. Esempi. Ricorsione Induzione matematica: numeri naturali e insiemi induttivamente generati. Definizioni per ricorsione strutturale. Soluzione ricorsiva di problemi. Programmazione ricorsiva: ruolo dello stack e valutazione di sotto-programmi ricorsivi. Tipi di Dati Astratti e Ricorsione. Tipi di dati ricorsivi: liste, pile, alberi, alberi binari. Algoritmi ricorsivi; eliminazione della ricorsione.