- Docente: Paolo Felli
- Credits: 6
- SSD: INF/01
- Language: English
- Moduli: Paolo Felli (Modulo 1) Enrico Malizia (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 05, 2024 to May 02, 2024
-
from May 08, 2024 to Jun 06, 2024
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 of the main fields of theoretical computer science.
The first module deals with the foundations of computers, with a focus on a specific architecture, as well as with the relational model for database systems with its query language.
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:
Elements of logic
- Propositional logic
- Circuit Models of Computation and Boolean Algebra
Computer Architectures
- Organisation of computer systems and binary systems.
- Logical gates, combinatorial and sequential circuits. Architectures.
Databases
- 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 (Boolean functions, Support Vector Machines, neural networks)
Readings/Bibliography
Slides of the lectures will be provided. For further reading we suggest the following textbooks:
- Andrew S. Tanenbaum - Todd Austin. Structured Computer Organization 6th edition. Pearson. 2013.
- 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). Written exams are then discussed in a brief oral test.
In case the exam will be online the theoretical questions will be reserved for the oral test.
Teaching tools
The following material will be provided: slides of the lectures.
Office hours
See the website of Paolo Felli
See the website of Enrico Malizia