Ateneo - UPO

The essence of this course is reasoning about computer science itself. It gives master graduates a distinctive depth and width of vision and provides them with powerful and widely applicable technical and cognitive tools. The course concentrates on the meaning of computing, through the analysis of models of computation and of their power, on the inherent hardness of problems (not of single algorithms), relating them to each other from the point of view of the resources they require. Instead of offering techniques and tools to implement systems and solve problems, the course rather investigates whether computers can do anything: the answer is no, in some cases computer solving is utterly impossible, in others the time and memory requirements are prohibitive. Being aware of the limits of the tools that one uses is essential in order to be able to set reasonable goals, resizing requests as needed, accepting approximate solutions. The answers obtained in this course are completely general, valid and meaningful in any field of computer science. In particular, they motivate and validate from a theoretical point of view the adoption of techniques typical of Artificial Intelligence.

Main text: Thomas A. Sudkamp, Languages and Machines, Pearson International Edition, 2006. For some (few parts): C. Papadimitriou, Computational Complexity, Addison-Wesley, 1994. Reference on NP-completeness: Garey-Johnson, Computers and Intractability, Freeman, 1979. Additional material is provided on the course's online site.

Knowledge and understanding:
The course introduces basic concepts of computability and structural complexity. The presentation is based on the Turing Machine model. Techniques for analysis and comparison of the expressiveness of computational models on one side, and of the hardness of problems on the other (simulation, diagonalisation, dove-tailing and reduction) are explained. They are applied in both domains of computability and complexity, to achieve classical results such as Church's thesis, the existence and some properties of undecidable problems, properties of Turing-complete languages and formalisms, the justification of the use of big-O in complexity, properties of problem hierarchies with respect to their difficulty, the existence of NP-complete problems and the powerfulness of the resource space versus time.
Applying knowledge and understanding:
- comparing models of computation
- applying methodologies for analyzing the inherent hardness of problems
- in particular: ability to discern the context in which each of the proof techniques (simulation, reduction and diagonalization) is best applied
- ability to apply the mentioned techniques to simple cases
As a by-product, students will consolidate their own programming skills.

Making judgements:
The student will acquire technical and cognitive tools that are powerful and of wide applicability, and will learn to recognize the limits of the tools used by computer scientists; the latter is a fundamental competence to be able to set oneself reachable objectives, appropriately reducing requests and accepting approximate solutions.
Communication skills:
In order to attain such objectives, the student will acquire a specific formal language. Moreover the students will increase their proficiency in the technical English of computer science.

Learning skills:
The students will sharpen the rigor of their own logical reasoning skills. Challenging the idea of omnipotence of computational devices, they will have a new point of view from which to revisit all that they have learned so far. Finally the technical and cognitive tools developed in this course can be applied to any area of computer science and therefore constitute an enrichment independently of the specific notions around which they were introduced.

Knowledge of the fundamental concept of programming, logic, analysis, and preferably computer architectures and formal languages. Java programming.

The course consists of theoretical classes and hands on activity in lab.
In class definitions and theorems (with proofs) are presented formally in order to communicate to students the notions, to work on the rigor of reasoning and to teach the formal terminology. In particular the techniques on which proofs are based are emphasized, and their applications in different areas are compared; this serves the double aim of helping the students to conceptualize these techniques and of stimulating them to acquire the techniques as a tool for wider usage.
Moreover the students are encouraged to participate suggesting the application of techniques, developing reasoning by recalling fundamental concepts and results previously presented in the course.
In lab the students are requested to realize software projects in order to understand in depth the models studied and in order to fully comprehend the constructive character of almost all the proofs of the theorems presented in this course. Participation to lab activity replaces the possibly passive attendance to classes with a necessity to actively measure oneself with the notions and the results studied and especially with the arguments presented.

On the DIR platform students find:
all the practical information on the course, information on textbooks and the program, additional didactic material, for each class the subject treated and bibliographic references (written soon after the class), specifics and if necessary additional material for the activity in lab. This way, students that attend classes can review and consolidate subjects presented in class or activities proposed in lab; students that don't attend classes can keep abreast of the course or study autonomously.

Since the recommended textbook is in English, preparing for the exam will give the students the possibility to practice the technical language of computer science.

