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

ModulesAreaTypeHoursTeacher(s)
FONDAMENTI DELL'INFORMATICAINF/01LEZIONI72
ALESSIO CONTE unimap
ROBERTO GROSSI unimap
Obiettivi di apprendimento
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.

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.

Updated: 11/09/2020 18:45