Università di Pisa - Valutazione della didattica e iscrizione agli esami

Scheda programma d'esame

FOUNDATIONS OF COMPUTER SCIENCE

ALESSIO CONTE

Academic year2022/23
CourseCOMPUTER SCIENCE
Code728AA
Credits9
PeriodSemester 1
LanguageItalian

Modules

Area

Type

Hours

Teacher(s)

FONDAMENTI DELL'INFORMATICA

INF/01

LEZIONI

ALESSIO CONTE unimap

ROBERTO GROSSI unimap

Esporta in pdf

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 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.

Modalità di verifica delle conoscenze

Verifica continua attraverso test bi-settimanali, completati da un esame scritto e un orale.

Assessment criteria of knowledge

Continuous assessment with biweekly online tests, completed by a written and an oral exam.

Capacità

Alla fine del corso, lo studente è in grado di comprendere l'uso di strutture discrete matematiche per la modellazione di problemi computazionali, l'uso dell'induzione e della ricorsione per la definizione di funzioni, e l'uso della logica matematica per la formalizzazione delle proprietà. Verranno inoltre sviluppate delle abilità deduttive per la risoluzione di problemi elementari.

Skills

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.

Modalità di verifica delle capacità

I test permetteranno di veridicare il livello di comprensione dello studente nei riguardi degli argomenti trattati a lezione. L'esame scritto e orale permetteranno di verificare le capacità deduttive nella risoluzione di semplici problemi.

Assessment criteria of skills

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.

Comportamenti

Durante gli esercizi, ciascun studente verrà coinvolto in un gruppo di lavoro per la risoluzione di problemi.

Behaviors

During the exercises students will be able to develop problem solving skills in groups.

Modalità di verifica dei comportamenti

Non è prevista una modalità di verifica dei comportamenti

Assessment criteria of behaviors

Assesement criteria of behaviours are not envisaged.

Prerequisiti (conoscenze iniziali)

Matematica insegnata nei licei e negli istituti tecnici.

Prerequisites

Mathematics taught in high schools.

Indicazioni metodologiche

Il corso è costituito da lezioni frontali, da esercitazioni in gruppo e da test di valutazione erogati sulla piattaforma Moodle. Se necessario le lezioni vengono trasmesse in streaming e vengono registrate.
Le lezioni frontali si svolgono con uso di slide.
Le esercitazioni si svolgono in aula (o aula virtuale): 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 online con 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é le eventuali registrazioni delle lezioni.

Teaching methods

The course consists of lectures, group exercises and assessment tests delivered on the Moodle platform. If necessary, the lessons are streamed and recorded.
The lectures are held with the use of slides.
The exercises take place in the classroom (or virtual 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 online 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 any recordings of the lessons.

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

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.

Bibliografia e materiale didattico

Dispense del corso: versione di settembre 2022.

Bibliography

Lecture notes of the course: Version of September 2022.

Modalità d'esame