Matematica | COMPUTABILITY THEORY

cod. 0512300045

COMPUTABILITY THEORY

	0512300045
	DIPARTIMENTO DI MATEMATICA
	EQF6
	MATHEMATICS
	2021/2022

PERCORSO SHARED STUDY PATHWAY

	YEAR OF COURSE 3
	YEAR OF DIDACTIC SYSTEM 2018
	SPRING SEMESTER

TEACHING UNITS

	SSD	CFU	HOURS	ACTIVITY	TYPE OF ACTIVITY
	MAT/01	6	48	LESSONS	COMPULSORY SUBJECTS, CHARACTERISTIC OF THE CLASS

	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

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.