Course Syllabus
Obiettivi
L’insegnamento fornisce le basi teoriche e formali dell’informatica, con particolare riferimento alla matematica discreta, alla logica e alla teoria degli automi.
L’obiettivo è sviluppare negli studenti e nelle studentesse la capacità di modellare e analizzare problemi computazionali mediante strumenti rigorosi, promuovendo adeguati livelli di astrazione, formalizzazione e ragionamento deduttivo. Un ruolo centrale sarà riservato alle esercitazioni su problemi sia teorici, sia applicativi.
Al termine del corso, studenti e studentesse avranno acquisito strumenti teorici, metodologici e operativi fondamentali per affrontare con rigore le complessità concettuali tipiche del percorso in Informatica.
1. Conoscenza e capacità di comprensione
Al termine dell'insegnamento, lo/a studente/ssa:
- conoscerà le basi teoriche e computazionali dell'informatica, in termini di matematica discreta, teoria degli insiemi, logica e automi;
- comprenderà il ruolo delle strutture astratte nella modellazione informatica.
- avrà interiorizzato la differenza fra sintassi e semantica
2. Conoscenza e capacità di comprensione applicate
Lo/a studente/ssa sarà in grado di:
- comprendere un testo o un problema computazionale definito in termini formali
- modellare problemi complessi tramite insiemi, relazioni, funzioni, grafi e logiche formali;
- impiegare la ricorsione, costruire dimostrazioni, utilizzare sistemi deduttivi e progettare automi a stati finiti;
- applicare un linguaggio formale per analizzare strutture e sistemi.
3. Autonomia di giudizio
Lo studente svilupperà la capacità sufficienti per:
- comprendere il linguaggio formale utilizzato nel dominio dell'informatica teorica e applicata;
- valutare la correttezza e l’efficacia di modelli e dimostrazioni;
- scegliere strumenti formali adatti al problema trattato.
4. Abilità comunicative
Lo studente sarà in grado di:
- comunicare con precisione concetti e modelli formali;
- utilizzare il linguaggio tecnico appropriato in ambito informatico.
5. Capacità di apprendere
Lo studente svilupperà la capacità di:
- affrontare lo studio di contenuti teorici e pratici in modo autonomo;
- applicare le conoscenze acquisite in insegnamenti successivi del Corso di Laurea e in contesti interdisciplinari.
Contenuti sintetici
Il corso introduce gli strumenti matematico-formali fondamentali per la comprensione dell’informatica, fra cui l’acquisizione di un linguaggio formale di base (insiemi, funzioni, relazioni), lo studio di strutture astratte per la concettualizzazione (grafi, alberi, ordinamenti, reticoli e strutture algebriche), strumenti matematici quali ricorsione e induzione, i principi essenziali della logica matematica, sia proposizionale che predicativa e cenni di teoria degli automi.
Programma esteso
Sezione 1 | "Insiemi, relazioni e funzioni"
Argomenti: Matematica discreta; numeri; insiemi; sottoinsiemi; insieme potenza; rappresentazione estensionale ed intensionale; operazioni su insiemi; famiglie di insiemi; partizioni; coppie/tuple ordinate; prodotto cartesiano; relazioni; dominio e codominio; operazioni su relazioni; proprietà delle relazioni; rappresentazione delle relazioni (sagittale/grafo), diagramma cartesiano, tabella); proprietà delle relazioni; grafi bipartiti; matrici Booleane; operazioni su matrici Booleane: join, meet, prodotto Booleano (composizione di relazioni); relazioni di equivalenza; classi di equivalenza; insieme quoziente; funzioni; proprietà delle funzioni; arietà; punto fisso; operazioni; controimmagine; composizione di funzioni; funzione inversa; funzione caratteristica; multinsieme; cardinalità e funzioni; teorema di Cantor.
Sezione 2 | "Grafi, alberi, ordinamenti e Algebra di Boole"
Argomenti: Grafi, grado, (semi)cammini, cicli, distanza, DAG, sottografo indotto, grafi etichettati, grafi completi e grafi connessi, isomoformismo fra grafi; alberi; profondità e altezza, alberi binari; proprietà degli alberi binari (pieni, completi, bilanciati); coperture, elementi estremali, join e meet; diagrammi di Hasse, reticoli, tipi di reticolo; complemento; reticoli complementati; strutture algebriche; reticoli Booleani; algebra Booleana; operazioni logiche.
Sezione 3 | "Induzione e ricorsione"
Argomenti: differenza fra ricorsione e induzione; definizioni; assiomi, ipotesi e teoremi; ricorsione: caso base e funzione ricorsiva; insiemi ben fondati; codice ricorsivo; funzioni ricorsive su stringhe e strutture complesse; dimostrazioni per induzione: caso base, ipotesi induttiva, passo induttivo; induzione completa.
Sezione 4 | "Logica proposizionale"
Argomenti: Proposizioni atomiche; operatori e precedenza; formule ben formate; albero sintattico; semantica; assegnazioni Booleane; valutazioni Booleane; tavole di verità; composizionalità; equivalenze; completezza; modelli e contromodelli; tipi di formule: tautologie, contraddizioni, formule soddisfacibili non tautologiche; sistemi logici; relazione di conseguenza logica ⊨; soddisfacibilità; sistemi deduttivi; regole di inferenza; assiomi; dimostrazioni e teoremi; derivabilità ⊢; chiusura deduttiva; proprietà dei sistemi deduttivi (inclusività, monotonicità, compattezza, taglio di premesse, deduzione); collegamento fra sistemi logici e sistemi deduttivi; correttezza e completezza; decibilità; tableaux proposizionali.
Sezione 5 | "Logica predicativa"
Argomenti: Sintassi della logica predicativa: variabili, costanti, funzioni, predicati, operatori, costruttori logici, quantificatori; arietà di funzioni e predicati; focus su quantificatori universali ed esistenziali; termini, atomi e formule ben formate; variabili libere e legate; enunciati; semantica della logica dei predicati; interpretazione o struttura del primo ordine: dominio, funzione di interpretazione; assegnazioni; soddisfacibilità atomica; sostituzioni; modelli e tautologie; equivalenze semantiche; teorie del primo ordine; rappresentazione della conoscenza; da formule a linguaggio naturale e viceversa; sistemi logici vs. sistemi deduttivi; tableaux predicativi.
**Sezione 6 | "Introduzione ai linguaggi formali: gli automi a stati finiti" **
Prerequisiti
Conoscenze matematiche di base apprese durante la scuola superiore.
Modalità didattica
Le attività previste sono:
- 48 ore di lezione frontale in modalità erogativa
- 20 ore di esercitazione in modalità interattiva.
Uso della piattaforma elearning.
Il corso sarà tenuto in lingua italiana.
Materiale didattico
Luigia Carlucci Aiello, Fiora Pirri, “Strutture, logica, linguaggi” (Pearson, 2005)
Periodo di erogazione dell'insegnamento
1° Semestre
Modalità di verifica del profitto e valutazione
Esame finale (senza prove intermedie) composto da due prove separate: esame scritto ed esame orale, articolati come descritto qui di seguito.
L'esame scritto prevede dieci (10) domande aperte su tutti gli argomenti del corso e viene valutato con un punteggio 0-30/30. Ciascuna domanda prevede un numero di sottodomande, ciascuna appartenente a una delle seguenti tipologie di esercizi: domande sulle nozioni presentate, domande di ragionamento e deduzione, risoluzione di esercizi che richiedono calcolo o sviluppo di una soluzione ad un problema assegnato, con prevalenza di esercizi del terzo tipo.
L'esame orale orale consiste nella valutazione della conoscenza degli argomenti del corso attraverso domande aperte, eventualmente relative agli errori commessi durante l'esame scritto.
Coloro che hanno preso un punteggio sufficiente, ovvero maggiore o uguale a 18/30 sono ammessi alla prova orale (facoltativa) o alla verbalizzazione del voto.
Orario di ricevimento
Su richiesta.
Sustainable Development Goals
Aims
The course provides the theoretical and formal foundations of computer science, with particular emphasis on discrete mathematics, logic, and automata theory.
Its objective is to develop students’ ability to model and analyze computational problems using rigorous tools, fostering appropriate levels of abstraction, formalization, and deductive reasoning. Exercises on both theoretical and applied problems will play a central role.
By the end of the course, students will have acquired essential theoretical, methodological, and practical tools to rigorously tackle the conceptual complexities typical of the computer science curriculum.
1. Knowledge and understanding
By the end of the course, the student will:
- know the theoretical and computational foundations of computer science, including discrete mathematics, set theory, logic, and automata;
- understand the role of abstract structures in modeling computational problems;
- have internalized the distinction between syntax and semantics.
2. Applying knowledge and understanding
The student will be able to:
- understand a text or a computational problem defined in formal terms
- model complex problems using sets, relations, functions, graphs, and formal logic;
- apply recursion, construct proofs, use deductive systems, and design finite-state automata;
- use formal languages to analyze computational structures and systems.
3. Making judgements
The student will develop the ability to:
- understand the formal language used in theoretical and applied computer science;
- evaluate the correctness and adequacy of models and proofs;
- choose appropriate formal tools for the problem at hand.
4. Communication skills
The student will be able to:
- clearly and precisely communicate formal concepts and models;
- use appropriate technical language in computer science contexts.
5. Learning skills
The student will be able to:
- approach theoretical and practical content with increasing autonomy;
- apply acquired knowledge in advanced courses and interdisciplinary contexts.
Contents
The course introduces the fundamental mathematical and formal tools essential for understanding computer science, including the acquisition of a basic formal language (sets, functions, relations), the study of abstract structures for conceptualization (graphs, trees, orderings, lattices, and algebraic structures), mathematical tools such as recursion and induction, the essential principles of mathematical logic, both propositional and predicate logic, and an introduction to automata theory.
Detailed program
Section 1 | “Sets, Relations, and Functions”
Topics: Discrete mathematics; numbers; sets; subsets; power set; extensional and intensional representations; set operations; families of sets; partitions; ordered pairs/tuples; Cartesian product; relations; domain and codomain; operations on relations; properties of relations; representations of relations (arrow/graph), Cartesian diagram, table); properties of relations; bipartite graphs; Boolean matrices; operations on Boolean matrices: join, meet, Boolean product (composition of relations); equivalence relations; equivalence classes; quotient set; functions; properties of functions; arity; fixed point; operations; inverse image; function composition; inverse function; characteristic function; multisets; cardinality and functions; Cantor’s theorem.
Section 2 | “Graphs, Trees, Orderings, and Boolean Algebra”
Topics: Graphs, degree, (semi)paths, cycles, distance, DAGs, induced subgraphs, labeled graphs, complete and connected graphs, graph isomorphism; trees; depth and height; binary trees; properties of binary trees (full, complete, balanced); coverings, extremal elements, join and meet; Hasse diagrams, lattices, types of lattices; complement; complemented lattices; algebraic structures; Boolean lattices; Boolean algebra; logical operations.
Section 3 | “Induction and Recursion”
Topics: Difference between recursion and induction; definitions; axioms, hypotheses, and theorems; recursion: base case and recursive function; well-founded sets; recursive code; recursive functions on strings and complex structures; proofs by induction: base case, inductive hypothesis, inductive step; strong induction.
Section 4 | “Propositional Logic”
Topics: Atomic propositions; operators and precedence; well-formed formulas; syntax tree; semantics; Boolean assignments; Boolean evaluations; truth tables; compositionality; equivalences; completeness; models and countermodels; types of formulas: tautologies, contradictions, satisfiable but non-tautological formulas; logical systems; logical consequence relation ⊨; satisfiability; deductive systems; inference rules; axioms; proofs and theorems; derivability ⊢; deductive closure; properties of deductive systems (inclusiveness, monotonicity, compactness, premise cutting, deduction); connection between logical and deductive systems; soundness and completeness; decidability; propositional tableaux.
Section 5 | “Predicate Logic”
Topics: Syntax of predicate logic: variables, constants, functions, predicates, operators, logical constructors, quantifiers; arity of functions and predicates; focus on universal and existential quantifiers; terms, atoms, and well-formed formulas; free and bound variables; statements; semantics of predicate logic; first-order interpretation or structure: domain, interpretation function; assignments; atomic satisfiability; substitutions; models and tautologies; semantic equivalences; first-order theories; knowledge representation; from formulas to natural language and vice versa; logical systems vs. deductive systems; predicate tableaux.
Section 6 | “Introduction to Formal Languages: Finite-State Automata”
Prerequisites
High school-level mathematical skills.
Teaching form
The planned activities are:
- 48 hours of frontal lessons in lecture mode
- 20 hours of exercise in interactive mode.
Usage of the e-learning platform.
Course language: Italian.
Textbook and teaching resource
Luigia Carlucci Aiello, Fiora Pirri, “Strutture, logica, linguaggi” (Pearson, 2005).
The textbook is in Italian. Alternative books in English can be suggested upon request.
Semester
1st Semester
Assessment method
Final exam (without intermediate tests) that consists of two separate tests: written test and oral test.
The written test includes ten questions on all the topics addressed in the course and is evaluated with a mark ranging from 0 to 30. Each question includes three sub-questions, each belonging to one of the following types of exercises: open questions on a topic, questions that require reasoning and deduction, resolution of exercises requiring calculation or development of a solution to an assigned problem, with prevalence of exercises of the third type .
The oral test consists in the evaluation of the knowledge acquired about the course topics through open questions, possibly related to the mistakes made during the written test.
Those who have taken a sufficient mark, that is, greater than or equal to 18/30, are admitted to the oral test (optional) or can register their mark.
Office hours
On demand.
Sustainable Development Goals
Staff
-
Davide Elio Ciucci
-
Alex Graudenzi
-
Daniele Maria Papetti
