Note: This unit is an archived version! See Overview tab for delivered versions.
COMP2022: Formal Languages & Logic (2015 - Semester 1)
| Unit: | COMP2022: Models of Computation (6 CP) |
| Mode: | Normal-Day |
| On Offer: | Yes |
| Level: | Intermediate |
| Faculty/School: | School of Computer Science |
| Unit Coordinator/s: |
A/Prof Yacef, Kalina
|
| Session options: | Semester 1 |
| Versions for this Unit: | |
| Site(s) for this Unit: |
| Campus: | Camperdown/Darlington |
| Pre-Requisites: | INFO1103 OR INFO1903. INFO1105 desired |
| Brief Handbook Description: | This unit aims at providing a deeper understanding of computing systems and of what computation is in general. It covers two essential theoretical aspects of computer science and gives students the foundations to understand the power as well as the limitations of computers. It covers various abstract models for computation such as finite automata, grammars and regular expressions, and the different classes of formal languages that these models recognize such as regular and context-free languages. It also covers the concept of formal proofs in propositional and predicate logic. The course concludes with Turing machines, as well as the notions of computability and decidability. |
| Assumed Knowledge: | MATH1004 OR MATH2069 OR MATH2969. |
| Lecturer/s: |
A/Prof Yacef, Kalina
|
||||||||||||||||||||
| Tutor/s: | tbc | ||||||||||||||||||||
| Timetable: | COMP2022 Timetable | ||||||||||||||||||||
| Time Commitment: |
|
||||||||||||||||||||
| T&L Activities: | Independent Study: Students are expected to undertake the prescribed reading and work on homework exercises and assignments. |
Attributes listed here represent the key course goals (see Course Map tab) designated for this unit. The list below describes how these attributes are developed through practice in the unit. See Learning Outcomes and Assessment tabs for details of how these attributes are assessed.
| Attribute Development Method | Attribute Developed |
| Design of solutions to given problems and scenarios using algorithms and techniques learned in class | Design (Level 2) |
| Competently applies theories, principles, tools & materials of both theory of computation and logic to well-defined problems. | Engineering/IT Specialisation (Level 2) |
| Fluent use of mathematical & scientific concepts, tools and techniques required for formal languages and logic formal proofs. | Maths/Science Methods and Tools (Level 2) |
For explanation of attributes and levels see Engineering & IT Graduate Outcomes Table.
Learning outcomes are the key abilities and knowledge that will be assessed in this unit. They are listed according to the course goal supported by each. See Assessment Tab for details how each outcome is assessed.
Maths/Science Methods and Tools (Level 2)| Assessment Methods: |
|
||||||||||||||||||||||||||||||||||||
| Assessment Description: |
Weekly homework exercises: based on lecture content, handed over at tutorials Assignments: the first 2 are programming assignments, which consists of a report and a programming parts. The 3rd assignment is a formal proof, to be done on paper, individually or in pairs. Final Exam: 2 hour exam, paper-based |
||||||||||||||||||||||||||||||||||||
| Assessment Feedback: | Assignments are handed back within 2 weeks with written feedback. General feedback given in the lecture or in the tutorial. Solutions of tutorials are posted each week. |
||||||||||||||||||||||||||||||||||||
| Grading: |
|
||||||||||||||||||||||||||||||||||||
| Policies & Procedures: | IMPORTANT: School policy relating to Academic Dishonesty and Plagiarism. In assessing a piece of submitted work, the School of IT may reproduce it entirely, may provide a copy to another member of faculty, and/or to an external plagiarism checking service or in-house computer program and may also maintain a copy of the assignment for future checking purposes and/or allow an external service to do so. Other policies See the policies page of the faculty website at http://sydney.edu.au/engineering/student-policies/ for information regarding university policies and local provisions and procedures within the Faculty of Engineering and Information Technologies. |
| Recommended Reference/s: |
Note: References are provided for guidance purposes only. Students are advised to consult these books in the university library. Purchase is not required.
|
| Online Course Content: | USyd e-Learning (WebCT) |
Note that the "Weeks" referred to in this Schedule are those of the official university semester calendar https://web.timetable.usyd.edu.au/calendar.jsp
| Week | Description |
| Week 1 | Lecture: Unit introduction, Deterministic Finite Automata |
| Week 2 | Lecture/Tutorial: NFAs, NFA to DFA and DFA minimisation |
| Week 3 | Lecture/Tutorial: DFA minimisation, Regular expressions |
| Week 4 | Lecture/Tutorial: Grammars, Context-free Languages |
| Week 5 | Lecture/Tutorial: Push down automata, parsing |
| Week 6 | Lecture/Tutorial: More parsing, grammar transformations |
| Assessment Due: Assignment 1 | |
| Week 7 | Regular grammars, Chomsky Normal Form, Introduction to logic |
| Week 8 | Lecture/Tutorial: Propositional Logic, introduction to formal proofs |
| Week 9 | Lecture/Tutorial: More formal proofs, IP and CP rules of inference, tautologies, proving invalidity |
| Assessment Due: Assignement 2 | |
| Week 10 | Lecture/Tutorial: Proofs by resolution, Introduction to Predicate Logic |
| Week 11 | Lecture/Tutorial: Predicate Logic: interpretation, formal proofs, prenex normal forms |
| Week 12 | Lecture/Tutorial: Turing Machines, Church-Turing Hypothesis |
| Assessment Due: Assignment 3 | |
| Week 13 | Lecture/Tutorial: Notion of decidability and tractability, Revisions, Final exam matters |
| Exam Period | Assessment Due: Final exam |
Course Relations
The following is a list of courses which have added this Unit to their structure.
Course Goals
This unit contributes to the achievement of the following course goals:
| Attribute | Practiced | Assessed |
| Maths/Science Methods and Tools (Level 2) | Yes | 7.45% |
| Engineering/IT Specialisation (Level 2) | Yes | 6.45% |
| Design (Level 2) | Yes | 86.1% |
These goals are selected from Engineering & IT Graduate Outcomes Table which defines overall goals for courses where this unit is primarily offered. See Engineering & IT Graduate Outcomes Table for details of the attributes and levels to be developed in the course as a whole. Percentage figures alongside each course goal provide a rough indication of their relative weighting in assessment for this unit. Note that not all goals are necessarily part of assessment. Some may be more about practice activity. See Learning outcomes for details of what is assessed in relation to each goal and Assessment for details of how the outcome is assessed. See Attributes for details of practice provided for each goal.
