Person in charge: | (-) |
Others: | (-) |
Credits | Dept. |
---|---|
7.5 (6.0 ECTS) | CS |
Person in charge: | (-) |
Others: | (-) |
This course will deepen into the general subjects of logic as a basic tool for computing.
Additionally, we will develop abilities in some application areas that will allow the student to quickly create systems for solving very diverse practical problems.
Special attention will be dedicated to logical programming and logical programming with constraints.
Estimated time (hours):
T | P | L | Alt | Ext. L | Stu | A. time |
Theory | Problems | Laboratory | Other activities | External Laboratory | Study | Additional time |
|
T | P | L | Alt | Ext. L | Stu | A. time | Total | ||
---|---|---|---|---|---|---|---|---|---|---|
9,0 | 0 | 6,0 | 0 | 6,0 | 8,0 | 0 | 29,0 | |||
Review of propositional logic.
Algorithms: Resolution, Davis-Putnam-Logemann-Loveland, DBB"s. Tools: Prolog, Chaff, DDB packages. Programming using translation into a SAT (satisfiability formula) and use of associated tools. Examples of applications: timetabling problems, etc.
|
|
T | P | L | Alt | Ext. L | Stu | A. time | Total | ||
---|---|---|---|---|---|---|---|---|---|---|
12,0 | 0 | 8,0 | 0 | 4,0 | 6,0 | 0 | 30,0 | |||
Review of first order logic.
Algorithms: Resolution and constraints, automatic deduction. Resolution-based methods: Logic programming, deductive databases.
|
|
T | P | L | Alt | Ext. L | Stu | A. time | Total | ||
---|---|---|---|---|---|---|---|---|---|---|
6,0 | 0 | 4,0 | 0 | 8,0 | 10,0 | 0 | 28,0 | |||
Foundations: SLD resolution.
Optimisations: pre-defined data types, input-output. Designing declarative programmes. Advanced data structures in logic programming.
|
|
T | P | L | Alt | Ext. L | Stu | A. time | Total | ||
---|---|---|---|---|---|---|---|---|---|---|
9,0 | 0 | 6,0 | 0 | 6,0 | 9,0 | 0 | 30,0 | |||
How to obtain flexibility and speed in expressing characteristic problems of logic programming, and efficiently using specialised resolvers for integers, real numbers, finite domains, etc.
CLP(X) and domains. Ways of reducing the search space. Logic problems with domain constraints. Example: resource allocation, schedules. Search for optimum solutions in CLP (Constraint Logic Programming). CLP(X) and domains, ways of reducing the search space. Logic problems with domain constraints. Example: schedules (revisited). Search for optimum solutions in CLP (Constraint Logic Programming).
|
|
T | P | L | Alt | Ext. L | Stu | A. time | Total | ||
---|---|---|---|---|---|---|---|---|---|---|
4,0 | 0 | 4,0 | 0 | 4,0 | 4,0 | 0 | 16,0 | |||
Some problems that can be represented in propositional logic and in First Order Logic.
Verification of circuits. Verification of cryptographic protocols. Representation of finite state systems.
|
Total per kind | T | P | L | Alt | Ext. L | Stu | A. time | Total |
42,0 | 0 | 28,0 | 0 | 28,0 | 37,0 | 0 | 135,0 | |
Avaluation additional hours | 4,0 | |||||||
Total work hours for student | 139,0 |
On average, 3 hours a week will be spent on theory and/or problems. The actual number of hours in any one week will not be fixed since this would render class schedules too inflexible. The same applies to classes of problems.
Students are encouraged to work on their own. The teacher will be present in the 2 hours of weekly lab classes. His or she will work in a consulting role and evaluate students" work as they tackle the exercises.
The theory grade will be based on the written exam and carry a weight of 60%.
The lab grade (40%) will be based on assessment of the successive submissions on lab class exercises. Four such assignments are envisaged. However, an optional one may also be set at the end of the term to give students the opportunity to improve their marks or to make up for a fail mark.
The course is fairly self-contained and requires little in the way of previous knowledge.
Basic knowledge of logic is required at the level of the IL course. However, it should be noted that LI provides a broad review of these contents, albeit with a stronger orientation towards computing applications. It is desirable - though not essential - that students also have some knowledge of data structures and basic algorithms (Pred).