Postgraduate Course: Propositional Methods (INFR11009)
Course Outline
School |
School of Informatics |
College |
College of Science and Engineering |
Course type |
Standard |
Availability |
Available to all students |
Credit level (Normal year taken) |
SCQF Level 11 (Postgraduate) |
Credits |
10 |
Home subject area |
Informatics |
Other subject area |
None |
Course website |
http://www.inf.ed.ac.uk/teaching/courses/propm |
|
|
Course description |
Satisfiability (SAT) was the first problem shown to be NP-complete and is both a cornerstone of computational complexity theory and commercially important since thousands of practical combinatorial problems would benefit from a highly efficient SAT solver.
This course will introduce modern methods and tools for representing and manipulating boolean formulae, in particular, Binary Decision Diagrams and probabilistic SAT solvers.
Students will develop facility in encoding a variety of problems in propositional form. |
Entry Requirements
Pre-requisites |
|
Co-requisites |
|
Prohibited Combinations |
|
Other requirements |
For Informatics PG and final year MInf students only, or by special permission of the School. Students are expected to have familiarity with basic Boolean Logic and some acquaintance with SML.
|
Additional Costs |
None |
Course Delivery Information
Summary of Intended Learning Outcomes
1 - Students will be able to apply BDD and SAT technologies in a variety of applications.
2 - They will be able to find potential for practical applications of reductions more commonly seen in proofs of complexity results, and apply abstract methods to practical applications.
3 - Students will be able to solve problems by bringing together a variety of software tools and components.
4 - Students will have read, presented and discussed papers from the current literature.
5 - They will have completed an extended practical project and produce a written report. |
Assessment Information
Written Examination 70
Assessed Assignments 20
Oral Presentations 10
Assessment
In the first four weeks ot the source, students will carry out routine assignments designed to familiarise them with current tools.
They will then undertake a four-week assignment requiring them to encode a family of combinatorial problems in propositional form and investigate the effectiveness of SAT- or BDD- based methods in solving problems from this family.
If delivered in semester 1, this course will have an option for semester 1 only visiting undergraduate students, providing assessment prior to the end of the calendar year. |
Please see Visiting Student Prospectus website for Visiting Student Assessment information |
Special Arrangements
Not entered |
Contacts
Course organiser |
Dr Michael Rovatsos
Tel: (0131 6)51 3263
Email: mrovatso@inf.ed.ac.uk |
Course secretary |
Miss Gillian Watt
Tel: (0131 6)50 5194
Email: gwatt@inf.ed.ac.uk |
|
copyright 2010 The University of Edinburgh -
1 September 2010 6:10 am
|