PROGRAMMAZIONE PROCEDURALE E LOGICA

Obiettivi formativi:

Questo insegnamento ha lo scopo di illustrare i principi di base, le tecniche e gli strumenti della programmazione di applicazioni informatiche, attraverso la presentazione dei concetti tipici della programmazione imperativa di natura procedurale e della programmazione dichiarativa di natura logica.

Settore scientifico-disciplinare:

INF/01.

Crediti:

12.

Modulo:

Unico.

Durata:

Annuale, 120 ore (72 di lezione teorica + 48 di esercitazione guidata).

Frequenza:

Consigliata, ma non obbligatoria.

Docente:

Prof. Marco Bernardo.

Programma:

01. Introduzione alla programmazione degli elaboratori:
      01.01 Definizioni di base dell'informatica.
      01.02 Cenni di storia dell'informatica.
      01.03 Architettura degli elaboratori.
      01.04 Sistemi operativi.
      01.05 Linguaggi di programmazione e compilatori.
      01.06 Una metodologia di sviluppo software "in the small".

02. Programmazione procedurale: il linguaggio ANSI C:
      02.01 Cenni di storia del C.
      02.02 Formato di un programma con una singola funzione.
      02.03 Inclusione di libreria.
      02.04 Funzione main.
      02.05 Identificatori.
      02.06 Tipi di dati predefiniti: int, double, char.
      02.07 Funzioni di libreria per l'input/output interattivo.
      02.08 Funzioni di libreria per l'input/output tramite file.

03. Espressioni:
      03.01 Definizione di costante simbolica.
      03.02 Dichiarazione di variabile.
      03.03 Operatori aritmetici.
      03.04 Operatori relazionali.
      03.05 Operatori logici.
      03.06 Operatore condizionale.
      03.07 Operatori di assegnamento.
      03.08 Operatori di incremento/decremento.
      03.09 Operatore virgola.
      03.10 Espressioni aritmetico-logiche.
      03.11 Precedenza e associatività degli operatori.

04. Istruzioni:
      04.01 Istruzione di assegnamento.
      04.02 Istruzione composta.
      04.03 Istruzioni di selezione: if, switch.
      04.04 Istruzioni di ripetizione: while, for, do-while.
      04.05 Istruzione goto.
      04.06 Teorema fondamentale della programmazione strutturata.

05. Procedure:
      05.01 Formato di un programma con più funzioni su singolo file.
      05.02 Dichiarazione di funzione.
      05.03 Definizione di funzione e parametri formali.
      05.04 Invocazione di funzione e parametri effettivi.
      05.05 Istruzione return.
      05.06 Parametri e risultato della funzione main.
      05.07 Passaggio di parametri per valore e per indirizzo.
      05.08 Funzioni ricorsive.
      05.09 Modello di esecuzione a pila.
      05.10 Formato di un programma con più funzioni su più file.
      05.11 Visibilità degli identificatori locali e non locali.

06. Tipi di dati:
      06.01 Classificazione dei tipi di dati e operatore sizeof.
      06.02 Tipo int: rappresentazione e varianti.
      06.03 Tipo double: rappresentazione e varianti.
      06.04 Funzioni di libreria matematica.
      06.05 Tipo char: rappresentazione e funzioni di libreria.
      06.06 Tipi enumerati.
      06.07 Conversioni di tipo e operatore di cast.
      06.08 Array: rappresentazione e operatore di indicizzazione.
      06.09 Stringhe: rappresentazione e funzioni di libreria.
      06.10 Strutture e unioni: rappresentazione e operatore punto.
      06.11 Puntatori: operatori e funzioni di libreria.

07. Correttezza di programmi procedurali:
      07.01 Triple di Hoare.
      07.02 Determinazione della precondizione più debole.
      07.03 Verifica della correttezza di programmi procedurali iterativi.
      07.04 Verifica della correttezza di programmi procedurali ricorsivi.

08. Introduzione alla logica matematica:
      08.01 Cenni di storia della logica.
      08.02 Teoria degli insiemi.
      08.03 Relazioni e funzioni.
      08.04 Principio di induzione.

