Saltar al contingut Menu
Map
  • Home
  • Information
  • Contact
  • Map

Logic in Information Technology (LI)

Credits Dept.
7.5 (6.0 ECTS) CS

Instructors

Person in charge:  (-)
Others:(-)

General goals

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.

Specific goals

Knowledges

  1. Learn the logical principles underlying logic programming, and deductive databases, and of other applications employing computing logic, such as the semantic web or verification.
  2. Learn the logic programming techniques and tools oriented towards rapid, flexible development of systems required to deal with a given problem.
  3. Learn some of the logic programming extensions oriented to achieving efficiency: partial evaluation, parallelisation, constrained logic programming (finite domains, Boolean domains, real domains).
  4. Learn some of the critical applications providing security, reliability, and privacy, as well as related techniques: tools based on the testing of models,

    abstract interpretation and automatic deduction.

Abilities

  1. Ability to choose the most suitable techniques and programming tools for dealing with a given practical problem.
  2. Ability to develop some of the practical applications using the tools studied.

Competences

  1. Improve knowledge of advanced techniques and skills in order to become better, more efficient programmers.

Contents

Estimated time (hours):

T P L Alt Ext. L Stu A. time
Theory Problems Laboratory Other activities External Laboratory Study Additional time

1. Introduction:
T      P      L      Alt    Ext. L Stu    A. time Total 
2,0 0 0 0 0 0 0 2,0
Some examples of problems. How can we solve these problems using

the techniques encountered in previous courses? How much time will the application of such techniques take? What guarantees are there regarding the reliability of such techniques?

2. Techniques based on propositional logic
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.











  • Laboratory
    Implementation of an imperative language (possibly C) of a simple algorithm for SAT.
    Learn PROLOG language at user level.
    Application of PROLOG to various problems.

3. Techniques based on First Order Logic
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.











  • Laboratory
    PROLOG Implementation of automatic deductive problems, deductive databases, and other types.

4. Programming logic
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.











  • Laboratory
    Advanced examples in logic programming.

5. Constraint 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).











  • Laboratory
    Problems involving planning, resource allocation, schedules, etc., using GNU PROLOG with constraints.

6. Verification applications
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.







  • Laboratory
    Use of CLP and other tools for dealing with verification problems.


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

Docent Methodolgy

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.

Evaluation Methodgy

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.

Basic Bibliography

  • W. F. Clocksin y C. S. Mellish Programación en Prolog, Gustavo Gili, 1993.
  • Robert Nieuwenhuis Apuntes de Lógica, Dept. LSI, 2004.
  • Pascal Van Hentenryck Constraint satisfaction in logic programming, The MIT Press, 1989.

Complementary Bibliography

  • Richard A. O'Keefe The Craft of PROLOG, the MIT Press, 1990.
  • Pascal Van Hentenryck The OPL optimization programming language, Pascal Van Hentenryck, 1999.
  • Moskewicz et al. Chaff: engineering an efficient SAT solver, Procs. Design Automation Conference, 2001.

Web links

  1. http://www.lsi.upc.es/~roberto


Previous capacities

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).


Compartir

 
logo FIB © Barcelona school of informatics - Contact - RSS
This website uses cookies to offer you the best experience and service. If you continue browsing, it is understood that you accept our cookies policy.
Classic version Mobile version