1. Instructor information
:
Instructor name: Ngô Thanh Hùng Email: hungnt@uit.edu.vn
Phone: Cell phone:
Office: Office hours:
2. Class room
:
Main class room (campus):
Online classroom (website):
Class meeting time: weekly
Library hours (where): VNU-Library.
3. Course information
:
Course description:
Credit: 4 (3 lecture, 1 lab)
Introduction to sequential machines and their applications to devices, processes, and programming. Models of computation: finite state automata, push-down
automata, Turing machines. The role of non-determinism. Limit of digital computation. Computability and unsolvability. The Church-Turing machines.
Course objectives:
At the completion of this course, a student should be able to:
- Understand the linear programming, goal programming, network models and forcasting.
- Solve the problems by using the problem solving techniques to be mentioned in the course.
- Understanding and computing the complexity of algorithm.
Prerequisite:
Operations Management (MIS 3223) and Calculus (Math 2103 or 2144).
4. Book and materials
:
Required textbook:
Michael Sipser, Introduction to the Theory of Computation, Second edition
Other materials:
- John C. Martin, Introduction to Languages and the Theory of Computation
- Eitan Gurari, An Introduction to the Theory of Computation
- Harry R. Lewis and Christos H. Papadimitriou, Elements of the Theory of Computation
- Raymond Greenlaw and H. James Hoover, Fundamentals of the Theory of Computation: Principles and Practice
Related materials:
- Thomas H. Cormen, et al, Introduction to Algorithm
Course website:
5. Course requirements
:
Assignments: Exercises are in corresponding sections of the required book.
Projects or Team Class Projects: Projects are given by the instructor after finishing a chapter.
Midterm Examinations:
Class attendance/participation: Evaluated by checking in the Attendance Book
Final Examination: Students are directly tested and automatically marked on computers.
6. Grading Procedures
:
Assignments: ............................................................................... 20%
Quizzes: ...............................................................................................
Computer-based training and testing: ..................................................
Projects or Team Class Projects: ................................................... 10%
Midterm Examinations: ............................................................... 25%
Class attendance/participation: ...................................................... 5%
Final Examination: ....................................................................... 40%
Total point and Grades
:
90-100: Good (A) 80-89: Well (B) 70-79: Mean (C)
60-69: Weak (D) 50-59: bad (E) 1-49: too bad (F)
7. Academic integrity Policies
:
- Student may not be absence in 4 sessions. If so, he/she will be prohibitted from test or exam
- Student may not use Vietnamese languague in their class, or will be reduced 2% final marks
- Be punctual to come and leave the class.
- Maximum cancellation time per semester is 6 hours per class.
8.. Course outline
:
|
Week |
Topic |
Assignments |
|
1 |
Introduction |
|
|
2,3 |
Regular Languages |
|
|
4,5 |
Context - Free Languages |
|
|
6,7 |
The Church-Turing Thesis |
|
|
8,9 |
Decidability |
|
|
10,11 |
The complexity theory and NP - Completeness |
9. Comments and notes
:
Make-up: Make-up classes are officially accepted after the Make-up forms are signed by all of the students in the class and directly send to the
Registrars.
Preparation for Class: It is expected that the students read related chapter in textbook and lecture noted before each class. This will help to
capture the topics presented and discussed during class hours.
Use of Class Time: Class time will be used mainly for lectures and discussions. A small part of class hours is used for testing. House works will
be discussed on individual basis.
Class Attendance: Due to the broad range of topics discussed throughout the course and their inter-relationship, it is requested that the students
should attend the class regularly.
Incomplete Grade: A grade of “I” (Incomplete) will be administered only under extreme, verifiable “emergency” situation where the student is
unable to complete some portion of the course work due to circumstances beyond his/her control PROVIDED THE STUDENT IS PASSING THE COURSE.
Assignment Requirement: Assignments of each session must be submited by email before the next session begins.
Instructor’s Signature
Hung Thanh Ngo