Hands-on activity requires active participation of the students, and leads the latter to ask themselves questions (and, as a consequence, often to ask questions to the instructor); this way it allows a regular monitoring of the way the subject is being understood.
The activity in lab fundamentally requires programming in Java: therefore, beyond its importance as a means to reach the formative objectives of the course, it is in general an additional moment to consolidate the students' programming skills and to refine their competences as Java programmers.

Students with physical disabilities, Learning Disabilities or Special Education Needs can request
specific services and tools via the Staff Sviluppo e Coordinamento Carriere e Servizi alle Studentesse
e agli Studenti, consulting the University webpage: https://www.uniupo.it/en/services/services-
students-physical-or-learning-disabilities
Students with disabilities, learning disabilities or special education needs, once they have contacted
the University Staff, can refer to the tutor in charge of the course to define the examination
modalities, concerning academic aspects.

Oral exam
The oral exam consists normally of three questions: one general introductory question on formal methods, one more specific on computability aspects and the third on complexity. The goal is to ascertain whether the student has understood the fundamental concepts and can present them with a formal language, and has acquired the methodological instruments and can apply them. Therefore, on one hand the student is requested to present definitions and proofs, and on the other hand the student must reason on slightly modified contexts or explore connections among different parts of the course. During the interview the level of formality, both in expression and reasoning, is also ascertained.
The number of questions can vary, depending on the quality of the answers (with respect to clarity, completeness, precision, formality,...), since the final aim is to ascertain that the formative objectives have been reached.

Introduction to Computability:
The first part of the course aims at the acquisition of formal techniques and analysis tools, and to the formalization of the concept of computability (Turing Machines, formal definitions and operation. Comparison of different machine models. Simulation technique. Turing computable functions).
Following, the course offers a basilar formalization of classes of hardness of problems, based solely on computability aspects, with no reference to resource limitations. (Recursive and recursively enumerable sets. Enumerators).
Then the presentation moves to general results and, following the track of historical evolution, gives a first connection to present-day computer science (Church thesis, Turing machines coding and universal Turing machine).
Then negative results underline the limits of computer science tools; moreover tools for the extension of such negative results are provided (Diagonalization. Existence of non computable functions. Proofs that sets are not enumerable or not recursively enumerable. Undecidability, Halting problem and reductions).
The introduction to computability is concluded relating the tools and results learned to every-day computer science or to subjects known to students from other courses (Importance of the "while" construct in programming languages. Comparison of Turing machines with weaker models of computation, such as finite state and pushdown automata, unrestricted and context sensitive grammars, and recursivity).

Introduction to structural complexity: The second part of the course relativizes the analysis and the formalization carried out in the introduction to computability, to a more realistic situation in which resources are limited; it focuses in particular on the relation among classes of problems distinguished in terms of computational hardness, and on the meaning of nondeterministic classes. (Complexity measures, models and problem representation. Linear speedup theorem. Non deterministic Turing machines and the meaning of non determinism. Classes P and NP, problems in NP, polynomial time reductions, NP-completeness, SAT and Cook's theorem Space complexity, deterministic space vs. deterministic time, non deterministic space vs. time; Savitch's theorem. Existence of problems of arbitrary complexity and hierarchy theorems, time and space constructible functions).

Knowledge
Concept of model of computation, Turing machine, computable function, recursive and recursively enumerable sets, time complexity classes, P and NP and their mutual relationship, NP-completeness, space complexity; simulation, reduction and diagonalization techniques; existence of undecidable problems and of problems that require too many computational resources to be feasible in practice

Competencies and skills
Explain what is a computational model and in particular give a formal definition of the Turing machine.
Apply the simulation technique to examples introduced in the course, but given the variety of such examples, the students will acquire the flexibility to extend it to other situations and contexts.
Define and explain the concepts of computable function, recursive and recursively enumerable sets, that is the computability properties of sets and functions.
State and explain the meaning of Church's Thesis.
Define time and space complexity classes.
Define and explain the concept of non-determinism.
Define the concept of NP-completeness and its importance.
Analyze the relationship between complexity classes as a function of amounts of resources.
State, explain and prove the theorems presented in class.
Analyze the function of specific hypotheses in the theorems presented in class.
Show applications of the reduction technique in the appropriate area of usage in computability or complexity.
Show applications of the diagonalization technique in the appropriate area of usage in computability or complexity.
Propose the right technique to be used on a specific variation of some problem proposed in class.