Computer science | ELEMENTS OF COMPUTATION THEORY

cod. 0512100018

ELEMENTS OF COMPUTATION THEORY

	0512100018
	DIPARTIMENTO DI INFORMATICA
	EQF6
	COMPUTER SCIENCE
	2017/2018

CURRICULUM METODOLOGICO Cohort 2015/2016

	OBBLIGATORIO
	YEAR OF COURSE 3
	YEAR OF DIDACTIC SYSTEM 2015
	SECONDO SEMESTRE

TEACHING UNITS

SSD	CFU	HOURS	ACTIVITY	TYPE OF ACTIVITY
INF/01	6	48	LESSONS	COMPULSORY SUBJECTS, CHARACTERISTIC OF THE CLASS
INF/01	3	24	LAB	COMPULSORY SUBJECTS, CHARACTERISTIC OF THE CLASS

	Objectives
	KNOWLEDGE AND UNDERSTANDING 1.ABSTRACT COMPUTING MODELS 2.TURING MACHINES 3.PROBLEMS THAT ARE SOLVABLE AND PROBLEMS THAT ARE NOT SOLVABLE 4.TIME COMPLEXITY 5.PROBLEMS THAT ARE COMPUTATIONALLY EASY AND PROBLEMS THAT ARE COMPUTATIONALLY HARD APPLYING KNOWLEDGE AND UNDERSTANDING THE STUDENT MUST BE ABLE TO ANALYSE THE BEHAVIOUR OF FINITE AUTOMATA AND TURING MACHINES. HE MUST ALSO BE ABLE TO DESIGN SIMPLE ABSTRACT COMPUTING DEVICES FOR THE SOLUTION OF DECISION PROBLEMS (QUESTIONS WITH A YES-OR-NO ANSWER).

KNOWLEDGE AND UNDERSTANDING
1.ABSTRACT COMPUTING MODELS
2.TURING MACHINES
3.PROBLEMS THAT ARE SOLVABLE AND PROBLEMS THAT ARE NOT SOLVABLE
4.TIME COMPLEXITY
5.PROBLEMS THAT ARE COMPUTATIONALLY EASY AND PROBLEMS THAT ARE COMPUTATIONALLY HARD

APPLYING KNOWLEDGE AND UNDERSTANDING
THE STUDENT MUST BE ABLE TO ANALYSE THE BEHAVIOUR OF FINITE AUTOMATA AND TURING MACHINES. HE MUST ALSO BE ABLE TO DESIGN SIMPLE ABSTRACT COMPUTING DEVICES FOR THE SOLUTION OF DECISION PROBLEMS (QUESTIONS WITH A YES-OR-NO ANSWER).

	Prerequisites
	KNOWLEDGE OF DISCRETE MATHEMATICS, LOGIC, AND ALGORITHMS. DISCRETE MATHEMATICS: SETS, SET OPERATIONS, CARDINALITY, CARTESIAN PRODUCT, FUNCTIONS. LOGIC: PREDICATES AND QUANTIFIERS, PROOF METHODS AND STRATEGY. ALGORITHMS: ASYMPTOTIC NOTATION.

	Contents
	COMPUTATIONAL MODELS: DETERMINISTIC AND NONDETERMINISTIC FINITE AUTOMATA. REGULAR EXPRESSIONS. CLOSURE PROPERTIES OF REGULAR LANGUAGES. KLEENE’S THEOREM. THE PUMPING LEMMA FOR REGULAR LANGUAGES. SINGLE-TAPE DETERMINISTIC TURING MACHINES. THE LANGUAGE RECOGNIZED BY A TURING MACHINE. VARIANTS OF TURING MACHINES AND THEIR EQUIVALENCE IN POWER. THE CONCEPT OF COMPUTABILITY: COMPUTABLE FUNCTIONS, DECIDABLE AND TURING-RECOGNIZABLE LANGUAGES. DECIDABLE LANGUAGES AND UNDECIDABLE LANGUAGES. THE HALTING PROBLEM. MAPPING REDUCIBILITY. RICE’S THEOREM. THE CONCEPT OF COMPLEXITY: MEASURING TIME COMPLEXITY. THE CLASS P. THE CLASS NP. THE CONCEPT OF NP-COMPLETENESS. POLYNOMIAL TIME REDUCIBILITY. EXAMPLES OF NP-COMPLETE LANGUAGES.

Contents

COMPUTATIONAL MODELS: DETERMINISTIC AND NONDETERMINISTIC FINITE AUTOMATA. REGULAR EXPRESSIONS. CLOSURE PROPERTIES OF REGULAR LANGUAGES. KLEENE’S THEOREM. THE PUMPING LEMMA FOR REGULAR LANGUAGES. SINGLE-TAPE DETERMINISTIC TURING MACHINES. THE LANGUAGE RECOGNIZED BY A TURING MACHINE. VARIANTS OF TURING MACHINES AND THEIR EQUIVALENCE IN POWER.

THE CONCEPT OF COMPUTABILITY: COMPUTABLE FUNCTIONS, DECIDABLE AND TURING-RECOGNIZABLE LANGUAGES. DECIDABLE LANGUAGES AND UNDECIDABLE LANGUAGES. THE HALTING PROBLEM. MAPPING REDUCIBILITY. RICE’S THEOREM.

THE CONCEPT OF COMPLEXITY: MEASURING TIME COMPLEXITY.
THE CLASS P. THE CLASS NP. THE CONCEPT OF NP-COMPLETENESS.
POLYNOMIAL TIME REDUCIBILITY. EXAMPLES OF NP-COMPLETE LANGUAGES.

	Teaching Methods
	CLASS LESSONS. LECTURES INCLUDE EXERCISES THAT PRESENT EXAMPLES OF APPLICATIONS OF THE STUDIED CONCEPTS, WITH THE AIM OF ENABLING THE STUDENT TO APPLY THE ACQUIRED KNOWLEDGE.

	Verification of learning
	THE ASSESSMENT OF THE ACQUISITION OF THE BASIC CONCEPTS AND OF THE ABILITY TO APPLY THOSE CONCEPTS WILL BE IN A 2-HOURS WRITTEN EXAM. IT CAN BE SUBSTITUTED BY A MIDTERM PLUS A FINAL TEST. THE EVALUATION CRITERIA INCLUDE THE COMPLETENESS AND CORRECTNESS OF THE LEARNING AND THE CLARITY OF THE PRESENTATION.