## Handbook home

# Models of Computation (COMP30026)

Undergraduate level 3Points: 12.5On Campus (Parkville)

## About this subject

- Overview
- Eligibility and requirements
- Assessment
- Dates and times
- Further information
- Timetable(opens in new window)

## Contact information

##### Semester 2

A/Prof Harald Sondergaard

email: harald@unimelb.edu.au

## Overview

Availability | Semester 2 |
---|---|

Fees | Look 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)

- 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

**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