estructuras_discretas_logicas

1 de 11

Asignatura: Estructuras Discretas y Lgica Cdigo: 17824 Centro: Escuela Politcnica Superior Titulacin: Grado en Ingeniera Informtica Nivel: Grado Tipo: Formacin Obligatoria

N de crditos: 6

GUA DOCENTE DE ESTRUCTURAS DISCRETAS Y LGICA

La presente gua docente corresponde a la asignatura Estructuras Discretas y Lgica (EDyL), aprobada para el curso lectivo 2012-2013 en Junta de Centro y publicada en su versin definitiva en la pgina web de la Escuela Politcnica Superior. Esta gua docente de EDyL aprobada y publicada antes del periodo de matrcula tiene el carcter de contrato con el estudiante.

2 de 11


N de crditos: 6

ASIGNATURA

Estructuras Discretas y Lgica (EDyL)

1.1. Cdigo

17824

1.2. Materia

Estructuras Discretas y Lgica

1.3. Tipo

Formacin obligatoria

1.4. Nivel

Grado

1.5. Curso

1 ingeniera informtica, 2 Plan conjunto Informtica/Matemticas

1.6. Semestre

1

1.7. Nmero de crditos

6 crditos ECTS

1.8. Requisitos previos

No son necesarios requisitos previos para cursar la asignatura.

3 de 11


N de crditos: 6

1.9. Requisitos mnimos de asistencia a las sesiones presenciales

Se plantean dos itinerarios, uno con asistencia obligatoria a clase y otro sin ella, los estudiantes pueden optar por uno u otro a principio del curso y cumplir con los distintos requisitos de evaluacin que conlleva cada uno de los modelos, publicados en la presente gua docente (ver apartado 4). ITINERARIO CON ASISTENCIA OBLIGATORIA A CLASE La asistencia es obligatoria al menos en un 85%. ITINERARIO SIN ASISTENCIA OBLIGATORIA A CLASE La asistencia es muy recomendable aunque no obligatoria.

1.10. Datos del equipo docente

Docente: Dr. Pilar Rodrguez Marn (Coordinadora) Departamento: Ingeniera Informtica Centro: Escuela Politcnica Superior Despacho: Edificio B, N 326 Telfono: +34 91 497 2283 Correo electrnico: [email protected] Pgina web: Horario de atencin al alumnado: Por peticin Docente: Dr. Xavier Alamn Roldn Departamento: Ingeniera Informtica Centro: Escuela Politcnica Superior Despacho: Edificio B, N 420 Telfono: +34 91 497 2250 Correo electrnico: [email protected] Pgina web: http://www.eps.uam.es/~xalaman Horario de atencin al alumnado: Por peticin Docente: Dr. Alberto Surez Gonzlez Departamento: Ingeniera Informtica Centro: Escuela Politcnica Superior Despacho: Edificio B, N 309 Telfono: +34 91 497 2286 Correo electrnico: [email protected] Pgina web: http://www.eps.uam.es/~asuarez Horario de atencin al alumnado: Por peticin

4 de 11


N de crditos: 6

1.11. Objetivos del curso

Las competencias que se pretenden adquirir con esta asignatura son: B3: Capacidad para comprender y dominar los conceptos bsicos de matemtica discreta, lgica, algortmica y complejidad computacional, y su aplicacin para la resolucin de problemas propios de la ingeniera.

Los objetivos que se pretenden alcanzar con esta asignatura son:

OBJETIVOS ESPECIFICOS POR TEMA

TEMA 1.- Introduccin a la lgica proposicional y de predicados

1.1.

Saber definir y manejar los conceptos bsicos de la lgica proposicional. Ser capaz de formular frmulas bien formadas (fbf) de lgica proposicional a partir de frases en lenguaje natural. Ser capaz de interpretar clusulas de lgica proposicional. Ser capaz de entender una deduccin lgica. Ser capaz de formular una deduccin lgica sencilla. Ser capaz de convertir una fbf en lgica de predicados una clusula a formas normales equivalentes.

1.2.

Entender la relacin entre razonamiento formal y deduccin natural. Ser capaz de utilizar tablas de verdad para realizar la demostracin de fbf es consecuencia lgica de una base de conocimiento. Demostraciones mediante inferencia: deduccin, reduccin al absurdo. Resolucin.

1.3.

