Rosalba ZIZZA | ELEMENTS OF COMPUTATION THEORY

cod. 0512100018

ELEMENTS OF COMPUTATION THEORY

	0512100018
	COMPUTER SCIENCE
	EQF6
	COMPUTER SCIENCE
	2022/2023

PERCORSO COMUNE

	OBBLIGATORIO
	YEAR OF COURSE 3
	YEAR OF DIDACTIC SYSTEM 2017
	SPRING SEMESTER

TEACHING UNITS

	SSD	CFU	HOURS	ACTIVITY	TYPE OF ACTIVITY
	INF/01	9	72	LESSONS	COMPULSORY SUBJECTS, CHARACTERISTIC OF THE CLASS

PROFESSORS

	CLELIA DE FELICE T Curriculum
	ROSALBA ZIZZA Curriculum

EXAMS

Exam	Date	Session
APPELLO PROF.SSA DE FELICE	09/06/2023 - 12:00	SESSIONE ORDINARIA
II PROVA INTERCORSO DE FELICE/ZIZZA	09/06/2023 - 12:00	SESSIONE ORDINARIA
APPELLO PROF.SSA DE FELICE	29/06/2023 - 12:00	SESSIONE ORDINARIA
APPELLO PROF.SSA DE FELICE	13/07/2023 - 15:00	SESSIONE ORDINARIA

	Objectives
	KNOWLEDGE AND UNDERSTANDING 1.ABSTRACT COMPUTING MODELS 2.PROBLEMS THAT ARE SOLVABLE AND PROBLEMS THAT ARE NOT SOLVABLE 3. DIFFERENCE BETWEEN THE CONCEPTS OF COMPUTABLE AND NOT COMPUTABLE 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.PROBLEMS THAT ARE SOLVABLE AND PROBLEMS THAT ARE NOT SOLVABLE
3. DIFFERENCE BETWEEN THE CONCEPTS OF COMPUTABLE AND NOT COMPUTABLE

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, FIRST PART (28 HOURS): DETERMINISTIC AND NONDETERMINISTIC FINITE AUTOMATA. REGULAR EXPRESSIONS. CLOSURE PROPERTIES OF REGULAR LANGUAGES. KLEENE’S THEOREM. THE PUMPING LEMMA FOR REGULAR LANGUAGES. • COMPUTATIONAL MODELS, SECOND PART (14 HOURS): 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 (14 HOURS): COMPUTABLE FUNCTIONS, DECIDABLE AND TURING-RECOGNIZABLE LANGUAGES. DECIDABLE LANGUAGES AND UNDECIDABLE LANGUAGES. THE HALTING PROBLEM. MAPPING REDUCIBILITY. RICE’S THEOREM. THE CONCEPT OF COMPLEXITY (16 HOURS): 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, FIRST PART (28 HOURS): DETERMINISTIC AND NONDETERMINISTIC FINITE AUTOMATA. REGULAR EXPRESSIONS. CLOSURE PROPERTIES OF REGULAR LANGUAGES. KLEENE’S THEOREM. THE PUMPING LEMMA FOR REGULAR LANGUAGES.
• COMPUTATIONAL MODELS, SECOND PART (14 HOURS): 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 (14 HOURS): COMPUTABLE FUNCTIONS, DECIDABLE AND TURING-RECOGNIZABLE LANGUAGES. DECIDABLE LANGUAGES AND UNDECIDABLE LANGUAGES. THE HALTING PROBLEM. MAPPING REDUCIBILITY. RICE’S THEOREM.

