Scheda programma d'esame
FOUNDATIONS OF COMPUTER SCIENCE
FILIPPO BONCHI
Academic year2020/21
CourseCOMPUTER SCIENCE
Code728AA
Credits9
PeriodSemester 1
LanguageItalian

ModulesAreaTypeHoursTeacher(s)
FONDAMENTI DELL'INFORMATICAINF/01LEZIONI72
FILIPPO BONCHI unimap
Obiettivi di apprendimento
Learning outcomes
Conoscenze

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.

Knowledge

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.

Modalità di verifica delle conoscenze

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.

Assessment criteria of knowledge

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.

Capacità

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.

Skills

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.

Modalità di verifica delle capacità

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.

Assessment criteria of skills

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.

Comportamenti

Lo studente sarà stimolato al lavoro di gruppo.

Behaviors

The student are enouraged to work in teams.

Modalità di verifica dei comportamenti

Il lavoro che gli studenti svolgono in gruppo è tipicamente controllato da un assistente.

Assessment criteria of behaviors

The team work done by the students is usually checked by an assistant.

Prerequisiti (conoscenze iniziali)

Nessuna conoscienza iniziale è richiesta.

Prerequisites

None: the course provides basic knowledge.

Corequisiti

Nessuno.

Co-requisites

None.

Prerequisiti per studi successivi

Nessuno.

Prerequisites for further study

None.

Indicazioni metodologiche

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.

Programma (contenuti dell'insegnamento)

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.

Syllabus

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.

Bibliografia e materiale didattico

Dispense pubblicate online sulla pagine del corso.

Bibliography

Notes which are available online in the web page.

Indicazioni per non frequentanti

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 info

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.

Modalità d'esame

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.

Assessment methods

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.

Stage e tirocini

Nessuno.

Work placement

None.

Altri riferimenti web

Nessuno.

Additional web pages

None.

Note

Nessuna.

Notes

None.

Updated: 02/02/2021 18:56