Saber definir y manejar los conceptos bsicos de la lgica de predicados. Ser capaz de formular frmulas bien formadas de lgica de predicados a partir de frases en lenguaje natural. Ser capaz de interpretar clusulas de lgica de predicados. Ser capaz de entender una deduccin lgica. Ser capaz de convertir una fbf en lgica de predicados una clusula a formas normales utilizando skolemizacin y unificacin. Ser capaz de entender y formular deducciones lgicas sencillas.

TEMA 2.- Principios de enumeracin y combinatoria

2.1. Saber emplear las reglas de la suma y del producto para contar sucesos.

2.2. Saber definir las permutaciones. Ser capaz de calcular permutaciones.

2.3. Saber definir las combinaciones. Ser capaz de calcular combinaciones.

2.4. Conocer los nmeros combinatorios y saber aplicar el teorema del binomio.

2.5. Ser capaz de calcular combinaciones con repeticin.

TEMA 3.- Grafos.

3.1. Sabe definir qu es un grafo, y los tipos de grafos existentes. Saber definir qu es un camino.

3.2. Ser capaz de calcular el grado de un vrtice y la distancia entre dos vrtices.

3.3. Ser capaz de pasar un grafo a representacin matricial y viceversa.

3.4. Saber definir los grafos eulerianos y emplear los algoritmos particulares.

3.5. Saber definir los grafos hamiltonianos y emplear los algoritmos particulares.

3.6. Saber encontrar el camino ms corto en un grafo.

5 de 11


N de crditos: 6

TEMA 4.- rboles

4.1. Saber definir los conceptos bsicos de rboles.

4.2. Ser capaz de emplear todos los algoritmos de recorrido de rboles.

4.3. Saber definir y emplear rboles binarios.

4.4. Saber definir y encontrar un rbol extendido mnimo.

TEMA 5.- Modelos de computacin y mquinas de Turing 5.1. Ser capaz de definir y comparar distintos modelos de computacin.

5.2. Ser capaz de analizar y disear autmatas finitos elementales.

5.3. Saber definir la mquina de Turing y ser capaz de analizar el funcionamiento de mquinas de Turing elementales. Saber enunciar la tesis de Church-Turing.

5.4. Ser capaz de analizar el funcionamiento de una mquina de Turing Universal

5.5. Saber demostrar el teorema de la parada de la mquina de Turing

1.12. Contenidos del programa

Programa Sinttico

UNIDAD 1. Introduccin a la lgica proposicional y de predicados. UNIDAD 2. Principios de enumeracin y combinatoria. UNIDAD 3. Grafos. UNIDAD 4. rboles. UNIDAD 5. Modelos de computacin y mquinas de Turing.

Programa Detallado

1. Introduccin a la lgica proposicional y de predicados. 1.1. Lgica proposicional

1.1.1. Representacin del conocimiento, razonamiento y lgica. 1.1.2. Sintaxis: tomos, conectores lgicos, frmulas bien formadas. 1.1.3. Semntica: Tablas de verdad e interpretacin. 1.1.4. Reglas de equivalencia 1.1.5. Satisfacibilidad lgica. 1.1.6. Reglas de inferencia en lgica proposicional. 1.1.7. Formas normales.

1.2. Demostracin automtica de teoremas. 1.2.1. Razonamiento natural y razonamiento formal. 1.2.2. PSAT, bsqueda de modelos y demostracin de teoremas. 1.2.3. Demostracin mediante tablas de verdad. 1.2.4. Demostracin mediante inferencia: Deduccin y reduccin al absurdo. 1.2.5. Resolucin.

1.3. Lgica de predicados 1.3.1. Definiciones bsicas: sintaxis y semntica. 1.3.2. Funciones y predicados. 1.3.3. Cuantificadores. 1.3.4. Reglas de equivalencia 1.3.5. Representacin del conocimiento en lgica de predicados

6 de 11


N de crditos: 6

2. Principios de enumeracin y combinatoria. 2.1. Regla del producto y de la de la suma. 2.2. Principio del palomar. 2.3. Permutaciones y Combinaciones. 2.4. Coeficientes binomiales. 2.5. Combinaciones y permutaciones con repeticin.

3. Grafos. 3.1. Definiciones bsicas. 3.2. Representacin de grafos. Isomorfismo de grafos. 3.3. Caminos, circuitos y conectividad. 3.4. Caminos eulerianos y hamiltonianos. 3.5. Caminos de longitud mnima. 3.6. Algoritmos sobre grafos

4. rboles. 4.1. Definiciones bsicas de rboles. 4.2. Aplicaciones de rboles. 4.3. Recorridos en rboles 4.4. rboles generadores. 4.5. rbol generador mnimo. 4.6. Algoritmos sobre rboles

