- Docente: Paolo Pistone
- Credits: 6
- SSD: INF/01
- Language: Italian
- 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 in 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 provides an introduction to computational complexity and its application for the analysis of cryptographic protocols as well as 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:
Complexity:
- Mathematical models of universal computation, Turing machines
- Asymptotic notation, complexity classes, the P=NP problem
- Some intractable problems (prime factorization, discrete logarithm)
Cryptography and security:
- Basics of modular arithmetics
- Overview on cryptography (one-way functions, encryption systems, private/public key systems)
- Examples of public key cryptosystems (RSA, DHKE)
- Digital signatures
Machine Learning:
- The PAC model of learning complexity
- Estimating the complexity of some learning problems (e.g. 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, The 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