FOUNDATIONS OF COMPUTER SCIENCE F - N
Academic Year 2022/2023 - Teacher: Franco BARBANERAExpected Learning Outcomes
Knowledge and understanding: students will acquire knowledge relative to some of the most important formal theories that are fundamental in Informatics. He will understand how all the aspects of applied Informatics have been realized or influenced by knowledge developed at a theoretical level.
Applying knowledge and understanding: students will acquire the ability of applying theoretical notions in applicative contexts.
Making judgements: students will be stimulated to search independently which aspects of theoretical computer science are used in topics covered in more applicative courses he followed in the same year. They will also be stimulated to understand how topics of other different courses could be formalized in mathematical logic.
Communication skills: students will acquire the necessary communication skills and expressive ability in order to express in a formal and non-ambiguous way scientific arguments.
Learning skills: students will get the competences to tackle independentlythe study of theoretical arguments when formally described.
Course Structure
Each lesson is divided into two parts. The first one (about one third of the time) is devoted to the solution of exercises and to the clarification of unclear topics of the previous lessons. The second part is devoted to the explanation of new topics.
Should teaching be carried out in mixed mode or remotely, it may be necessary to introduce changes with respect to previous statements, in line with the programme planned and outlined in the syllabus.
Detailed Course Content
Elements of Theory of formal languages:
- Alphabet, string, language. Operations on languages. Regular expressions. Cardinality of languages.
- Chomsky grammars. Type 0,1,2,3 grammars. Chomsky Hierarchy. Bakus normal form.
- What does it mean ''to compute''
- Recognition and decision of languages. Automata.
- Finite state automata, deterministic and nondeterministic.
- Pumping Lemma for FSA.
- Context-free languages: a hint.
Computational models and computability theory:
- Turing machines and universal Turing machine.
- Introduction to functional programming and the lambda-calculus
- free and bound variables, alpha-conversion, substiturions, beta-reduction. Definition of formal system, Church numerals. Lambda-definable functions.
- Lambda-definability of recursive functions. Uniqueness of normal form. Consistency of beta-conversion theory.
- The formalism of primitive recursive functions and partial functions.
- Informal introduction to recursion theory and some fundamental results.
- A logic-based computational model: a sketchy introduction to logic programming.
Codes and representation of numerical information:
- Codes and two-complements representation of integers.
- Strings vs Numbers
Abstract machines.
- Abstract machine definition.
- Implementation of abstract machines; layered organization of computation systems.
Logics:
- Formal systems. Admissible and derivable rules. Some properties of formal systems. Consistency.
- Propositional logic definition and main properties. Deduction theorem.
- Semantics of propositional logics. Soundness and completeness.
- Natural deduction for propositional logics-
- The correspondence proofs as programsLa corrispondenza dimostrazioni-programmi
- First-order logic: language and semantics.
- Substitutions, natural deduction, axiomatic system.
- Statements of fundamental theorems.
- Arithmetic and group theory formalizations.
- Statements of some fundamental theorems. .
- Induction-Recursion correspondence: a hint.
Programming-languages semantics:
- Structured Operational Semantics
General
- The work of the computer scientists in a globalized world.
Textbook Information
Most of the texts are in electronic format and are downloadable from the following web page
Course Planning
Subjects | Text References | |
---|---|---|
1 | Introduzione alla teoria dei linguaggi formali. Definizioni di alfabeto, stringa, linguaggio. Espressioni regolari | Link ai testi |
2 | Enumerazione di Sigma*. Non numerabilita' dei linguaggi su un alfabeto Sigma. Numerabilita' dei programmi di riconoscimento dei linguaggi. Introduzione alle Grammatiche di Chomsky: Definizione, Classi di grammatiche. | Link ai testi |
3 | BNF. Cosa significa computare. Automi. Automi a stati finiti e corrispondenza con linguaggi regolari. | Link ai testi |
4 | Linguaggio decidibili e semidecidibili. Introduzione al Pumping Lemma | Link ai testi |
5 | Automi a stati finiti non deterministici. Punping Lemma: enunciato e dimostrazione. Induzione e suo utilizzoper dimostrare proprieta' di programmi. | Link ai testi |
6 | Uso del Pumping Lemma. Alcune caratteristiche dei linguaggi context-free. Alberi di derivazione sintattica. Esistenza di linguaggi non generabili da grammatiche: metodo di diagonalizzazione. | Link ai testi |
7 | Introduzione alle macchine di Turing. Definizione formale di Macchina di Turing. Esempio di macchina di Turing. | Link ai testi |
8 | Induzione completa ed esempio di uso per dimostrare proprieta' di programmi. Trasduttori. Esempi di trasduttori. Macchina di Turing Universale. | Link ai testi |
9 | Codici. Rappresentazione informzione numerica. Rappresentazione posizionale e algoritmi di conversione di base. Codici a lunghezza fissa e variabile. Codici ad espansione. | Link ai testi |
10 | Definizione di rappresentazione degli interi in complemento alla base. Proprieta' della rappresentazione in complemento a due e loro dimostrazioni. Introduzione alla programmazione funzionale. | Link ai testi |
11 | Intro alla programmazione funzionale ed al lambda-calcolo Lambda-termini; beta-riduzione (informale); | Link ai testi |
12 | Variabili libere e legate; Alfa-conversione; Sostituzione; Forme normali e loro unicita'; strategie di riduzione; Introduzione alle funzioni lambda-definibili; | Link ai testi |
13 | Lambda-definibilita' di algoritmi che calcolano funzioni. Teorema del punto fisso (enunciato). Lambda-definibilita' di algoritmi ricorsivi. Introduzione ai sistemi formali. Esempio di sistema formale: alfa-conversione. | Link ai testi |
14 | Sistemi formali. Principali definizioni correlate ai sistemi formali. Esempio di sistema formale: Combinatory Logic | Link ai testi |
15 | Logica Proposizionale alla Hilbert. Teorema di deduzione. Semantica della Logica Proposizionale. Teorema di correttezza e completezza (enunciato), | Link ai testi |
16 | Logica Proposizionale in deduzione naturale. Corrispondenza deduzioni-programmi. | Link ai testi |
17 | Logica del primo ordine: segnatura, fbf, strutture, semantica. | Link ai testi |
18 | Regole ammissibili e derivabili. Deduzione naturale per logica primo ordine. | Link ai testi |
19 | Correttezza e completezza; Assiomi non logici dell'aritmetica (PA) e dei gruppi. Non esistenza di formalismi per tutte e sole le funzioni totali. | Link ai testi |
20 | Alcuni risultati fondamentali di Teoria della Ricorsivita'. Problema della fermata. Isomorfismo di Cantor. Codifica di stringhe con numeri naturali. Definizione di macchina astratta. Corrispondenza Macchine astratte e linguaggi. | Link ai testi |
21 | Realizzazione di Macchine Astratte. Gerarchie di Macchine Astratte. Primo teorema di Incompletezza di Goedel e schema di dimostrazione. Enunciato secondo teorema di Incompletezza di Goedel. | Link ai testi |
22 | Teorema di Church. Semidecisione per relazione di derivabilita'; Clausole di Horn. Cenni di Prolog. Induzione ben-fondata. | Link ai testi |
23 | Introduzione alla semantica formale dei linguaggi di programmazione. Semantica Operazionale Strutturata dei linguaggi imperativi: il linguaggio WHILE | Link ai testi |
24 | Alcuni risultati fondamentali. Il lavoro dell'informatico nel mondo globalizzato. | Link ai testi |