CdSINFORMATICA
Codice728AA
CFU9
PeriodoPrimo semestre
LinguaItaliano
| Moduli | Settore/i | Tipo | Ore | Docente/i | |
| FONDAMENTI DELL'INFORMATICA | INF/01 | LEZIONI | 72 |
|
Il corso si pone l'obbiettivo di fornire le conoscenze di base allo studio dell'Informatica: le strutture fondamentali (come insiemi, grafi, alberi), le tecniche di specifica e dimostrazione (come ricorsione e induzione) e il linguaggio logico-matematico.
The course aims to provide the basic knowledge for the study of computer science: fundamental structures (such as sets, graphs, trees), specification and proof techniques (such as recursion and induction) and the logical-mathematical language.
Valutazione continua con svolgimento di test online bisettimanali, completata da un esame scritto e da un orale.
Continuous assessment with bi-weekly online tests, completed by a written and an oral exam.
Alla fine del corso gli studenti sapranno comprendere l'uso di strutture matematiche discrete per la modellazione di problemi, l'uso di induzione e ricorsione per la definizione di funzioni, e l'uso della logica matematica per la formalizzazione di proprietà. Inoltre avranno sviluppato capacità deduttive utili per la risoluzione di semplici problemi.
At the end of the course, students will be able to understand the use of discrete mathematical structures for problem modeling, the use of induction and recursion for the definition of functions, and the use of mathematical logic for the formalization of properties. They will also have developed deductive skills useful for solving simple problems.
I test online consentiranno di verificare il livello di comprensione degli argmenti introdotti nel corso. Gli esami scritti e orali saranno utili per verificare le capacità deduttive nella risoluzione di semplici problemi.
The online tests will allow to verify the students' level of understanding of the topics introduced in the course. The written and oral exams will be useful to verify the deductive skills in solving simple problems.
Durante le esercitazioni gli studenti potranno sviluppare capacità di risoluzione di problemi in gruppo.
During the exercises students will be able to develop problem solving skills in groups.
Non sono previste verifiche dei comportamenti.
Assesement criteria of behaviours are not envisaged.
- Il corso è costituito da lezioni frontali, da esercitazioni in gruppo e da test di valutazione erogati sulla piattaforma Moodle.
- Solo in caso di necessità le lezioni vengono trasmesse in streaming e vengono registrate.
- Il docente metterà a disposizione degli studenti le registrazioni delle lezioni dell'anno precedente.
- Le lezioni frontali si svolgono con uso di slide.
- Le esercitazioni si svolgono in aula: gli studenti svolgono gli esercizi proposti, anche in gruppo, sotto la supervisione del docente e degli assistenti
- I test di valutazione vengono proposti ogni due settimane, e vengono svolti in aula usando computer o smartphone. Come preparazione a tali test il docente pubblicherà nei giorni precedenti a ciascun test un analogo "test di autovalutazione", che gli studenti potranno ripetere un numero illimitato di volte.
- L'interazione con il docente avviene con colloqui (in orario di ricevimento o su appuntamento) e tramite posta elettronica.
- Sulla pagina web del corso (sulla piattaforma Moodle) vengono pubblicati progressivamente i lucidi presentati in ogni lezione, con riferimenti ai corrispondenti argomenti nella dispensa del corso. Vengono anche pubblicati i testi degli esercizi proposti per le esercitazioni e i test di autovalutazione, nonché i link alle registrazioni delle lezioni dello scorso anno.
- The course consists of lectures, group exercises and assessment tests delivered on the Moodle platform.
- Only if necessary, the lessons are streamed and recorded.
- The recordings of the lessons of the previous year will be made available by the lecturer.
- The lectures are held with the use of slides.
- The exercises take place in the classroom: students solve the exercises, even in groups, under the supervision of the teacher and assistants.
- Assessment tests are offered every two weeks, and are taken in the classroom with a computer or smartphone. In preparation for these tests, the teacher will publish a similar "self-assessment test" in the days preceding each test, which students can take an unlimited number of times.
- The interaction with the teacher takes place through interviews (during office hours or by appointment) and by e-mail.
- The slides presented in each lesson are progressively published on the course web page (on the Moodle platform), with references to the corresponding topics in the lecture notes. The texts of the proposed exercises and the self-assessment tests are also published, as well as the link to the recordings of the previous year's lessons.
Teoria degli Insiemi: Notazione estensionale e intensionale; insiemi notevoli; inclusione e uguaglianza; operazioni su insiemi; diagrammi di Eulero-Venn; leggi sugli insiemi e dimostrazioni per sostituzione; insiemi di insiemi; prodotto Cartesiano.
Relazioni: Relazioni come sottoinsiemi; operazioni su relazioni; relazione opposta, relazione identità; composizione di relazioni e leggi; proprietà di relazioni (totale, univalente, iniettiva e surgettiva); teoremi di caratterizzazione; funzioni e biiezioni; sequenze di lunghezza fissata e di lunghezza arbitraria.
Relazioni su un insieme: Proprietà riflessiva, transitiva, simmetrica e anti-simmetrica; chiusura riflessiva, simmetrica e transitiva; relazioni di equivalenza e partizioni; relazioni di ordinamento; ordinamento lessicografico.
Grafi: Collegamento con le relazioni; grafi orientati e non; vicinato e grado dei nodi; handshaking lemma; rappresentazione grafica, con matrici e con liste di adiacenza; isomorphismo; cammini e connettività; cammini Euleriani e Hamiltoniani; alberi; grafi diretti aciclici (DAG); distanze.
Induzione e Ricorsione: Definizione di insiemi e di funzioni per induzione; principio di induzione sui naturali; induzione su stringhe, liste, alberi ed espressioni; principio di induzione strutturale; funzioni ricorsive; relazioni ben fondate e definizioni ricorsive ben date.
Calcolo Combinatorio: Cardinalità di un insieme; teorema su bigiezioni e cardinalità; cardinalità di insiemi notevoli; cardinalità dell'insieme delle funzioni, delle relazioni e delle permutazioni; principio delle buche e dei piccioni; combinazioni semplici; coefficiente binomiale; combinazioni con ripetizioni; principio di inclusione-esclusione; contare su alberi e su grafi.
Linguaggi Formali: Alfabeti, parole e linguaggi; operazioni su linguaggi; automi deterministici e non; grammatiche libere da contesto; ambiguità; relazione tra automi e grammatiche.
Cenni di Logica Matematica: Calcolo proposizionale, sintassi e semantica; tavole di verità e tautologie; formalizzazione di enunciati; leggi e dimostrazioni per sostituzione; sistemi di dimostrazione; tecniche di dimostrazione e tautologie; cenni di Logica dei predicati; quantificatori; sintassi; formalizzazione di enunciati; interpretazioni e semantica; dimostrazioni di validità di formule.
Set Theory: Extensional and intensional notation; notable sets; inclusion and equality; operations on sets; Euler-Venn diagrams; laws on sets and proofs by substitution; sets of sets; Cartesian product.
Relations: Relations as subsets; operations on relations; opposite relation, identity relation; composition of relations and laws; properties of relations (total, single valued, injective and surjective); characterization theorems; functions and bijections; sequences of fixed length and of arbitrary length.
Relations on a set: reflexive, transitive, symmetric and anti-symmetric properties; reflexive, symmetric and transitive closure; equivalence relations and partitions; ordering relations; lexicographic ordering.
Graphs: Connection with relations; directed and undirected graphs; neighborhood and degree of nodes; handshaking lemma; graphical representation, representation with matrices and adjacency lists; isomorphisms; paths and connectivity; Eulerian and Hamiltonian paths; trees; directed acyclic graphs (DAG); distances.
Induction and Recursion: Definition of sets and functions by induction; induction principle on natural numbers; induction on strings, lists, trees and expressions; structural induction principle; recursive functions; well founded relations and well given recursive definitions.
Combinatorics: Cardinality of a set; bijections and cardinality theorem; cardinality of notable sets; cardinality of the set of functions, relations and permutations; pigeonhole principle; simple combinations; binomial coefficient; combinations with repetitions; inclusion-exclusion principle; counting on trees and graphs.
Formal Languages: Alphabets, words and languages; operations on languages; deterministic and non-deterministic automata; context free grammars; ambiguity; relations between automata and grammars.
Elements of Mathematical Logic: propositional calculus, syntax and semantics; truth tables and tautologies; formalization of statements; laws and proofs by substitution; proof systems; proof techniques and tautologies; elements of predicate logic; quantifiers; syntax; formalization of statements; interpretations and semantics; proofs of validity of formulas.
Dispensa del corso: Versione di Ottobre 2021
Attenzione: verrà pubblicata una nuova versione prima dell'inizio del corso.
Lecture notes of the course: Versione of Octorber 2021
Note: a new version will be published before the beginning of the course.
- Test di valutazione online bisettimanali
- Esame scritto
- Esame orale
Gli studenti che non raggiungono la sufficienza nei test di valutazione dovranno fare un test online aggiungivo prima di scritto e orale.
- Biweekly online assessment test
- Written exam
- Oral exami
Students who fail to pass the assessment tests will have to take an additional online test before written and oral exam.
Pagina web AA 2021/22:
https://elearning.di.unipi.it/course/view.php?id=268
Web page for AA 2021/22:
https://elearning.di.unipi.it/course/view.php?id=268