- Docente: Paolo Pistone
- Credits: 6
- SSD: INF/01
- Language: English
- Moduli: Paolo Pistone (Modulo 1) Francesco Gavazzo (Modulo 2)
- Teaching Mode: Traditional lectures (Modulo 1) Traditional lectures (Modulo 2)
- Campus: Bologna
- Corso: First cycle degree programme (L) in Genomics (cod. 9211)
Learning outcomes
The course aims to provide the student with some additional knowledge in computer science beyond the one from basic courses. This is meant to allow students to gain greater awareness of the potential of modern computing and communication systems. In particular, some concepts pertaining to operating systems, computer networks, computer security, and databases will be provided.
Course contents
The course consists of two independent learning modules and provides an introduction to some of the main fields of theoretical computer science.
The first module deals with logical foundations of physical computational machines, as well as with applications of logic in computer science.
The second module introduces the fundamental concepts of computational complexity as well as their application for the analysis of cryptographic protocols and machine learning algorithms.
At the end of the course students will be able to discuss theoretical issues and solve some practical problems in computer science by using concepts and results from each of the aforementioned fields.
Module 1
Logical Foundations
- Propositional and Predicate Logic
- Circuit Models of Computation and Boolean Algebra
Physical Computing Machines
- Introduction to Physical Computing Machines
- From Circuits to Computers
- From Computers to Programming
Logic in Computer Science
- Artificial Intelligence and Symbolic Reasoning
- Relational Databases
Module 2:
Computational complexity:
- Mathematical models of computation, Turing machines
- Asymptotic notation, complexity classes, the P=NP problem
- Some intractable problems (integer factorization, discrete logarithm)
Cryptography:
- Basics of modular arithmetics
- Overview on cryptography (one-way functions, public/private keys cryptosystems)
- Examples of public key cryptosystems (RSA, DHKE)
- Digital signatures
Machine Learning:
- The PAC model of the complexity of learning
- Complexity estimations for some learning problems (Boolean functions, Support Vector Machines, neural networks)
Readings/Bibliography
Slides of the lectures will be provided. For further reading we suggest the following textbooks (selected chapters will be indicated during the lectures):
First module:
- Robert Sedgewick, Kevin Wayne: Computer Science: An Interdisciplinary Approach, Pearson Education US (2016)
- Dirk van Dalen: Logic and Structure, Universitext; 5th edition (2013)
- Michael Huth, Mark Ryan: Logic in Computer Science: Modelling and Reasoning about Systems, Cambridge University Press (2012)
Second module:
- Guttag J.V. Introduction to Computation and Programming Using Python. Revised and Expanded Edition. MIT Press, Cambridge, 2013.
- Sipser, M. Introduction to the theory of computation. Second Edition. Thomson Course Technology, USA, 2006.
- Paar, C. and Pelzl, J. Understanding Cryptography. Springer-Verlag, Berlin-Heidelberg, 2010.
- Mohri, M., Rostamizadeh, A., Talwalkar, A. Foundations of Machine Learning, MIT Press, Cambridge, Massachussets 2018.
Teaching methods
Lectures.
Assessment methods
Daily sheets and oral examination.
Teaching tools
The following material will be provided: slides of the lectures.
Office hours
See the website of Paolo Pistone
See the website of Francesco Gavazzo