Day | Time | Location CB 121 ------------------------ |
|||
Monday and Wednesday | 2:30-4:00 pm [See also Lecture Schedule ] |
Instructor: | Professor
G. Tourlakis , Office: 2051 CSEB, Telephone: 736-2100-66674, e-mail: gt@cse.yorku.ca |
|
Start date: | Jan. 7, 2019 |
It is the responsibility of students to check the course web page weekly for course related information.
COURSE DESCRIPTION
This is a first course on the theoretical limitations of computing:
That is, what we cannot do by programming. On the other hand, some
topics (e.g., Finite Automata, Context Free Grammars) find
application in a wide variety of areas in the field (e.g.,
software engineering, developing compiler writing tools), however,
application is not the main focus of the course.
Topics will include in approximate chronological sequence: A
General Mathematical Model of Computation (e.g., the URM, the
Turing Machine); Church's Thesis and Kleene's SMN Theorem;
problems that the general model can solve and problems it cannot solve:
diagonalisation and reductions toward proving that certain
problems -- such as the "Halting Problem" -- cannot be solved by
our model (same as: cannot be programmed in our model). We
then look into Restricted
Models of Computation: Formal Languages, their deciders and verifiers, and their limitations.
Specifically, the following themes: Regular and Context
free languages and Grammars
and finite automata. The focus will be on what these restricted models of computation
cannot
do: Impossibility
results via the pumping lemmata.
PREREQUISITES:
General
prerequisites; LE/EECS1021 3.00 or LE/EECS1022 3.00 or
LE/EECS1720 3.00 or LE/EECS1030 3.00;
LE/EECS1028 3.00 or SC/MATH1028 3.00 or LE/EECS1019 3.00
or SC/MATH1019 3.00
Learning Outcomes for the course:
REQUIRED TEXT
G. Tourlakis,
Theory of Computation , John Wiley & Sons. ISBN: 9781118014783.
OTHER SUGGESTED TEXTS
H. R. Lewis and C. H. Papadimitriou, Elements of the Theory
of Computation, Prentice Hall (latest edition). ISBN 013
2734176
Michael Sipser, Introduction
to
the Theory of Computation, PWS Publishing Company. ISBN
0-534-94728-X
WEIGHTING OF COURSE
Term work (Homework 30% ; Mid-Term Test 30%) |
|
|
Final Exam |
|
Term Test Date/Time: Feb
13, 2019 (in class), 2:30-3:50pm.
Note:
Missed tests with good reason
(normally medical, and
well documented) will have their weight transferred to the final exam.
There are no "make up" tests and no makeup assignments.
Tests missed for no reason are deemed to have been written and are marked
"0" (F). The weight of a
missed assignment is never carried to the final.
The
homework must
be each individual's own work. While consultations
with the instructor, tutor(s), and among students, are part of the learning process and are encouraged, nevertheless,
at the end of all
this consultation each
student will have to produce an individual (typed)
report rather than a copy (full or partial) of
somebody else's report.
Follow these links to familiarise
yourselves with Senate's expectations regarding Academic
Honesty, but also with many other Senate policies, in
particular, with those about Academic
Accommodation
for Students with Disabilities, Religious
Accommodation and Repeating
Passed
or Failed Courses for Academic Credit. See also this link.
The concept of "late assignments" does not exist in
this course (solutions are posted on the due date).
Last revised: Aug 25, 2018