Curso 2013-14
Lógica Computacional
| Titulación: | Código: | Tipo: |
| Grado en Ingeniería Informática | 21422 | Obligatoria 2º curso |
| Grado en Ingeniería Telemática | 22606 | Optativa |
| Grado en Ingeniería en Sistemas Audiovisuales | 22672 | Optativa |
| Créditos ECTS: | 4 | Dedicación: | 100 horas | Trimestre: | 3º |
| Departamento: | Dpto. de Tecnologías de la Información y las Comunicaciones |
| Coordinador: | Héctor Palacios |
| Profesorado: | Teoría: Héctor Palacios Prácticas: Héctor Palacios Seminarios: Héctor Palacios, Filippos Kominis |
| Idioma: | Material: Inglés, Castellano Teoría: Héctor Palacios (castellano) Prácticas: Héctor Palacios (castellano) Seminarios: Héctor Palacios (castellano), Filippos Kominis (castellano/inglés) |
| Horario: | |
| Campus: | Campus de la Comunicación - Poblenou |
La asignatura Lógica Computacional es una asignatura obligatoria que se ofrece en el grado en ingeniería informática, formando parte del
segundo curso. En la asignatura se estudian los aspectos deductivos y algorítmicos tanto de la lógica proposicional como de la lógica de predicados, y así como sus problemas computacionales computacionales. La asignatura tiene un componente teórico y otro práctico. Dentro del componente teórico el énfasis está en la comprensión de los conceptos a nivel intuitivo y de la utilización de lenguaje matemático.
La asignatura está compuesta de tres actividades principales: clases de teoría, seminarios y laboratorios. En las clases de teoría se introducen los conceptos formales y se muestran ejemplos de su aplicación. En los seminarios los alumnos resuelven pequeños problemas. Cada problema corresponde a los conceptos introducidos en clase de teoría. En los laboratorios se presentan problemas de mayor complejidad y de carácter más computacional para los alumnos tengan la oportunidad de poner en práctica los conceptos
aprendidos.
Objetivos de aprendizaje
El objetivo de la asignatura es entender aspectos deductivos y algorítmicos de la lógica proposicional y de predicados, y así como sus problemas computacionales computacionales. Asimismo, los estudiantes deberían desarrollar
competencias para entender las diferencias entre los diversos tipos de lógica e identificar el mejor formalismo para especificar diferentes problemas y poder solucionarlos de forma computacional.
Los conocimientos previos para el seguimiento de la asignatura son ciertas nociones
de matemáticas básicas adquiridas en la enseñanza secundaria
obligatoria y durante los primeros tres cursos de los estudios. En particular, los
conocimientos previos requeridos para la asignatura son:
• Nociones algebraicas básicas: funciones, conjuntos y operaciones
elementales sobre conjuntos, relaciones de equivalencia.
• Nociones básicas de lógica matemática: relaciones, conectivas lógicas.
• Aritmética básica.
• Capacidad básica para comprender y escribir expresiones matemáticas a nivel elemental.
El objetivo fundamental de la asignatura es que los alumnos adquieran los
ideas fundamentales relacionados con los aspectos deductivos y algorítmicos
de la lógica proposicional y de predicados.
| Competencias transversales | Competencias específicas |
|---|---|
|
Instrumentales 1. Capacidad de razonar a nivel abstracto
|
1. Capacidad de entender a nivel intuitivo y formal |
En la evaluación continuada se tiene en cuenta cada una de las tres actividades que constituyen la asignatura: clases de teoría, laboratorios y seminarios:
T: la evaluación de la teoría mediante un examen final
L: la evaluación de los laboratorios mediante las prácticas de programación.
S: la evaluación de los seminarios
En la evaluación contínua, hay que aprobar el laboratorio y también aprobarse la suma de la evaluación de los seminarios mas el examen final. Es decir,
L tiene que estar aprobado.
T + S tiene que estar aprobado.
Nota Final = 0,6 * T + 0,2 * L + 0,2 * S
El examen de teoría se realizará sobre los contenidos desarrollados a clase de teoría y los seminarios. Es un examen escrito e individual que evalúa todas las competencias desarrolladas a lo largo de la asignatura.
En los laboratorios se realizan un serie de prácticas que ponen a prueba la capacidad
de los alumnos de aplicar la teoría en forma de programas de ordenador. Las prácticas se realizan en pareja, de forma que los
alumnos tengan que cooperar y saber comunicarse para resolver los
problemas.
Antes de cada seminario se presentarán problemas a los alumnos para que ellos los resuelvan antes de la sesión, como una preparación previa al seminario. Estos problemas corresponden a conceptos o conocimientos tratados en clase de teoría. Se pedirá a los alumnos que presenten sus soluciones a la pizarra o por escrito. Como parte de la evaluación, se realizarán dos pruebas cortas, y dos tareas para entregar por escrito.
En caso de no aprobar la asignatura, el alumno tiene derecho a una convocatoria en
el mes de julio, pero sólo si había aprobado el laboratorio (L). La nota de esta convocatoria se obtendrá en un examen.
Nota Julio = 1,0*T+0*L +0*S (si había aprobado L)
1. Lógica: Qué es, historia, usos en la informática. Concepto de derivación
formal. Ejemplos de las matemáticas.
2. Lógica proposicional.
1. Lenguaje formal, formulas.
2. Modelación.
3. Teoría de pruebas: sistema de deducción natural para la lógica
proposicional. Pruebas, derivabilidad.
4. Semántica: tablas de verdad y valuaciones. Satisfactibilidad y
Consecuencia Lógica. Tautologías.
5. Formas Normales. Resolución. Clausulas de Horn. SAT y SAT solvers.
3. Lógica de predicados.
1. Motivación. Lenguaje formal, formulas.
2. Modelación.
3. Teoría de pruebas para lógica de predicados: sistema de deducción
natural. Pruebas, derivabilidad.
4. Semántica: interpretaciones de formulas de la lógica de predicados.
5. Satisfactibilidad y Consecuencia Lógica. Resolución en lógica de
predicados.
El proceso habitual de aprendizaje empieza con una sesión de teoría en la que se presentan ciertos fundamentos teórico-prácticos. Esta actividad se realiza con todo el grupo de estudiantes. El estudiante tendrá que complementar esta actividad con una lectura detenida de sus propios apuntes y el material
adicional que el profesor haya proporcionado. Por ejemplo, una sesión de teoría de 2 horas, convenientemente aprovechadas, requerirá un trabajo adicional fuera del aula de 1 hora por parte del estudiante.
Posteriormente se realizarán algunas sesiones de ejercicios, en las cuales el estudiante
pone en práctica los conceptos y técnicas presentadas a la sesión de teoría,
mediante la resolución de pequeños problemas. Para los primeros ejercicios de la sesión
se pueden proporcionar las soluciones, pero por el resto no. El objetivo es que consolide
los fundamentos para que posteriormente pueda resolver problemas de mayor
complejidad. Esta actividad se realiza en
cuatro grupos pequeños de estudiantes.
El siguiente paso en el proceso de aprendizaje es la sesión de prácticas. En ella se proponen unos problemas más grandes que requieren integrar diferentes conceptos y técnicas. Esta actividad se realiza por parejas, en grupos de unos 20 estudiantes, y se presupone que continúa fuera del aula.
Están previstas 18h de teoría, 12h de seminario, y 6h en aula de práctica, aunque esta continúa fuera del aula.
Fuentes de información para el aprendizaje. Bibliografía básica (apoyo papel y electrónico)
Logic in Computer Science
Michael R.A. Huth, Mark D Ryan
Cambridge University Press. 2nd edition, 2004.
Cubrimos la primera parte, páginas 1-131. Excepto las sección 1.6 que haremos de
manera diferente (usándo el método DPLL).
Fuentes de información para el aprendizaje. Bibliografía complementaria (apoyo papel y electrónico)
Mathematical Logic for Computer Science
Mordechai Ben-Ari
Springer (2003).
Logic and its Applications
Edmund Burke, Eric Foxley
Prentice Hall (1996)
Fuentes de información para el aprendizaje. Bibliografía de refuerzo (apoyo papel y electrónico)
Recursos didácticos. Material docente de la asignatura
Web de la asignatura
Apuntes
Colección de ejercicios (con solución)
Enunciados de las prácticas
Recursos didácticos. Materiales y herramientas de apoyo
http://www.diveintopython.org
http://www.swi-prolog.org/