ECTS - University of Pisa
| Modules | Area | Type | Hours | Teacher(s) | |
| 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 provides basic knowledge for studying compuer science: the foundamental structures (like sets, graphs and trees), specification and proof techniques (like recursion and induction) and the basic logical-mathematical language.
Le conoscenze degli studenti sono verificate attraverso svariati test effecttuati durante le lezioni. Inoltre l'esame orale finale consiste di una prova orale. In tale prova, l'esaminatore farà delle domande per verificare le conscienze di base e fornirà allo studente degli esercizi per testare le capacità acquisite durante il corso.
The knowledge of the students are verified trhough several tests issued during the classes.
Moreover, the final examination consists of a discussion among professor and student. During the discussion, the professor check the aquired knowledge through some questions and check the capability acquired by the student providing some problem to solve.
Alla fine del corso, lo studente dovrà capire in linguaggio logico matematico ed essere capace di esprimersi in maniera rigorosa. Sperabilmente sarà in grado di maneggiare diverse tecniche di dimostrazione.
At the end of the course, the students should be able to understand the mathematical language and be able to specify problems in a rigours way. Hopefully, the students will be able to handle several proof techniques.
Le conoscenze degli studenti sono verificate attraverso svariati test effecttuati durante le lezioni. Inoltre l'esame orale finale consiste di una prova orale. In tale prova, l'esaminatore farà delle domande per verificare le conscienze di base e fornirà allo studente degli esercizi per testare le capacità acquisite durante il corso.
The knowledge of the students are verified trhough several tests issued during the classes.
Moreover, the final examination consists of a discussion among professor and student. During the discussion, the professor check the aquired knowledge through some questions and check the capability acquired by the student providing some problem to solve.
Lo studente sarà stimolato al lavoro di gruppo.
The student are enouraged to work in teams.
Il lavoro che gli studenti svolgono in gruppo è tipicamente controllato da un assistente.
The team work done by the students is usually checked by an assistant.
Nessuna conoscienza iniziale è richiesta.
None: the course provides basic knowledge.
Nessuno.
None.
Nessuno.
None.
Il corso consiste di tre lezioni per settimana. Due lezioni sono di didattica frontale. La terza lezione consiste o di un test o di una esercitazione da svolgere in gruppo.
Teoria degli Insiemi: Notazione estensionale, intensionale, insiemi notevoli, inclusione e uguaglianza, operazioni di base, diagrammi di Venn, leggi sugli insiemi; Coppie ordinate e prodotto Cartesiano.
Relazioni: Relazioni come sottoinsiemi, proprietà di base (totale, sv, iniettiva e surgettiva), funzioni e biiezioni; relazione inversa, relazione identità, composizione di relazioni e leggi; Triple, Quadruple e Tuple; Sequenze di lunghezza fissata e stringhe.
Relazioni su un insieme: Proprietà riflessiva, transitiva, simmetrica e anti-simmetrica. Relazioni di ordinamento (ordinamento lessicografico), relazioni di equivalenza e partizioni. Chiusura riflessiva, simmetrica e transitiva.
Grafi: Collegamento con le relazioni, rappresentazione grafica e con matrici di adiacenza, grafi orientati e non. Connessione, cammini (path-trail-walk), cicli Euleriani e Hamiltoniani. Alberi.
Induzione e Ricorsione: Principio di induzione sui numeri naturali, stringhe e alberi. Induzione strutturale. Grammatiche libere da contesto. Railroad diagrams per dare la sintassi di un linguaggio. Ricorsione su naturali, stringhe e alberi.
Calcolo Combinatorio: Cardinalità di un insieme, teorema su bigiezioni e cardinalità, cardinalità di insiemi notevoli, cardinalità dell'insieme delle funzioni e delle permutazioni. Pigeon Hole principle. Combinazioni semplici, coefficiente binomiale, triangolo di Tartaglia. Combinazioni con ripetizioni. Principio di inclusione-esclusione.
Ancora Grafi: Grado, handshaking lemma, distanza, colorazione, grafi bipartiti, clique. Automi non deterministici e linguaggio accettato.
Linguaggi Formali: Linguaggi come insiemi di stringhe. Automi e grammatiche libere da contesto.
Logica: Introduzione al calcolo proposizionale, formalizzazione di enunciati, sintassi e semantica (tabelle di verità), leggi, dimostrazioni per sostituzione. Introduzione alla logica del Primo ordine, formalizzazione di enunciati, sintassi e semantica, alcune leggi.
Relations: Relations as subsets, basic properties (total, single-valued, injective and surjective), functions and bijiections; opposite relations, identity relation, relational composition and laws; Couple, Triples, and tuples; Sequences of fixed and arbitrary lenght. Strings.
Relations over a set: basic property (reflexive, transitive, symmetric and antisymmetric). Ordering relation and equivalence relations. Closures.
Graphs: graphical representation, adjacency matrixes and lists, directed and non-directed graphs. Connectivity, walks, paths and trails, Eulerian e Hamiltonian cycles. Trees. Degree of a node, handshaking lemma, distances, coloration problems, bipartite graphs, cliques.
Induction and Recursion: Induction pricinciple on natural numbers, strings and trees. Structural Induction. Context free grammars. Recursion on natural numbers, strings and trees.
Combinatorics: Cardinality of a set, cardinality and bijiections, cardinality of noteworthy sets, cardinality of sets of functions and permutations. Pigeon Hole principle. Simple Combination, binomiale coefficient, Combination with repetition. Inclusion/exclusion principle.
Formal Languages: Languages as sets of stings. Automata and context free grammars.
Logics: propositional calculus, formalization, syntax and semantics (truth table), laws, proofs by substituion. First order logic, formalization, syntax and semantics. Some laws.
Dispense pubblicate online sulla pagine del corso.
Notes which are available online in the web page.
Gli studenti non frequentanti, possono comunque passare l'esame anche senza fare i test durante le lezioni. Durante gli appelli di esame devono passare un pre-test per essere ammessi alla prova orale.
Non-attending students can pass the exams without doing the test during classes. During the exams, they should pass a pretest in order to be admitted to the oral examination.
L'esame consiste di una prova orale. Per poter accedere alla prova orale, gli stundeti devono aver superato con successo i tests che vengono erogati durante il corso. Altrimenti, possono essere ammessi all'orale facendo un pretest durante l'appello di esame.
The exam consist of a discussion. In order to be admitted to the discussion, the students should have successfully passed the tests issued during the course. Otherwise, the students, can be admitted to the oral discussion by doing a pretest before the exam.
Nessuno.
None.
Nessuno.
None.
Nessuna.
None.
