FOUNDATIONS OF COMPUTER SCIENCE F - N

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.

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. 
• Induction-Recursion correspondence: a hint.  

Programming-languages semantics:

• Structured Operational Semantics

General 

• The work of the computer scientists in a  globalized  world.

Most of the texts are in electronic format and are downloadable from the following web page

program and texts

Erasmus students and other non-italian speakers may ask to take an oral exam.

The assessment may also be conducted online, should the circumstances require it

For the assignment of grades for individual assessments, the following criteria are typically followed:

• Fail: The student has not acquired the basic concepts and is unable to complete the exercises.
• 18-23: The student demonstrates a minimal mastery of the fundamental concepts; their ability to present and connect content is modest, and they can solve simple exercises.
• 24-27: The student shows a good grasp of the course content; their ability to present and connect the content is good, and they solve exercises with few errors.
• 28-30 with honors: The student has acquired all course content and can present them comprehensively with a critical perspective; they solve exercises completely and without errors

Students with disabilities and/or learning disorders (DSA) must contact the instructor and the CInAP representative at DMI well in advance of the exam date to inform them of their intention to take the exam with the appropriate compensatory measures.

The following web site all the previous written examinations. 

scritti passati

Solutions of previous written examinations and many more exercises are present in 

esercizi