Undergraduate - UnitFIT2014 - Theory of computation

This unit entry is for students who completed this unit in 2013 only. For students planning to study the unit, please refer to the unit indexes in the the current edition of the Handbook. If you have any queries contact the managing faculty for your course or area of study.

print version

6 points, SCA Band 2, 0.125 EFTSL

To find units available for enrolment in the current year, you must make sure you use the indexes and browse unit tool in the current edition of the Handbook.

Level	Undergraduate
Faculty	Faculty of Information Technology
Offered	Clayton Second semester 2013 (Day) Sunway Second semester 2013 (Day)

Synopsis

This unit gives an introduction to formal languages using logic programming and looks at what a computer can compute and what problems are intractable. Examples include why it is so difficult to design timetables, get computers to play Go, or crack a code. Topics include computable functions, finite state automata, regular expressions, grammars, Turing computability, polynomial-time reductions, and NP-completeness.

Outcomes

At the completion of this unit, students will have -

A knowledge and understanding of:

propositional and predicate logic;
how to describe languages using Regular Expressions, Finite Automata, Nondeterministic Finite Automata, Context Free Grammars, Pushdown Automata, and Turing Machines;
the relationship between Regular Languages, Context Free Languages, Recursive Languages, and Recursive-Enumerable (or Computable) Languages;
how to use Turing Machines to represent computable functions;
how a Universal Turing machine can simulate any Turing Machine on any input;
basic computational complexity theory, including verifiers, polynomial-time reductions and NP-completeness.

Developed attitudes that will allow them to:

appreciate the limitations of Regular Languages, Context Free Languages, Recursive Languages, and Computable Languages;
comprehend the limitations of computers in terms of the problems they can solve;
appreciate that there are many solvable problems which cannot be solved in polynomial time.

Developed the skills to:

use propositional logic to represent and analysis problems in the theory of computation;
construct Finite Automata, Nondeterministic Automata, and Turing Machines to describe languages;
convert Regular Expressions into a Finite Automata;
convert Finite Automata into Regular Expressions;
find a Regular Grammar for a Regular Language;
find a parse tree, leftmost derivation and rightmost derivation for a word in a Context Free Language;
know how to show a Context Free Grammar is ambiguous;
show a problem is NP-complete.

Assessment

Examination (3 hours): 70%; In-semester assessment: 30%

Chief examiner(s)

Professor Graham Farr

Contact hours

2 hrs lectures/wk, 3 hrs laboratory/fortnight, 2 hrs tutorial/fortnight

This unit applies to the following area(s) of study

Computational science
Computer science

Prerequisites

FIT1029 and 6 points of level 1 (or above) mathematics

For students in courses 2380, 2770, 0050, 2672, 3517, 3282 and 0085 who commenced prior to 2011: FIT1008/FIT1015 and 6 points of approved mathematics

Prohibitions

CSE2303

Additional information on this unit is available from the faculty at:

http://www.infotech.monash.edu.au/units/fit2014