# Matematica | COMPUTABILITY THEORY

## Matematica COMPUTABILITY THEORY

 0512300045 DIPARTIMENTO DI MATEMATICA EQF6 MATHEMATICS 2022/2023

 YEAR OF COURSE 3 YEAR OF DIDACTIC SYSTEM 2018 SPRING SEMESTER
SSD CFU HOURS ACTIVITY TYPE OF ACTIVITY MAT/01 6 48 LESSONS COMPULSORY SUBJECTS, CHARACTERISTIC OF THE CLASS
 GIACOMO LENZI T
ExamDate
TEORIA DELLA COMPUTABILITA'03/04/2023 - 14:00
Objectives
1) KNOWLEDGE AND UNDERSTANDING CAPABILITY: PROVIDE THE BASIC INFORMATION ON THE CONCEPT OF COMPUTABLE FUNCTION AND SET, AND ON OTHER COMPUTATIONAL MODELS OF TECHNICAL AND CULTURAL IMPORTANCE.

2) CAPABILITY OF APPLYING KNOWLEDGE AND UNDERSTANDING: AN EXAMPLE OF APPLICATION OF KNOWLEDGE IS THE THEORY AND PRACTICE OF PROGRAMMING.

Prerequisites
IT IS REQUIRED TO HAVE A CERTAIN MATHEMATICAL MATURITY WHICH CAN BE OBTAINED WITH TWO YEARS OF UNDERGRADUATE MATHEMATICS STUDIES.
Contents
IT IS EXPECTED TO COVER THE FOLLOWING TOPICS:
1) COMPUTATIONAL COMPLEXITY
2) ALGORITHMS
3) STRAIGHTEDGE AND COMPASS
4) CLASSICAL PROBLEMS
5) GOLDEN RATIO
6) FIBONACCI NUMBERS
7) NEUSIS AND ORIGAMI
8) TRANSDUCER AUTOMATA
9) CARDINALITY
10) MACHINES TO PLOT CURVES
11) REGULAR LANGUAGES
12) FORMAL GRAMMARS
13) KLEENE THEOREM
14) GENERALIZED AUTOMATA
15) BOOLEAN FUNCTIONS
16) LOGICAL GATES
17) PEANO TRIPLES
18) RECURSIVE FUNCTIONS
Teaching Methods
THE MAIN METHOD IS GIVEN BY LESSONS AT BLACKBOARD. THE STUDENTS WHO FOLLOW THE COURSE MUST PRESENT A TOPIC RELATED TO THE COURSE IN A HALF HOUR SEMINAR.
Verification of learning
ORAL EXAMINATION INTENDED TO EVALUATE THE THEORETICAL AND PRACTICAL KNOWLEDGE OF THE ARGUMENTS TREATED IN THE LECTURES. THE SCORE GOES FROM 18 TO 30 CUM LAUDE FOR THOSE WHO PASS THE EXAM.
Texts
THE MAIN REFERENCES WILL BE: THE LECTURE NOTES WRITTEN BY THE STUDENTS, THE BOOK BY G. GERLA "WHAT A COMPUTER CAN DO?" (IN ITALIAN), AND THE LECTURE NOTES ON COMPUTABILITY THEORY BY L. SPADA. IF YOU DO NOT READ ITALIAN CONTACT THE TEACHER.