5. Modelos de computacin y mquinas de Turing. 5.1. Modelos de computacin. 5.2. Autmatas finitos y lenguajes. 5.3. La mquina de Turing. Tesis de Church-Turing. 5.4. La mquina de Turing Universal. 5.5. El teorema de la parada de la mquina de Turing.

1.13. Referencias de consulta

1. Matemtica Discreta, K.H. Rosen, Ed. McGraw Hill, 2004.

2. Matemticas Discretas y Combinatoria (3 Ed.), Ralph P. Grimaldi, Ed. Prentice may, 1998.

3. Matemticas Discretas, T. Veerarajan, Ed. McGraw Hill, 2008.

4. Nilsson, N.J.: "Artificial Intelligence, a new synthesis", Ed. Morgan Kaufmann Publishers, 1998

5. Conferencias sobre computacin, Richard P. Feynman, Ed. Drakontos clsicos, 2003.

6. Lgica computacional, Enrique Paniagua Ars et al., Ed. Thomson, 2003.

7. Elementos de lgica formal, Calixto Badesa et al., Ed. Ariel, 2003.

7 de 11


N de crditos: 6

8. Artificial Intelligence: a modern approach, S. Russell y P. Norvig, Ed. Prentice Hall, 1995.

9. An introduction to algorithms, T.H. Cormen,The MIT Press (2009)

Bibliografa principal y secundarias asociadas al temario propuesto: UNIDAD 1. Introduccin a la lgica proposicional y de predicados. Principal: Ref. 4, Captulos 13 al 16 Secundarias: Ref. 1, Caps. 1.1,1.2,1.3

Ref. 6, Captulo 5 Ref. 7, Captulos 6 al 10 y 12 al 14 Ref. 8, Captulos 7 y 8

UNIDAD 2. Principios de enumeracin y combinatoria. Principal:

Ref. 1: Captulo 4 Secundarias:

Ref. 2: Captulo 1 Ref. 3: Captulo 6

UNIDAD 3. Grafos. Principal:


Ref. 3: Captulo 7 Ref. 2: Captulo 11 Ref. 9: Sec. VI

UNIDAD 4. rboles. Principal:


Ref. 3: Captulo 7 Ref. 2: Captulos 12 y 13 Ref. 9: Sec. VI

UNIDAD 5. Modelos de computacin y mquinas de Turing. Principal: Ref. 5: Captulo 3

8 de 11


N de crditos: 6

2. Mtodos docentes

La metodologa utilizada en el desarrollo de la actividad docente incluye los siguientes tipos de actividades: *Clases de teora: Actividad del profesor

Clases expositivas simultaneadas con la realizacin de ejercicios. Se utilizar la pizarra, combinada con presentaciones en formato electrnico.

Actividad del estudiante: Actividad presencial: Toma de apuntes, participar activamente en clase respondiendo a las cuestiones planteadas. Resolucin de los ejercicios propuestos durante el desarrollo de las clases. Actividad no presencial: Preparacin de apuntes, estudio de la materia y realizacin de los ejercicios propuestos.

*Clases de problemas en aula: Actividad del profesor

Primera parte expositiva, una segunda parte de supervisin y asesoramiento en la resolucin de los problemas por parte del estudiante y una parte final de anlisis del resultado y generalizacin a otros tipos de problemas. Se utiliza bsicamente la pizarra con proyecciones en formato electrnico para las figuras.

Actividad del estudiante: Actividad presencial: Participacin activa en la resolucin de los problemas y en el anlisis de los resultados. Actividad no presencial: Realizacin de otros problemas, planteados a travs del Campus Virtual y no resueltos en clase, y estudio de los planteados en las mismas. Estudio y planteamiento de modificaciones que permitan la optimizacin de las soluciones planteadas.

*Seminarios: Actividad del profesor:

Propuesta de temas a exponer por parte de los estudiantes, tutorizacin de la preparacin de cada tema, soporte mientras se presenta.

Actividad del estudiante: Actividad presencial: Presentacin del tema ante la clase. Discusin del tema por parte del resto de los estudiantes. Actividad no presencial: Estudio de la bibliografa sugerida por el profesor, elaboracin de la presentacin.

9 de 11


N de crditos: 6

3. Tiempo de trabajo del estudiante

4. Mtodos de evaluacin y porcentaje en la calificacin final

La asignatura se punta sobre 10 puntos.

