First cycle
degree courses
Second cycle
degree courses
Single cycle
degree courses
School of Science
COMPUTER SCIENCE
Course unit
COMPUTABILITY AND ALGORITHMS
SCN1037673, A.A. 2015/16

Information concerning the students who enrolled in A.Y. 2015/16

Information on the course unit
Degree course Second cycle degree in
COMPUTER SCIENCE
SC1176, Degree course structure A.Y. 2014/15, A.Y. 2015/16
N0
bring this page
with you
Number of ECTS credits allocated 10.0
Type of assessment Mark
Course unit English denomination COMPUTABILITY AND ALGORITHMS
Website of the academic structure http://informatica.scienze.unipd.it/2015/laurea_magistrale
Department of reference Department of Mathematics
Mandatory attendance No
Language of instruction Italian
Branch PADOVA
Single Course unit The Course unit can be attended under the option Single Course unit attendance
Optional Course unit The Course unit can be chosen as Optional Course unit

Lecturers
Teacher in charge PAOLO BALDAN INF/01
Other lecturers LIVIO COLUSSI

ECTS: details
Type Scientific-Disciplinary Sector Credits allocated
Core courses INF/01 Computer Science 10.0

Course unit organization
Period Second semester
Year 1st Year
Teaching method frontal

Type of hours Credits Teaching
hours
Hours of
Individual study
Shifts
Practice 2.0 16 34.0 No turn
Lecture 8.0 64 136.0 No turn

Calendar
Start of activities 01/03/2016
End of activities 15/06/2016
Show course schedule 2019/20 Reg.2014 course timetable

Examination board
Examination board not defined

Syllabus
Prerequisites: The course requires some familiarity with basic mathematical concepts such as relations, functions, sets, cardinality, partial orders, principles of induction.
There are no propaedeutical courses.
Target skills and knowledge: The aim of the course is to guide the student into some classic themes in the theory of computability and to complete and deepen the algorithmic knowledge acquired at undergraduate level. For the first part, starting from a mathematical analyisis of the intuitive concept of an effective procedure, the class of effectively computable functions is formally introduced, and a theory of undecidability and recursion is developed. For the second part, some algorithmic techniques are presented, for the elaboration of fundamental structures such as graphs, strings and geometric objects. Also multithreaded and randomized algorithms are discussed. More generally, the course is intended to improve the formalization, reasoning and problem solving skills of the student.
Examination methods: The exam consists of a written test, mainly focused on exercises concerning the theory of computability, and in an oral discussion focussed on algorithmic themes.
Assessment criteria: The written test contains exercises designed to test the student's ability to use concepts and proof techniques, learnt during the course, for the solution of new problems. The oral test verifies the acquired knowledge and the depth of understanding of the topics discussed during the lessons, by requiring the presentation of known concepts and proofs.
Course unit contents: The course is divided into two parts, the first focused on computability theory, and the second devoted to algorithmic themes.

As regards the theory of computability, the following topics will be developed:

- Algorithms and the concept of effective procedure. Register machines (URM). Partial recursive functions. Equivalences between computational models. Universality of computational models. Church's thesis.

- Enumeration of computable functions. Existence of non-computable functions: diagonalization techniques. The parameter theorem. Universal programs.

- Decidable, undecidable and semidecidable problems. Undecidability of the halting problem. Reduction techniques. Other undecidable problems.

- Recursive and recursively enumerable sets. Rice and Rice-Shapiro theorems.

- Functionals. Recursive definitions. Partial orderings, monotone functions and fixed points. Recursive functional. Myhill-Sheperdson's theorem. First recursion theorem. Second recursion theorem.

The deepening of algorithmic techniques will focus on:

- Graph algorithms. Breadth-first and depth-first visit. Topological sort. Strongly connected components.

- String algorithms. Comparison based algorithms (Knuth, Morris and Pratt, Boyer, Moore and Yao, Corasich). Semi numerical algorithms (ShiftAnd and Fingerprint Rabin Karp). Suffix trees and Ukonnen algorithm for their construction in linear time.

- Multithreaded Algorithms.

- Computational Geometry. Representation of geometric objects and fundamental algorithms. Non-intersection test between segments. Convex hull: Graham algorithm and Jarvis algorithm. Finding the poligonal region that contains a given point.

- Randomized algorithms. Rendering algorithm. Routing algorithm.
Planned learning activities and teaching methods: The course consists of lectures and exercises.
Additional notes about suggested reading: Web page for computability theory: http://www.math.unipd.it/~baldan/Computabilita
Material for the algorithm part:
http://www.math.unipd.it/~colussi/CompAlgoritmi_2014-15
Textbooks (and optional supplementary readings)
  • Nigel Cutland, Computability. An Introduction to Recursive Function Theory. --: Cambridge University Press, 1980. Testo per la parte di computabilit√†. Cerca nel catalogo
  • T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduzione agli Algoritmi e Strutture Dati (3a edizione). --: McGraw-Hill Italia, 2010. Cerca nel catalogo