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 independently the study of theoretical arguments when formally described.

The course site contains a notable set of exercises, and students are encouraged to tackle them during self-study. Those in which the students encountered difficulties are addressed in the first part of the lesson, at the students' request. Also in the first part, the teacher invites the students to communicate any difficulties encountered in tackling the study of the topics of the previous lessons, so that we can discuss them together.

In the second part of the lesson, new topics are addressed and exercises relating to them are often indicated, among those present on the course exercises page or new ones (which will eventually increase the set of available exercises). 

As in the previous year, we will try to organize numerous ongoing tests, the evaluation of which will allow you to be exempted from taking part of the final exam.

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.

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

The work of the computer scientists in a globalized world.

The majority of texts are in electronic format and can be downloaded from the following web page:

http://www.dmi.unict.it/barba/FONDAMENTI/PROGRAMMI-TESTI/programmaAAcorrente.html

The exam consists of a written and an oral exam (the latter optional).

In the written exam, questions of both a theoretical nature and exercises are proposed.

The written exam is generally composed of three subparts: the first, divided into three questions (the first usually of a theoretical nature), is based on the first part of the program.

Compatibly with the relatively subjective nature of the concept of "difficulty", the three questions are proposed in order of difficulty.

Similarly for the second part of the writing.

The third part instead consists of a single exercise or question which can focus on the first or second part of the program, but in any case on topics not taken into consideration by the two previous parts.

A sufficient assessment of the written exam allows you to accept the grade as final or to access, upon request, the optional oral exam which will contribute to the final assessment.

NOTE. Verification of learning can also be carried out electronically, should conditions require it.

A web portal has been prepared containing all the texts of the writings of previous years:

http://www.dmi.unict.it/barba/FONDAMENTI/ESAMI/AppelliPassati/index.html

The solutions to the exercises proposed for the exams, together with many others, with related solutions, can be found in another specially developed portal:

http://www.dmi.unict.it/barba/FONDAMENTI/ESERCIZI/index.html