Las condiciones para optar a evaluacin continua son

o Asistencia regular a clase (85% de asistencia)

o Entrega de los ejercicios resueltos.

o Realizacin de las pruebas intermedias.

o Participacin activa en clase.

Las pruebas intermedias consistirn en tres pruebas escritas correspondientes a una parte de la asignatura. Las pruebas escritas podrn incluir tanto cuestiones tericas, incluyendo cuestiones tipo test, como resolucin de problemas.

La ponderacin de las pruebas ser 0.4 [Prueba 1] + 0.2 [Prueba 2] + 0.4 [Prueba 3]

La prueba final consistir en un examen escrito cuyo contenido abarca a todos los objetivos que los estudiantes deben alcanzar durante el curso. Los estudiantes que hayan optado por la evaluacin continua estarn exentos de algunos de los ejercicios de la prueba final.

La nota de Teora se calcular

o Dentro del itinerario de evaluacin continua:

0,6*calificacin de la prueba final + 0,4*calificacin media ponderada de las pruebas intermedias, siempre que se obtenga una nota de al menos 4 puntos en el examen final.

o La calificacin del estudiante que no pueda optar, o desee renunciar, a la evaluacin continua, ser de la prueba final nicamente.

N de horas Porcentaje

Presencial

Clases tericas 46 h (30%)

62 h (40%) Clases de ejercicios 8 h (5%)

Realizacin de pruebas escritas parcial y final 8 h (5%)

No presencial

Estudio semanal de la teora 34 h (24%)

88 h (60%) Realizacin de ejercicios 24 h (16%)

Preparacin de las pruebas 30 h (20%)

Carga total de horas de trabajo: 25 horas x 6 ECTS 150 h

10 de 11


N de crditos: 6

Para aprobar la asignatura la nota de Teora tiene que ser de al menos 5 puntos

Los seminarios, la entrega de ejercicios y la participacin en clase sern valorados como parte de la nota final de la asignatura, sumando hasta un punto extra a la nota de Teora. Para recibir esta calificacin, es necesario

o Cumplir las condiciones para optar por evaluacin continua.

o La nota de Teora antes de sumarle el punto extra correspondiente a seminarios y ejercicios debe ser de al menos de 5 puntos.

5. Cronograma

Semana Actividad Presencial

Actividad No Presencial Terica en Aula Seminario/Problemas

1

Presentacin

Estudio de la bibliografa facilitada para la U1.

Resolucin de problemas de la U1.

Sesin 1 Unidad1

Sesin 2 Unidad1

Sesin 3 Unidad1

2

Sesin 4 Unidad1

Sesin 5 Unidad1

Sesin 6 Unidad1

Sesin 7 Unidad1

3

Sesin 8 Unidad1 Ejercicios U1 (2 horas) [Lgica proposicional]

Sesin 9 Unidad1

4

Sesin 10 Unid. 1

Sesin 11 Unid. 1

Sesin 12 Unid. 1

Sesin 13 Unid. 1

5 Sesin 14 Unid. 1 Ejercicios U1 (2 horas)

[Lgica de predicados]


Resolucin de problemas de la U2.

Sesin 1 Unidad2

6

prueba 1

Sesin 2 Unidad2

Sesin 3 Unidad2

Sesin 4 Unidad2

7

Sesin 5 Unidad2

Sesin 6 Unidad2

Sesin 7 Unidad2

Sesin 8 Unidad2

8 Sesin 9 Unidad2

Ejercicios U2 (2 horas) Sesin 10 Unid. 2

11 de 11


N de crditos: 6

9

prueba 2


Sesin 1 Unidad3

Sesin 2 Unidad3

Sesin 3 Unidad3

10

Sesin 4 Unidad3

Sesin 5 Unidad3

Sesin 6 Unidad3

Sesin 7 Unidad3

11 Sesin 1 Unidad4

Ejercicios U3 (2 horas) Estudio de la bibliografa

facilitada para la U4. Resolucin de problemas

de la U3.

Sesin 2 Unidad4

12

Sesin 3 Unidad4

Sesin 4 Unidad4

Sesin 5 Unidad4

Sesin 1 Unidad5

Estudio de la bibliografa facilitada para la U5

Resolucin de problemas

de la U4

13 Sesin 2 Unidad5

Ejercicios U4 (2 horas) Sesin 3 Unidad5

14

prueba 3

Sesin 4 Unidad5

Sesin 5 Unidad5

Sesin 6 Unidad5

Documents

estructuras_discretas_logicas