Hiroshima University Syllabus

Back to syllabus main page
Academic Year 2022Year School/Graduate School School of Informatics and Data Science
Lecture Code KA205001 Subject Classification Specialized Education
Subject Name 計算理論
Subject Name
Subject Name in
Theory of Computing
ナカニシ トオル
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)
Credits 2.0 Class Hours/Week   Language of Instruction B : Japanese/English
Course Level 2 : Undergraduate Low-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
Learning the fundamental theory in the system and information engineering and acquiring the logical thinking ability. 
Criterion referenced
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.

Informatics and Data Science Program
(Knowledge and Understanding)
・I1. Knowledge and ability required for collecting and processing high-dimensional data using information processing technologies based on scientific logic, while understanding the theoretical system that forms the basis of informatics.

(Abilities and Skills)
・A. Skills related to the development of an information infrastructure,information processing techniques, and technology for producing new added value through data analysis.
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. 
References: "Introduction to the theory of COMPUTATION (Second edition)" 1-3, Michael Sipser, Kyouritsu-Shuppan 
PC or AV used in
(More Details)  
Learning techniques to be incorporated  
Suggestions on
Preparation and
Students should review the exercises in each lecture. 
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  
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