- Docente: Paolo Felli
- Credits: 6
- SSD: INF/01
- Language: English
- Moduli: Paolo Felli (Modulo 1) Alina Sirbu (Modulo 2)
- Teaching Mode: Traditional lectures (Modulo 1) Traditional lectures (Modulo 2)
- Campus: Bologna
- Corso: First cycle degree programme (L) in Genomics (cod. 9211)
-
from Mar 03, 2025 to Apr 14, 2025
-
from Apr 16, 2025 to May 29, 2025
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 learning modules and provides an introduction to some main fields of computer science.
The first module deals with the study of relational databases, database query languages, database management systems and database design.
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 by using concepts and tools from each of the aforementioned fields.
MODULO 1:
Databases:
- Propositional logic
- Boolean Algebra
- Relational model and Relational Algebra
- Relational DBMS and the SQL language
- Database design and the ER language
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)
Machine Learning:
- The PAC model of the complexity of learning
- Complexity estimations for some learning problems
Readings/Bibliography
Slides of the lectures will be provided. For further reading we suggest the following textbooks:
- Database System Concepts (4th edition). Silberschatz, Korth, Sudarshan. McGraw Hill, 2002.
- 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
The exam consists of a written test, including both open theoretical questions and exercises.
Teaching tools
Slides will be provided and, when possible, recordings too.
Office hours
See the website of Paolo Felli
See the website of Alina Sirbu