Logica e Informatica (A.A. 2021/2022)
A chi è rivolto il corso. Il corso, di 3 crediti, è una delle sezioni del corso Metodi quantitativi per l'informatica e viene tenuto nel secondo semestre (periodo didattico da febbraio 2022 a maggio 2022).
Docente. Prof. Maurizio Lenzerini.
Obiettivi. L'obiettivo del corso è di introdurre la logica matematica come potente strumento per modellare e ragionare formalmente su diversi aspetti dell’informatica, quali: i requisiti di un sistema informatico, i dati, i programmi, gli automi e la computazione in generale. Vengono studiati i principali sistemi formali della logica, in primis la logica proposizionale e la logica dei predicati. Viene affrontato il tema dell’uso della logica nello specificare argomenti, dimostrare o confutare la loro validità ed inferire le loro conseguenze, anche in modo automatico. Vengono poi approfonditi alcuni temi che riguardano l’uso della logica nell’informatica, in particolare nella gestione dei dati, nell’interrogazione di basi di dati, nella specifica di programmi e nel ragionamento sulle proprietà dei programmi e degli automi.
- 28 giugno 2022. Gli studenti possono ora prenotarsi per l'appello di luglio. Si ricorda che al momento della verbalizzazione lo studente deve ovviamente superato gli esami di entrambe le sezioni del corso.
- Il materiale didattico prevede le slides preparate dal docente, che si possono scaricare dalla pagina MOODLE del corso
Per seguire le lezioni a distanza gli studenti che si sono iscritti al corso tramite il sistema MOODLE devono collegarsi alla stanza virtuale ZOOM. Sul sito dell'ateneo è disponibile una pagina che include una guida all'uso di ZOOM. Le registrazioni delle lezioni sono disponibili nella pagina MOODLE del corso. Gli orari e le aule sono questi:
- lunedì: [ore 11:00 - 13:00] Sede Marco Polo (RM021), viale dello Scalo S. Lorenzo, 82, aula 106
- martedì: [ore 14:00 - 15:00] Sede Marco Polo (RM021), viale dello Scalo S. Lorenzo, 82, aula 106
Il materiale delle esercitazioni, comprese le soluzioni degli esercizi, è scaricabile accedendo alla pagina MOODLE del corso.
| Week | Lunedì (11:00 - 13:00) aula 106 | Martedì (14:00 - 15:00) aula 106 |
| 01 (Feb 21) |
Lezioni 1,2 - Introduzione al corso - Sintassi della logica proposizionale |
Lezione 3 - Semantica della logica proposizionale |
| 02 (Feb 28) |
Lezioni 4,5 - Proprietà della logica proposizionale - Pragmatica della logica proposizionale: esempi ed esercizi |
Lezione 6 - La nozione di implicazione logica |
| 03 (Mar 07) | Lezione 7,8 - La nozione di teoria proposizionale - Esercizi di formalizzazione in logica proposizionale |
|
| 04 (Mar 14) | Lezione 9,10 - Sistemi formali per la deduzione in logica proposizionale - Il sistema assiomatico di Hilbert |
|
| 05 (Mar 21) | Lezione 11,12 - Inferenze nel sistema di Hilbert - Introduzione alla Davis-Putnam procedure |
|
| 06 (Mar 28) | Lezione 13,14 - La procedura DPLL per a verifica di soddisfacibilità |
|
| 07 (Apr 04) | Lezione 15,16 - La tecnica dei tableau per la logica proposizionale |
|
| 08 (Apr 11) | Lezione 17,18 - La logica del primo ordine: sintassi e semantica |
Lezione 19,20 - La logica del primo ordine: deduzione - La logica del primo ordine: esercizi |
| 09 (Apr 18) | |
|
| 10 (Apr 25) | ||
| 11 (Mag 02) |
|
|
| 12 (Mag 09) | Lezione 21,22 - La logica del primo ordine: esercizi - La logica del primo ordine: indecidibilità |
Lezione 23,24 - Logica e basi di dati - Il calcolo relazionale come linguaggio per query |
| 13 (Mag 16) | Lezione 25,26 - Logica e vincoli di integrità |
|
| 14 (Mag 23) | Lezione 27,28 - Il linguaggio Datalog |
- 1. La logica proposizionale. Sintassi e semantica della logica proposizionale. Potere espressivo della logica proposizionale. “Satisfiability”: problema, complessità e algoritmi di decisione. L’inferenza nella logica proposizionale. Problemi e algoritmi di decisione relativi all’inferenza.
- 2. La logica dei predicati del primo ordine. Sintassi e semantica della logica dei predicati del primo ordine. Potere espressivo della logica dei predicati. L’inferenza nella logica dei predicati: deduzione, induzione e abduzione. Sistemi formali per la deduzione. Problemi di decisione nella logica dei predicati. Cenno alle logiche modali e temporali.
- 3. Applicazione della logica nell’informatica. La logica nello sviluppo e nell’analisi dei programmi. Logica e automi. La logica nella gestione dei dati. Logica e linguaggi di interrogazione nelle basi di dati. Il linguaggio Datalog. La logica nella rappresentazione della conoscenza.
Lo studente può scegliere di svolgere l'esame per la sezione "Logica e Informatica" tra due modalità:
- Nel primo caso lo studente o il gruppo di due studenti (non di più) sceglie di affrontare un argomento da essi stessi proposto (eventualmente anche in sinergia con un progetto relativo alla sezione del corso su metodi probabilistici) oppure selezionato tra quelli proposti dal docente, e comunica la scelta al docente. Se l'argomento scelto non è stato selezionato già da altri studenti, il docente assegna l'argomento allo studente o al gruppo, altrimenti dovrà essere fatta un'altra scelta. Una volta ricevuta l'accettazione da parte del docente, lo studente o il gruppo si occupa di reperire il materiale per condurre il lavoro, eventualmente chiedendo consiglio al docente. Alla fine del lavoro svolto lo studente o il gruppo produce una breve relazione (anche semplicemente sotto forma di slides), consegna la relazione al docente pochi giorni prima del colloquio d'esame, e nel colloquio conduce una discussione (tipicamente di una ventina di minuti supportata da slides) sul lavoro svolto.
Quando lo studente è pronto per la presentazione manda un messaggio al docente chiedendo di effettuare la prova in una specifica data tra quelle di seguito indicate. Le possibili date per presentare il lavoro on line all'indirizzo [https://meet.google.com/hzy-save-oqw] sono per il momento le seguenti (altre se ne aggiungeranno nei successivi appelli):
- martedì 17 gennaio 2023, ore 17:00,
- martedì 24 gennaio 2023, ore 17:00,
- martedì 31 gennaio 2023, ore 17:00,
- martedì 7 febbraio 2023, ore 17:00,
- martedì 14 febbraio 2023, ore 17:00.
- Nel secondo caso l'esame consiste di una prova scritta ed eventualmente di una prova orale, entrambe vertenti sul programma d'esame. Anche in questo caso lo studente deve mandare un messaggio al docente, che indicherà la data dell'esame.
- Primo appello: giugno 2022
- Secondo appello: luglio 2022
- Terzo appello: settembre 2022
- Appello straordinario (per studenti studenti part-time, fuori corso, iscritti per l’A.A. 2021-2022 al terzo anno della laurea e al secondo anno della laurea magistrale, studenti con disabilità e con D.S.A.): ottobre 2022
- Quarto appello: gennaio 2023
- Quinto appello: febbraio 2023
- Appello straordinario (per studenti fuori corso, part time, con disabilità e con D.S.A.): aprile 2023