1. Handbook
  2. Subjects
  3. Models of Computation

Models of Computation (COMP30026)

Undergraduate level 3Points: 12.5On Campus (Parkville)

You’re viewing the 2018 Handbook:
Or view archived Handbooks
You’re currently viewing the 2018 version of this subject

Overview

Availability
Semester 2
FeesLook up fees

AIMS

Formal logic and discrete mathematics provide the theoretical foundations for computer science. This subject uses logic and discrete mathematics to model the science of computing. It provides a grounding in the theories of logic, sets, relations, functions, automata, formal languages, and computability, providing concepts that underpin virtually all the practical tools contributed by the discipline, for automated storage, retrieval, manipulation and communication of data.

INDICATIVE CONTENT

  • Logic: Propositional and predicate logic, resolution proofs, mathematical proof
  • Discrete mathematics: Sets, functions, relations, order, well-foundedness, induction and recursion
  • Automata: Regular languages, finite-state automata, context-free grammars and languages, parsing
  • Computability briefly: Turing machines, computability, decidability.

A functional programming language will be used to implement and illustrate concepts.

Intended learning outcomes

INTENDED LEARNING OUTCOMES (ILO)

  1. Use propositional and predicate logic as tools to reason about  non-trivial computational problems
  2. Explain basic principles of mechanised reasoning, including resolution proof, and apply these to reason about computational problems
  3. Reason about properties of mathematical objects such as functions
  4. and relations, and apply them to computational problems
  5. Apply discrete mathematical techniques to problems in computer science
  6. Synthesize context-free grammars from less formal language specifications
  7. Design abstract computational devices, such as finite-state automata and pushdown automata
  8. Analyze and reason about computational models, including finite-state automata, pushdown automata and Turing machines

 


INTENDED LEARNING OUTCOMES (ILO)



  • On completion of this subject the student is expected to:
  • Use propositional and predicate logic as tools to reason about non-trivial computational problems
  • Explain basic principles of mechanised reasoning, including resolution proof, and apply these to reason about computational problems
  • Reason about properties of mathematical objects such as functions and relations, and apply them to computational problems
  • Apply discrete mathematical techniques to problems in computer science
  • Synthesize context-free grammars from less formal language specifications
  • Design abstract computational devices, such as finite-state automata and pushdown automata.
  • Analyze and reason about computational models, including finite-state automata, pushdown automata and Turing machines.

Generic skills

On completion of this subject students should have developed the following skills:

  • Analytical skills
  • Reasoning and problem-solving skills
  • Ability to communicate with precision, rigour and efficacy
  • Ability to apply knowledge of science and engineering fundamentals
  • Capacity for creativity and innovation
  • Ability to undertake problem identification, formulation and solution

Last updated: 3 November 2022