THE CONCEPT OF COMPLEXITY (16 HOURS): 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. THE LECTURES INCLUDE EXERCISES THAT WILL PRESENT EXAMPLES OF APPLICATIONS OF THOSE CONCEPTS, WITH THE AIM OF ENABLING THE STUDENT TO APPLY THE KNOWLEDGE ACQUIRED.

	Verification of learning
	THE ASSESSMENT OF THE ACQUISITION OF THE BASIC CONCEPTS AND OF THE ABILITY TO APPLY THOSE CONCEPTS WILL BE IN A WRITTEN EXAM. THE WRITTEN EXAM 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. THE MINIMUM GRADE (18) IS ASSIGNED WHEN THE STUDENT HAS A LIMITED KNOWLEDGE OF THE COMPUTATIONAL MODELS AND COMPUTATIONAL COMPLEXITY AND SHOWS UNCERTAINTIES IN THE APPLICATION OF THE STUDIED METHODS. THE MAXIMUM GRADE (30) IS ASSIGNED WHEN THE STUDENT SHOWS A COMPLETE AND IN-DEPTH KNOWLEDGE OF THE CONCEPTS AND METHODS OF THE THEORY OF COMPUTATION. IT IS ALSO ABLE TO SOLVE THE PROPOSED PROBLEMS GIVING EFFICIENT AND ACCURATE SOLUTIONS AND SHOWS THE ABILITY TO LINK DIFFERENT CONCEPTS TOGETHER. ''LODE'' IS GIVEN WHEN THE CANDIDATE DEMONSTRATES SIGNIFICANT MASTERY OF THE THEORETICAL AND OPERATIONAL CONTENT AND SHOWS THAT SHE/HE IS ABLE TO PRESENT THE TOPICS WITH OWNERSHIP OF LANGUAGE AND AUTONOMOUS PROCESSING SKILLS.

Verification of learning

THE ASSESSMENT OF THE ACQUISITION OF THE BASIC CONCEPTS AND OF THE ABILITY TO APPLY THOSE CONCEPTS WILL BE IN A WRITTEN EXAM. THE WRITTEN EXAM 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.

THE MINIMUM GRADE (18) IS ASSIGNED WHEN THE STUDENT HAS A LIMITED KNOWLEDGE OF THE COMPUTATIONAL MODELS AND COMPUTATIONAL COMPLEXITY AND SHOWS UNCERTAINTIES IN THE APPLICATION OF THE STUDIED METHODS.
THE MAXIMUM GRADE (30) IS ASSIGNED WHEN THE STUDENT SHOWS A COMPLETE AND IN-DEPTH KNOWLEDGE OF THE CONCEPTS AND METHODS OF THE THEORY OF COMPUTATION. IT IS ALSO ABLE TO SOLVE THE PROPOSED PROBLEMS GIVING EFFICIENT AND ACCURATE SOLUTIONS AND SHOWS THE ABILITY TO LINK DIFFERENT CONCEPTS TOGETHER.
''LODE'' IS GIVEN WHEN THE CANDIDATE DEMONSTRATES SIGNIFICANT MASTERY OF THE THEORETICAL AND OPERATIONAL CONTENT AND SHOWS THAT SHE/HE IS ABLE TO PRESENT THE TOPICS WITH OWNERSHIP OF LANGUAGE AND AUTONOMOUS PROCESSING SKILLS.

	Texts
	•M. SIPSER, INTRODUZIONE ALLA TEORIA DELLA COMPUTAZIONE, APOGEO, 2016 •J. HOPCROFT, R. MOTWANI, J. ULLMAN, AUTOMI, LINGUAGGI E CALCOLABILITÀ, ADDISON WESLEY PEARSON EDUCATION ITALIA S.R.L, TERZA EDIZIONE, 2009.

	More Information
	E-LEARNING PLATFORM WEB SITE: HTTP://ELEARNING.INFORMATICA.UNISA.IT/EL-PLATFORM/ CONTACT INFORMATION: CDEFELICE@UNISA.IT RZIZZA@UNISA.IT HTTPS://DOCENTI.UNISA.IT/001119/HOME HTTPS://DOCENTI.UNISA.IT/020880/HOME

Lessons Timetable

BETA VERSION Data source ESSE3 [Ultima Sincronizzazione: 2023-06-06]

Rosalba ZIZZA | ELEMENTS OF COMPUTATION THEORY