KA205001 Theory of Computing

Hiroshima University Syllabus

Japanese

Academic Year 2024Year School/Graduate School School of Informatics and Data Science

Lecture Code KA205001 Subject Classification Specialized Education

Subject Name 計算理論

Subject Name
（Katakana）ケイサンリロン

Subject Name in
English Theory of Computing

Instructor NAKANISHI TOORU

Instructor
(Katakana) ナカニシ　トオル

Campus Higashi-Hiroshima Semester/Term 3rd-Year,  First Semester,  1Term

Days, Periods, and Classrooms (1T) Mon1-4：ENG 219

Lesson Style Lecture Lesson Style
(More Details) 　

Basically, Face-to-face Lecture

Credits 2.0 Class Hours/Week 　 Language of Instruction B : Japanese／English

Course Level 3 : Undergraduate High-Intermediate

Course Area（Area） 25 : Science and Technology

Course Area（Discipline） 02 : Information Science

Eligible Students

Keywords finite automaton, Turing machine, computability, complexity

Special Subject for Teacher Education 　 Special Subject 　

Class Status
within Educational
Program
(Applicable only to targeted subjects for undergraduate students) Learning the fundamental theory in the system and information engineering and acquiring the logical thinking ability.
Criterion referenced
Evaluation
(Applicable only to targeted subjects for undergraduate students) Program of Electrical,Systems and Information Engineering
（Abilities and Skills）
・Concepts, knowledge and methods which are the basis for studies related to electrical,  systems, and information engineering.
・Concepts, knowledge and methods which are the basis for studies related to electrical, systems, and information engineering.

Computer Science Program
（Knowledge and Understanding）
・D1. Knowledge and ability to understand the theoretical framework underlying computer science and to collect and process high-dimensional data through full use of information processing technology based on scientific logic.
（Abilities and Skills）
・A. Information infrastructure development technology, information processing technology, technology that analyzes data and creates new added value.

Data Science Program
（Abilities and Skills）
・A. Information infrastructure development technology, information processing technology, technology that analyzes data and creates new added value.

Intelligence Science Program
（Knowledge and Understanding）
・D1. A deep systematic understanding of the advanced intelligence of human beings and its realization by computers.
（Abilities and Skills）
・A. Information infrastructure development technology, information processing technology, technology that analyzes data and creates new added value.

Class Objectives
/Class Outline As fundamentals of computers, this class targets to learn the computability (What can be computed?) and the complexity (How efficiently can it be computed?) using formal computation models. In addition, this class targets to learn fundamental concepts and proving techniques to acquire the logical thinking ability.

Class Schedule lesson1: Guidance
lesson2: Mathematical reviews
lesson3: Finite automaton (1)
lesson4: Finite automaton (2)
lesson5: Turing machine (1)
lesson6: Turing machine (2)
lesson7: Turing machine (3)
lesson8: Computability (1)
lesson9: Computability (2)
lesson10: Computability (3)
lesson11: Computability (4)
lesson12: Complexity (1)
lesson13: Complexity (2)
lesson14: Complexity (3)
lesson15: Cryptography and excercise

The final examination will be held.

Text/Reference
Books,etc. References: "Introduction to the theory of COMPUTATION (Second edition)" 1-3, Michael Sipser, Kyouritsu-Shuppan

PC or AV used in
Class,etc. 　

(More Details)

Learning techniques to be incorporated 　

Suggestions on
Preparation and
Review Students should review the exercises in each lecture.

Requirements

Grading Method Evaluation based on exercises/small tests/reports (about 30%) and examinations (about 70%)

Practical Experience

Summary of Practical Experience and Class Contents based on it

Message

Other

Please fill in the class improvement questionnaire which is carried out on all classes.
Instructors will reflect on your feedback and utilize the information for improving their teaching.

Academic Year	2024Year	School/Graduate School	School of Informatics and Data Science
Lecture Code	KA205001	Subject Classification	Specialized Education
Subject Name	計算理論
Subject Name （Katakana）	ケイサンリロン
Subject Name in English	Theory of Computing
Instructor	NAKANISHI TOORU
Instructor (Katakana)	ナカニシ　トオル
Campus	Higashi-Hiroshima	Semester/Term	3rd-Year, First Semester, 1Term
Days, Periods, and Classrooms	(1T) Mon1-4：ENG 219
Lesson Style	Lecture	Lesson Style (More Details)
Basically, Face-to-face Lecture
Credits	2.0	Class Hours/Week		Language of Instruction	B : Japanese／English
Course Level	3 : Undergraduate High-Intermediate
Course Area（Area）	25 : Science and Technology
Course Area（Discipline）	02 : Information Science
Eligible Students
Keywords	finite automaton, Turing machine, computability, complexity
Special Subject for Teacher Education		Special Subject
Class Status within Educational Program (Applicable only to targeted subjects for undergraduate students)	Learning the fundamental theory in the system and information engineering and acquiring the logical thinking ability.
Criterion referenced Evaluation (Applicable only to targeted subjects for undergraduate students)	Program of Electrical,Systems and Information Engineering （Abilities and Skills）・Concepts, knowledge and methods which are the basis for studies related to electrical, systems, and information engineering. ・Concepts, knowledge and methods which are the basis for studies related to electrical, systems, and information engineering. Computer Science Program （Knowledge and Understanding）・D1. Knowledge and ability to understand the theoretical framework underlying computer science and to collect and process high-dimensional data through full use of information processing technology based on scientific logic. （Abilities and Skills）・A. Information infrastructure development technology, information processing technology, technology that analyzes data and creates new added value. Data Science Program （Abilities and Skills）・A. Information infrastructure development technology, information processing technology, technology that analyzes data and creates new added value. Intelligence Science Program （Knowledge and Understanding）・D1. A deep systematic understanding of the advanced intelligence of human beings and its realization by computers. （Abilities and Skills）・A. Information infrastructure development technology, information processing technology, technology that analyzes data and creates new added value.
Class Objectives /Class Outline	As fundamentals of computers, this class targets to learn the computability (What can be computed?) and the complexity (How efficiently can it be computed?) using formal computation models. In addition, this class targets to learn fundamental concepts and proving techniques to acquire the logical thinking ability.
Class Schedule	lesson1: Guidance lesson2: Mathematical reviews lesson3: Finite automaton (1) lesson4: Finite automaton (2) lesson5: Turing machine (1) lesson6: Turing machine (2) lesson7: Turing machine (3) lesson8: Computability (1) lesson9: Computability (2) lesson10: Computability (3) lesson11: Computability (4) lesson12: Complexity (1) lesson13: Complexity (2) lesson14: Complexity (3) lesson15: Cryptography and excercise The final examination will be held.
Text/Reference Books,etc.	References: "Introduction to the theory of COMPUTATION (Second edition)" 1-3, Michael Sipser, Kyouritsu-Shuppan
PC or AV used in Class,etc.
(More Details)
Learning techniques to be incorporated
Suggestions on Preparation and Review	Students should review the exercises in each lecture.
Requirements
Grading Method	Evaluation based on exercises/small tests/reports (about 30%) and examinations (about 70%)
Practical Experience
Summary of Practical Experience and Class Contents based on it
Message
Other
Please fill in the class improvement questionnaire which is carried out on all classes. Instructors will reflect on your feedback and utilize the information for improving their teaching.

Back to syllabus main page