Course Syllabus
Obiettivi
Scopo del Corso è quello di fornire, insieme a un linguaggio formale, le basi teoriche, gli strumenti e le tecniche che rappresentano i fondamenti matematici dell’informatica. Gli argomenti che verranno trattati hanno lo scopo di mettere lo studente in grado di acquisire livelli di astrazione necessari alla comprensione delle basi teoriche e computazionali dell’informatica mediante l’apprendimento di nozioni formali indispensabili per affrontare e padroneggiare livelli di complessità superiore caratteristici dell’iter disciplinare scelto.
Contenuti sintetici
Il corso prevede l’insegnamento introduttivo agli strumenti matematico formali che sono alla base dell’informatica teorica, che comprende l’acquisizione di un linguaggio formale di base (insiemi, funzioni e relazioni), di strumenti di concettualizzazione astratti (grafi, alberi e strutture algebriche) e nozioni basilari della logica matematica (proposizionale e predicativa).
Programma esteso
- Insiemi: definizioni estensionali e intensionali, sottoinsiemi e insiemi potenza, unione, intersezione, complementazione, differenza e differenza simmetrica, partizioni, prodotto cartesiano, sequenze, coppie e n-uple ordinate, relazioni, funzioni e operazioni, funzione inversa, proprietà delle funzioni, composizione di funzioni, cardinalità degli insiemi, tecnica di diagonalizzazione (cenni), multinsiemi, cenni di analisi combinatoria.
- Strutture relazionali, grafi e ordinamenti: proprietà delle relazioni, tabelle e matrici booleane e relative operazioni, grafi, relazioni d’equivalenza, composizione di relazioni, strutture relazionali e ordinamenti, diagramma di hasse, algebra relazionale (cenni), chiusura transitiva, ordinali e reticoli, funzioni monotone su insiemi ordinati, teorema del punto fisso (cenni).
- Algebra di Boole: definizione delle algebre di Boole. semigruppi, monoidi e gruppi (cenni), algebra booleana.
- Induzione: principi d’induzione matematica, dimostrazioni per induzione sui numeri naturali, induzione e ricorsione su insiemi arbitrari, stringhe, formule ben formate.
- Logica - linguaggi proposizionali: linguaggio e semantica, apparato deduttivo, sintassi e semantica della logica proposizionale, equivalenza logica, modelli, decidibilità, completezza di insiemi di connettivi.
- Logica - sistemi deduttivi proposizionali: tavole di verità, tableaux proposizionali, completezza e correttezza, teorema di deduzione.
- Logica - linguaggi predicativi: sintassi della logica predicativa, variabili libere e legate, semantica della logica predicativa, interpretazioni e modelli, equivalenza semantica, connettivi e operatori insiemistici, teorie del primo ordine.
- Logica - sistemi deduttivi predicativi: tableaux per la logica predicativa, completezza e correttezza nel calcolo predicativo.
- Teoria dei linguaggi formali: introduzione agli automi a stati finiti.
Prerequisiti
Conoscenze matematiche di base apprese durante la scuola superiore.
Modalità didattica
Lezioni frontali ed esercitazioni in aula. Uso della piattaforma Moodle. 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 domande aperte su tutti gli argomenti del corso e viene valutato con un punteggio 0-30/30. Ciascuna domanda prevede tre 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 o alla verbalizzazione del voto. Coloro che hanno preso un punteggio inferiore o uguale a 21/30 devono necessariamente sostenere la prova orale. Coloro che hanno ottenuto un punteggio strettamente superiore a 21 possono effettuare la prova orale oppure chiedere che venga verbalizzato il proprio voto.
Orario di ricevimento
Su richiesta.
Aims
The main aim of the course is to introduce formal, theoretical, and technical foundations of computer science. The main issues to be presented will give students the necessary abstraction level to understand the theoretical and computational bases of computer science through the learning of the basic formal notions to tackle required higher levels of complexity required by the discipline.
Contents
This course introduces the formal mathematical bases of theoretical computer science; namely, basic mathematical notions (set theory, relations, and functions), abstract conceptualization instruments (graphs, trees, and algebraic structures), and basics of logics (propositional and predicative).
Detailed program
- Sets: extensional and intensinal definitions, sub-sets and power sets, union, intersection, complementation, difference and symmetric difference, partitions, Cartesian product, sequences, pairs and ordered n-tuples, relations, functions and operations, inverted function, function composition, set cardinality, diagonalization (introduction), multi-sets, notions of combinatorics.
- Relational structures, graphs and sorting: properties of relations,boolean matrixes and related operations, graphs, relations of equivalence, composition of relations, transitive closure, ordinal and grids, monotonic functions on ordered sets, hasse diagrams, fixed-point theorem (introduction).
- Boolean algebra: introduction to semigroups, monoids and groups, Boolean algebra)
- Induction: principles of mathematical induction, proofs by induction, induction and recursion on arbitrary sets, strings, well-formed formulas.
- Logic - propositional language: language and semantics, deduction, syntax and semantics of propositional logics, logical equivalence, models, decidability, completeness of set of connectives.
- Logic - propositional deductive systems: truth tables, tableaux for propositional logic, completeness and correctness.
- Logic - predicative languages: syntax of predicative logics, free and bound variables, interpretations and models, semantic equivalence, connectives and set operator, first order theories.
- Logic - predicative deductive systems: tableaux for first order logic, completeness and correctness in the predicate calculus.
- Introduction to formal language theory: finite state automata.
Prerequisites
Basic mathematical knowledge from high school programs.
Teaching form
Active lectures and exercises both in person. Moodle 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 or, under the circumstances specified below, can register their mark. Those who have been marked below or equal to 21/30 in the written test must necessarily take the oral test. Those who have obtained a mark equal or larger to 22/30 can take the oral exam or ask for their vote to be registered. 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.
Office hours
On demand.
Staff
-
Stefania Bandini
-
Alex Graudenzi
-
Rafael Penaloza Nyssen