|
HU Credits:
5
Degree/Cycle:
1st degree (Bachelor)
Responsible Department:
Computer Sciences
Semester:
1st and/or 2nd Semester
Teaching Languages:
Hebrew
Campus:
E. Safra
Course/Module Coordinator:
Prof Orna Kupferman and Dr. Oded Schwartz
Coordinator Office Hours:
By appointment. Schedule by email.
Teaching Staff:
Prof Weinstein Omri,
Prof Oded Schwartz,
Mr. Gross Yoav,
Ms. Naama Shemeshhal,
Ms. Maya Dotan,
Mr. Ofer Leshkowitz,
Prof Orna Kupferman,
Mr. Bader Abu Radi
Course/Module description:
The course consists of three parts. The first part examines the computational strength of simple computational models, such as automata, and the formal representation of the languages recognizable by these models. The second part deals with the computational abilities and limitations of a general (Turing complete) computer. The last part focuses on quantifying the computational resources, such as time and space, required for deciding different classes of computational problems.
Possible specific subjects include:
Automata and formal languages: Finite automata and regular languages, closure properties, determinization, minimality, context free languages, grammars, pushdown automata.
Computability: The Turing machine model, decidability and undecidability, reductions.
Complexity: Time and space complexity. The classes P, NP, NLOGSPACE, PSPACE and completeness for these classes. Heirarchy theorems. Other advanced subjects.
Course/Module aims:
NA
Learning outcomes - On successful completion of this module, students should be able to:
NA
Attendance requirements(%):
0
Teaching arrangement and method of instruction:
Lectures, TA sessionsת exercises and quizzes.
Course/Module Content:
NA
Required Reading:
None
Additional Reading Material:
Introduction to the Theory of Computation by Michael Sipser
Course/Module evaluation:
End of year written/oral examination 80 %
Presentation 0 %
Participation in Tutorials 0 %
Project work 0 %
Assignments 10 %
Reports 0 %
Research project 0 %
Quizzes 10 %
Other 0 %
Additional information:
NA
|
