Foundations of Computer Science

Course objectives

General goals: Acquiring the basics of data science and machine learning. Specific goals: To make students aware of the theoretical and practical tools of data science and machine learning, as well as of their intrinsical limitations; to make students able to tackle real problems through the most appropriate tools. Knowledge and understanding: The course provides the basic notions, techniques and methodologies employed in data science and machine learning. It gives also the fundamental programming abilities needed to apply the theory to real-world scenarios. Applying knowledge and understanding: At the end of the course, students will be able to deal with real-world data science problems, from casting them into a theoretical framework to manipulating the actual data with the right software tools. Critical and judgmental abilities: Students will be able to select the techniques to be applied to the case at hand and to evaluate their performance. Communication skills: Students will we able to represent and communicate the information extracted from data, through the rational use of graphics and indicators. Ability of learning: Students will be able to learn autonomously both the theory and the practice of the field.

Channel 1
DANIELE GORLA Lecturers' profile

Program - Frequency - Exams

Course program
Automata and Languages: Regular languages, finite state automata and regular grammars. Context-free languages, context-free grammars and stack automata; Chomsky hierarchy. Calculability Theory: Turing Machines. Church-Turing thesis. Undecidable problems: the halting problem. Reduction between problems: a tool to demonstrate their indecidability or decidability. Examples of decidable and undecidable problems. Complexity Theory: Time and space complexity for Turing machines. Classes of complexity. Treatable problems and problems that are not proven to be intractable: the P and NP classes. Polynomial reductions and NP-completeness. Cook-Levin theorem and other NP-complete problems.
Prerequisites
Basic notions of algorithms, computational complexity (O notation), trees, graphs, first order logic
Books
M. Sipser, Introduction to the Theory of Computation, III edition. Engage Learning, 2012. A few topics are covered by chapter 9 of: J.E. Hopcroft, J.D. Ullman: Introduction to Automata Theory, Languages and Computation. Addison Wesley, 1979.
Frequency
Attendance is strongly suggested, because of the complexity of the topics covered
Exam mode
A written exam on the automata part and on oral exam on all the theory presented (definitions and proofs)
Lesson mode
Lectures in presence
  • Lesson code10595530
  • Academic year2024/2025
  • CourseApplied Computer Science and Artificial Intelligence
  • CurriculumSingle curriculum
  • Year3rd year
  • Semester1st semester
  • SSDINF/01
  • CFU6
  • Subject areaDiscipline Informatiche