FOUNDATIONS OF COMPUTER SCIENCE

Basic knowledge of Computer Science foundational theories.

Ability of understanding the intrinsic meaning of theoretical aspects of Computer Science.

Ability of applying theoretical notions in applicative contexts.

Ability of evaluating, judging and communicating IT methodologies and techniques in the wider setting of foundational theories.

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 model-theory theorems. .
• Formal introduction to some limitative theorems: Goedel, Tarski, Church.
• Induction, complete induction, well-founded induction and their use in proofs of correctness for programs.
• Induction-Recursion correspondence: a hint.
• A decidable fragment of first-order logic: Horn clauses and a sketchy introduction to Prolog.

Programming-languages semantics:

• Structured Operational Semantics