Useful links
Unit of study_
COMP2022: Models of Computation
This unit provides an introduction to the foundations of computing. The main aims are to introduce and compare different models of computation based on state-machines, grammars and algebra, and logic.
| Code | COMP2022 |
|---|---|
| Academic unit | Computer Science |
| Credit points | 6 |
|
Prerequisites:
?
|
INFO1103 OR INFO1903 OR INFO1113 |
|---|---|
|
Corequisites:
?
|
None |
| Prohibitions:
?
|
COMP2922 |
| Assumed knowledge:
?
|
(MATH1004 OR MATH1904 OR MATH1064 OR MATH1964 OR MATH2069 OR MATH2969) AND (INFO1105 OR INFO1905 OR COMP2123 OR COMP2823) |
At the completion of this unit, you should be able to:
- LO1. demonstrate a knowledge of basic discrete mathematics, theorems and formal proofs
- LO2. Design a deterministic (resp. nondeterministic) finite state machine to accept a specified language.
- LO3. Generate a regular expression to represent a specified language.
- LO4. Explain why the halting problem has no algorithmic solution.
- LO5. Design a context-free grammar to represent a specified language.
- LO6. Convert among equivalently powerful notations for a language, including among DFAs, NFAs, and regular expressions.
- LO7. Explain the Church-Turing thesis and its significance.
- LO8. Determine a language’s place in the Chomsky hierarchy (e.g., regular, context-free, Turing recognisable)
- LO9. Define the classes P and NP.
- LO10. Provide examples of uncomputable functions.
- LO11. Prove that a problem is uncomputable by reducing a classic known uncomputable problem to it.
- LO12. Convert logical statements from informal language to propositional and predicate logic expressions.
- LO13. Apply formal methods of symbolic propositional and predicate logic, such as calculating validity of formulae and computing normal forms.
- LO14. Use the rules of inference to construct proofs in propositional and predicate logic.
- LO15. Describe how symbolic logic can be used to model real-life situations or applications, e.g., arising in computing contexts such as software analysis (e.g., program correctness), database queries, or algorithms.
- LO16. Describe the strengths and limitations of propositional and predicate logic.
Unit outlines
Unit outlines will be available 2 weeks before the first day of teaching for the relevant session.
- Semester 2, 2024 [Normal day] - Camperdown/Darlington, Sydney
- Key dates
Key dates through the academic year, including teaching periods, census, payment deadlines and exams.
- Student administration
Enrolment, course planning, fees, graduation, support services, student IT
- Expectations of student conduct
Code of Conduct for Students, Conditions of Enrollment, University Privacy Statement, Academic Integrity
- Academic appeals
Academic appeals process, special consideration, rules and guidelines, advice and support
- Learning and teaching policy
Policy register, policy search
- Financial support
Scholarships, interest free loans, bursaries, money management
- Study resources
Learning Centre, faculty and school programs, Library, online resources
- Health and support
Student Centre, counselling & psychological services, University Health Service, general health and wellbeing
