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. -- Course Website
Prerequisites: FIT1029 and 6 points of level 1 (or above) mathematics<br/><br/>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