09. Logica proposizionale:
      09.01 Sintassi della logica proposizionale.
      09.02 Semantica e decidibilità della logica proposizionale.
      09.03 Conseguenza ed equivalenza nella logica proposizionale.
      09.04 Proprietà algebriche dei connettivi logici.
      09.05 Sistemi deduttivi per la logica proposizionale.

10. Logica dei predicati:
      10.01 Sintassi della logica dei predicati.
      10.02 Semantica e indecidibilità della logica dei predicati.
      10.03 Conseguenza ed equivalenza nella logica dei predicati.
      10.04 Proprietà algebriche dei quantificatori.
      10.05 Sistemi deduttivi per la logica dei predicati.

11. Programmazione logica: il linguaggio Prolog:
      11.01 Forme normali per formule logiche.
      11.02 Teoria di Herbrand e algoritmo di refutazione.
      11.03 Metodo di risoluzione per la logica proposizionale.
      11.04 Unificazione e risoluzione per la logica dei predicati.
      11.05 Prolog: clausole di Horn e strategia di risoluzione SLD.
      11.06 Prolog: termini, predicati, taglio e negazione.

12. Attività di laboratorio:
      12.01 Sessione di lavoro in Linux.
      12.02 Gestione dei file in Linux.
      12.03 L'editor gvim.
      12.04 Il compilatore gcc.
      12.05 L'utility di manutenzione make.
      12.06 Il debugger gdb.
      12.07 Implementazione dei programmi C introdotti a lezione.
      12.08 Il compilatore/interprete gprolog.
      12.09 Implementazione dei programmi Prolog introdotti a lezione.

Testi di riferimento:

  • Hanly, Koffman, "Problem Solving and Program Design in C", Addison-Wesley, 2012.
  • Kernighan, Ritchie, "The C Programming Language", Prentice Hall, 1988
               (Kernighan, Ritchie, "Il Linguaggio C", Prentice Hall, 2004).
  • Asperti, Ciabattoni, "Logica a Informatica", McGraw-Hill, 1997
               (Schöning, "Logic for Computer Scientists", Birkhäuser, 2008).
  • Console, Lamma, Mello, Milano, "Programmazione Logica e Prolog", UTET, 1997
               (Sterling, Shapiro, "The Art of Prolog", MIT Press, 1997).
  • Propedeuticità:

    Matematica Discreta.

    Modalità didattiche:

    Lezioni teoriche ed esercitazioni guidate in laboratorio (materiale didattico).

    Modalità di accertamento:

    Progetto, prova scritta e prova orale (prove d'esame).

    Commissione d'esame:

    Prof. Marco Bernardo e Dott. Alessandro Aldini (supplente: Prof. Alessandro Bogliolo).

    Note:

    Il progetto, che cambia ad ogni sessione d'esame, deve essere consegnato almeno 10 giorni prima della prova scritta. Esso è superato se il voto è di almeno 18/30; il voto rimane valido fino alla seconda sessione d'esame successiva a quella in cui il progetto viene consegnato. In caso di consegna tardiva, viene applicata una penale di 3/30 per ogni giorno di ritardo. Qualora il progetto venga riconsegnato in un successivo appello d'esame, il voto del progetto precedentemente consegnato viene annullato; se la riconsegna avviene nella medesima sessione, al voto del nuovo progetto consegnato viene applicata una penale di 5/30 perché gli sviluppatori possono beneficiare della correzione del progetto precedentemente consegnato.
    La prova scritta, che cambia ad ogni appello d'esame e può essere sostenuta solo se il progetto è stato superato, consiste in 9 domande più 2 esercizi da svolgere in 90 minuti. Essa è superata se il voto è di almeno 18/30; il voto rimane valido solo per l'appello d'esame in cui la prova scritta viene sostenuta.
    La prova orale, che può essere sostenuta solo se il progetto e la prova scritta sono stati superati, consiste in una discussione del progetto e della prova scritta, più ulteriori domande. Se superata, essa determina un aggiustamento compreso tra -5/30 e 5/30 della media dei due precedenti voti, producendo così il voto finale.

    Ultima modifica: 05/07/2016 Approvato da: Presidente CCdL