Saltar al contingut Saltar a navegacio
Mapa
  • Inicio
  • Información
  • Contacto
  • Mapa

Lógica en la Informática (LI)

Créditos Dept.
7.5 (6.0 ECTS) LSI

Profesores

Responsable:  Robert Lukas Mario Nieuwenhuis (roberto@lsi.upc.edu)
Otros:Albert Oliveras Llunell (oliveras@lsi.upc.edu)

Objectivos Generales

Esta asignatura profundizará en los conocimientos generales de la lógica como herramienta fundamental en la informática.

Además se desarrollarán habilidades en algunas áreas de aplicación que permitirán al estudiante crear en poco tiempo sistemas para la resolución de muy diversos problemas prácticos.

Se dedicará especial atención a la programación lógica y a la programación lógica con restricciones.

Objectivos Específicos

Conocimientos

  1. Conocer los fundamentos lógicos de la programación lógica, de las bases de datos deductivas, y de otras aplicaciones de la lógica en la informática, como la web semántica o la verificación.
  2. Conocer las técnicas y herramientas de programación lógica orientadas al desarrollo rápido y flexible de sistemas para un problema dado.
  3. Conocer algunas de las extensiones de la programación lógica orientadas a la eficiencia: evaluación parcial, paralelización, programación lógica con restricciones (dominios finitos, booleanos, reales).
  4. Conocer algunas aplicaciones críticas en seguridad, fiabilidad o privacidad y técnicas asociadas: herramientas basadas en comprobación de modelos, interpretación abstracta y deducción automática.

Habilidades

  1. Ante un problema práctico concreto, ser capaz de elegir las técnicas y herramientas de programación más adecuadas.
  2. Desarrollar algunas aplicaciones prácticas utilizando las técnicas y herramientas estudiadas.

Competencias

  1. Ser mejores programadores y más eficientes, a través de un mejor conocimiento de las técnicas y herramientas avanzadas.

Contenidos

Horas estimadas de:

T P L Alt L Ext. Est O. Ext.
Teoria Problemas Laboratorio Otras actividades Laboratorio externo Estudio Otras horas fuera del horario fijado

1. Introducción y motivación:
T      P      L      Alt    L Ext. Est    O. Ext. Total 
2,0 0 0 0 0 0 0 2,0
Algunos ejemplos de problemas. ¿Cómo los resolveríamos con las técnicas vistas en asignaturas previas? ¿Cuánto tiempo

nos costaría? ¿Qué sabríamos de las garantías de fiabilidad?

2. Técnicas basadas en lógica proposicional
T      P      L      Alt    L Ext. Est    O. Ext. Total 
9,0 0 6,0 0 6,0 8,0 0 29,0
Repaso de lógica proposicional.

Algoritmos: Resolución, Davis-Putnam-Logeman-Loveland, BDD"s.

Herramientas: Prolog, Chaff, paquetes de BDD"s.

Programación por traducción a SAT y uso de las herramientas asociadas.

Ejemplos de aplicaciones: problemas de horarios, etc.





  • Laboratorio:
    Implementación en un lenguaje imperativo (posiblemente C) de algún algoritmo sencillo para SAT.
    Aprendizaje del lenguaje Prolog a nivel de usuario.
    Implementación en Prolog de algún problema.

3. Técnicas basadas en lógica de Primer Orden
T      P      L      Alt    L Ext. Est    O. Ext. Total 
12,0 0 8,0 0 4,0 6,0 0 30,0
Repaso de lógica de primer orden.

Algoritmos: Resolución y sus restricciones, deducción automática.

Métodos basados en resolución: programación lógica, bases de datos deductivas.





  • Laboratorio:
    Implementación en Prolog de problemas de deducción automática y de bases de datos deductivas y de otros tipos.

4. Programación Lógica
T      P      L      Alt    L Ext. Est    O. Ext. Total 
6,0 0 4,0 0 8,0 10,0 0 28,0
Fundamentos: resolución SLD.

Optimizaciones: tipos de datos predefinidos, entrada-salida.

Diseño de programas declarativos.

Estructuras de datos avanzadas en programación lógica.





  • Laboratorio:
    Ejemplos avanzados de programación lógica.

5. Programación lógica con restricciones (Constraint Logical Programming)
T      P      L      Alt    L Ext. Est    O. Ext. Total 
9,0 0 6,0 0 6,0 9,0 0 30,0
¿Cómo obtener la flexibilidad y rapidez en la expresión del problema característica de la programación lógica, y a la vez tener la eficiencia del uso de resolvedores especializados para los enteros, los reales, dominios finitos, etc.?



CLP(X) y dominios,

Maneras de reducir el espacio de búsqueda.

Problemas lógicos con restricciones de otros dominios.

Ejemplo: asignación de recursos, horarios.

Búsqueda de soluciones óptimas con CLP.





CLP(X) y dominios,

Maneras de reducir el espacio de búsqueda.

Problemas lógicos con restricciones de otros dominios.

Ejemplo: horarios (revisited).

Búsqueda de soluciones óptimas con CLP.





  • Laboratorio:
    Problemas de planificación, asignación de recursos, horarios, etc., con el GNU prolog con restricciones.

6. Aplicaciones de verificación
T      P      L      Alt    L Ext. Est    O. Ext. Total 
4,0 0 4,0 0 4,0 4,0 0 16,0
Algunos problemas representables en lógica proposicional y en lógica de primer orden.

Verificación de circuitos.

Verificación de protocolos criptográficos.

Representación de sistemas de estados finitos.



  • Laboratorio:
    Uso de CLP y otras herramientas para problemas de verificación.


Total por tipo T      P      L      Alt    L Ext. Est    O. Ext. Total 
42,0 0 28,0 0 28,0 37,0 0 135,0
Horas adicionales dedicadas a la evaluación 4,0
Total horas de trabajo para el estudiante 139,0

Metodología docente

Habrá 3 horas semanales de teoría y/o problemas (para evitar una excesiva rigidez en la planificación, no hay un número fijo de horas por semana para problemas, ni clases específicas de sólo problemas).

Se fomentará el trabajo autónomo por parte del estudiante. El papel del profesor, que siempre estará presente en las 2 horas semanales de laboratorio, será en gran medida de consultor/evaluador de los trabajos que el estudiante realizará de forma autónoma a partir de un enunciado suficientemente específico.

Método de evaluación

Habrá un nota de teoría, obtenida del examen escrito, con un peso del 60%.

La nota de laboratorio (40%) se obtendrá a partir de la evaluación de las sucesivas entregas de los ejercicios en las clases de laboratorio (se prevé que sean unas cuatro entregas), aunque habrá una posibilidad opcional de mejora de esta nota, o de recuperación de cualquier suspenso, mediante un examen al final del cuatrimestre.

Bibliografía básica

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

Bibliografía complementaria

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

Capacidades previas

Se trata de una asignatura bastante autocontenida, que no requiere muchos conocimientos previos.

Se requieren conocimientos básicos de lógica, a nivel de la asignatura de IL, aunque en LI se realizará un amplio repaso de estos contenidos, con una visión más orientada a las aplicaciones en la informática.

Es deseable, pero no imprescindible, tener conocimientos de las estructuras de datos y algoritmos básicos (Pred).


Compartir

 
logo FIB © Facultad de Informática de Barcelona - Contacto - RSS