mat4ci comp utability
COMPUTABILITY AND INTRACTABILITY
MAT4CI
2015
Credit points: 15
Subject outline
When does a problem have an effective algorithmic solution? What does it mean for an algorithm to be effective? In this subject we attempt to give rigorous meaning to questions of this type and investigate some possible answers. Abstract computing machines and their role in the definitions of various notions of computational complexity will be discussed. Classes of problems such as P, NP will be defined and a number of well known problems in graph theory, algebra and applied discrete mathematics will be classified according to their computational complexity. The second half of the subject covers undecidability for decision problems: problems for which no algorithmic solution is possible. This property is found amongst problems from computing, abstract algebra, combinatorics, matrices and the theory of tilings.
SchoolSchool Engineering&Mathematical Sciences
Credit points15
Subject Co-ordinatorMarcel Jackson
Available to Study Abroad StudentsYes
Subject year levelYear Level 4 - UG/Hons/1st Yr PG
Exchange StudentsYes
Subject particulars
Subject rules
Prerequisites MAT1DM and MAT2AAL and MAT1CLA, or any third year mathematics subject and requires co-ordinators approval
Co-requisitesN/A
Incompatible subjectsN/A
Equivalent subjectsN/A
Special conditions Offered subject to sufficient enrolments.
Graduate capabilities & intended learning outcomes
01. Demonstrate advanced theoretical and technical knowledge in computational complexity
- Activities:
- Demonstrated in lectures and in worksheet classes with feedback through solutions and assignments.
- Related graduate capabilities and elements:
- Literacies and Communication Skills(Writing,Quantitative Literacy)
- Literacies and Communication Skills(Writing,Quantitative Literacy)
- Inquiry and Analytical Skills(Critical Thinking,Creative Problem-solving,Inquiry/Research)
- Inquiry and Analytical Skills(Critical Thinking,Creative Problem-solving,Inquiry/Research)
- Inquiry and Analytical Skills(Critical Thinking,Creative Problem-solving,Inquiry/Research)
- Discipline -Specific Knowledge and Skills(Discipline-Specific Knowledge and Skills)
02. Use advanced cognitive and technical skills to select and apply methods to critically analyse, evaluate and interpret tasks relevant to computational complexity
- Activities:
- Demonstrated in lectures and in worksheet classes with feedback through solutions and assignments.
- Related graduate capabilities and elements:
- Literacies and Communication Skills(Writing,Quantitative Literacy)
- Literacies and Communication Skills(Writing,Quantitative Literacy)
- Inquiry and Analytical Skills(Critical Thinking,Creative Problem-solving,Inquiry/Research)
- Inquiry and Analytical Skills(Critical Thinking,Creative Problem-solving,Inquiry/Research)
- Inquiry and Analytical Skills(Critical Thinking,Creative Problem-solving,Inquiry/Research)
- Discipline -Specific Knowledge and Skills(Discipline-Specific Knowledge and Skills)
03. Use advanced cognitive and technical skills to analyse, generate and transmit solutions to complex problems relevant to computational complexity.
- Activities:
- Demonstrated in lectures and in worksheet classes with feedback through solutions and assignments.
- Related graduate capabilities and elements:
- Literacies and Communication Skills(Writing,Quantitative Literacy)
- Literacies and Communication Skills(Writing,Quantitative Literacy)
- Inquiry and Analytical Skills(Critical Thinking,Creative Problem-solving,Inquiry/Research)
- Inquiry and Analytical Skills(Critical Thinking,Creative Problem-solving,Inquiry/Research)
- Inquiry and Analytical Skills(Critical Thinking,Creative Problem-solving,Inquiry/Research)
- Discipline -Specific Knowledge and Skills(Discipline-Specific Knowledge and Skills)
04. Use advanced communication skills to transmit complexity-theoretic knowledge and ideas to others.
- Activities:
- Demonstrated in lectures and in worksheet classes with feedback through solutions and assignments.
- Related graduate capabilities and elements:
- Literacies and Communication Skills(Writing,Quantitative Literacy)
- Literacies and Communication Skills(Writing,Quantitative Literacy)
- Inquiry and Analytical Skills(Critical Thinking,Creative Problem-solving,Inquiry/Research)
- Inquiry and Analytical Skills(Critical Thinking,Creative Problem-solving,Inquiry/Research)
- Inquiry and Analytical Skills(Critical Thinking,Creative Problem-solving,Inquiry/Research)
- Discipline -Specific Knowledge and Skills(Discipline-Specific Knowledge and Skills)
05. Demonstrate autonomy, well-developed judgement, adaptability and responsibility as a mathematician.
- Activities:
- Demonstrated in lectures and in worksheet classes with feedback through solutions and assignments.
- Related graduate capabilities and elements:
- Literacies and Communication Skills(Writing,Quantitative Literacy)
- Literacies and Communication Skills(Writing,Quantitative Literacy)
- Inquiry and Analytical Skills(Critical Thinking,Creative Problem-solving,Inquiry/Research)
- Inquiry and Analytical Skills(Critical Thinking,Creative Problem-solving,Inquiry/Research)
- Inquiry and Analytical Skills(Critical Thinking,Creative Problem-solving,Inquiry/Research)
- Discipline -Specific Knowledge and Skills(Discipline-Specific Knowledge and Skills)
Subject options
Select to view your study options…
Melbourne, 2015, Semester 1, Day
Overview
Online enrolmentYes
Maximum enrolment sizeN/A
Enrolment information
Subject Instance Co-ordinatorMarcel Jackson
Class requirements
LectureWeek: 10 - 22
Two 1.0 hours lecture per week on weekdays during the day from week 10 to week 22 and delivered via face-to-face.
"requires extensive preparation for class presentations"
Assessments
| Assessment element | Comments | % | ILO* |
|---|---|---|---|
| One assignment equivalent to 1,100 words | 40 | 01, 02, 03, 04, 05 | |
| Three assignments each equivalent to 700 words | 60 | 01, 02, 03, 04, 05 |