Información general


  • Tipo de asignatura: Básica
  • Coordinador: Adso Fernández Baena
  • Trimestre: 3
  • Créditos: 6
  • Profesorado:

Idiomas de impartición


  • Català

Descripción


La matemática discreta estudia estructuras matemáticas que son intrínsecamente discretas, es decir, que no son continuas. Por ejemplo la recta de números reales es continua ya que varían suavemente (no podemos decir qué número real viene después de otro, por ejemplo no sabemos qué número va después de 1,0) en cambio la recta de los números enteros es discreta ya que podemos distinguir claramente sus valores (después del 1 viene el 2). En esta asignatura estudiaremos la lógica proposicional y teoría de grafos que son dos disciplinas muy utilizadas en el campo de la computación. La lógica es utilizada en la programación, de hecho existe el paradigma de programación lógica del mismo modo que hay el imperativo y funcional, en bases de datos, en el diseño y verificación de sistemasy en la inteligencia artificial entre otros. En el caso de los grafos son una estructura matemática muy usada en la computación (y en otras disciplinas) para representar problemas, datos, conceptos y sus interrelaciones. Son estructuras fácilmente programables de las que se conocen muchas propiedades matemáticas que se pueden usar para validar la corrección de la solución propuesta a problemas computacionales. También estudiaremos los números enteros, los enteros congruentes y las ecuaciones congruentes que dan lugar a las técnicas modernas de codificación de mensajes.

 

Esta asignatura dispone de recursos metodológicos y digitales para hacer posible su continuidad en modalidad no presencial en el caso de ser necesario por motivos relacionados con el Covid-19. De esta forma se asegurará la consecución de los mismos conocimientos y competencias que se especifican en este plan docente.

Resultados de aprendizaje


A nivel general, esta asignatura contribuye a los siguientes resultados de aprendizaje especificados para la materia a la que pertenece (Fundamentos científicos):

  • Familiarizarse con el lenguaje y la lógica matemática y conocer sus aplicaciones en el ámbito de la informática. Saber expresar con precisión conceptos matemáticos. Ser capaz de entender una demostración y realizar demostraciones usando varios métodos.
  • Conocer los grafos como modelo abstracto de relación binaria y sus posibles aplicaciones en el ámbito de la informática
  • Conocer las propiedades de los números enteros y los enteros modulares, y saber operar y resolver ecuaciones en estos conjuntos

A un nivel más concreto, al finalizar la asignatura el estudiante debe ser capaz de:

  • RA1: Formalizar el lenguaje natural con enunciados
  • RA2: Resolver (en el sentido de la lógica) razonamientos usando la lógica de enunciados
  • RA3: Conocer las propiedades de los números enteros congruentes
  • RA4: Resolver ecuaciones lineales congruentes
  • RA5: Describir los grafos como estructuras matemáticas útiles para modelar problemas
  • RA6: Implementar algoritmos de recorridos de grafos
  • RA7: Resolver problemas usando la teoría de grafos
  • RA8: Demostrar formalmente la corrección de los algoritmos sobre grafos

Metodologia de trabajo


Todos los conceptos teóricos de la materia se expondrán en clases de teoría (grupos grandes). En estas clases, y a discreción de los docentes impartidores, también se resolverán ejercicios y problemas de carácter más práctico. Asimismo, y siempre a discreción de los impartidores, se podrá pedir a los estudiantes que resuelvan, de forma individual o en grupo, problemas y / o ejercicios breves. Estas actividades, breves y optativas, servirán al estudiante como instrumento de autoevaluación de su logro de los contenidos de la materia y podrán ser utilizados por parte del docente para tomar decisiones sobre la calificación final del estudiante  aúnque nunca en detrimento de la calificación numérica calculada según el sistema de calificación especificado por la asignatura.

 

Contenidos


  1. Lógica de enunciados
    1. Lógica de enunciados y su lenguaje.
    2. Formalización Interpretación de los enunciados
    3. Categorización de los enunciados (tautologías, contradicciones y contingencias)
    4. Categorización de conjuntos de enunciados (consistentes e inconsistentes)
    5. Razonamientos válidos e inválidos.
    6. Contraejemplos
    7. Formas normales
    8. El método de resolución
    9. resolución Lineal
  2. Números enteros
    1. Propiedades y divisibilidad
    2. Enteros congruentes
    3. Ecuaciones lineales de congruencias
  3. Grafos y dígrafos
    1. definiciones básicas
    2. Representación matricial y con listas
    3. Caminos, conectividad y distancia
    4. Isomorfismo entre grafos
    5. Recorridos en profundidad y anchura
    6. Dígrafos y dags
    7. ordenación topológica
    8. Árboles de expansión mínima: algoritmos de Prim y Kruskal
    9. Caminos más cortos: algoritmo de Dijkstra

Actividades de aprendizaje


Se pone a disposición de los estudiantes una serie de actividades de carácter eminentemente práctico (ejercicios cortos, problemas ...) que son la base de las actividades de aprendizaje de la asignatura. Estas actividades los estudiantes / se las tendrán que resolver, a menudo de manera no presencial, siguiendo las indicaciones de los docentes y también serán trabajadas en clase. Si bien estas actividades tendrán carácter optativo (los docentes no verificarán de manera individualizada la realización por parte de los estudiantes), serán imprescindibles para alcanzar los conocimientos teórico-prácticos de la asignatura.


Con el objetivo de recoger evidencia del logro de los resultados de aprendizaje esperados se realizarán las siguientes actividades de carácter evaluativo:
Prueba escrita 1: Prueba individual de aplicación práctica (resolución de ejercicios y problemas) de los conceptos teóricos y procedimientos prácticos de lógica de enunciados y predicados y los números enteros. (Evidencia de los resultados de aprendizaje RA1 - RA4 y relacionada con las competencias EFB1, EFB3, B1 y B3)
Prueba escrita 2: Prueba individual de aplicación práctica (resolución de ejercicios y problemas) de los conceptos teóricos y procedimientos prácticos de la teoría de grafos (Evidencia de los resultados de aprendizaje RA5 - RA8 y relacionada con la competencia EFB3)
Resolución de problemas tipo: Los estudiantes realizarán ejercicios propuestos por el profesor. Estos ejercicios se podrán exponer en clase y serán realizados de forma individual o en grupo según indicaciones del profesor. Estos problemas tienen como objetivo ayudar al estudiante a comprender los conceptos básicos de matemática discreta, y detectar deficiencias en el propio conocimiento para superarlas con ayuda de los compañeros y el profesor. (Relacionada con todos los resultados de aprendizaje y las competencias EFB1, EFB3, B1 y B3)
Implementación de algoritmos sobre grafos: Los estudiantes realizarán ejercicios de programación de algoritmos sobre grafos. El objetivo es consolidar los conocimientos de la teoría de grafos, reconocer el vínculo entre la teoría de los grafos y su aplicación práctica, así como detectar deficiencias en el propio conocimiento para superarlas con ayuda de los propios compañeros y el profesor. (Relacionada con RA5 - RA8 y las competencias EFB1, EFB3, B1 y B3)

A continuación se explicitan los aspectos más importantes de cada competencia asignada a la asignatura:

  • B1: resolución de problemas dentro de su área de estudio.
  • B3: reunir e interpretar información relevante para la materia
  • EFB1: resolución de problemas matemáticos
  • EFB3: dominar conceptos básicos de matemática discreta, lógica, algorítmica y complejidad computacional
  • T1: tercera lengua

Para superar (aprobar) las actividades evaluativas, los estudiantes deberán demostrar

  • Que han adquirido los conocimientos teóricos relativos a los contenidos de la asignatura y que su comprensión les permite llevarlos a la práctica [MECES-2 punto a, punto c]
  • Que pueden desarrollar soluciones a problemas que, si bien son similares a otros vistos anteriormente, presentan aspectos que son nuevos [MECES2 punto f]

Nota: Mucha documentación estará en inglés por lo que el estudiante deberá tener el conocimiento mínimo de comprensión lectora (Relacionado con la competencia T1)
 

Sistema de evaluación


La calificación final es la suma ponderada de las calificaciones de las actividades:

ACTIVIDAD Y PESO

  1. Prueba Escrita I 45% - 50%
  2. Prueba Escrita II 45% - 50%
  3. Resolución de problemas tipo 0% - 5%
  4. Implementación de algoritmos sobre grafos 0% - 5%

Si la media de las pruebas escritas es inferior a 3 la calificación final de la asignatura será la media de estas actividades.

Recuperación

  • Sólo se podrán recuperar las actividades Prueba Escrita I y II. Se aplicará la ponderación descrita anteriormente siempre que la nueva calificación no sea inferior a 3,5. En caso contrario la asignatura no se consideró recuperada.
  • Si un estudiante no se ha presentado a alguno de los exámenes y / o no ha presentado ninguna de las actividades 3 y 4 no podrá presentarse a la recuperación.

Normas de realización de las actividades

Para cada actividad, los docentes informarán de las normas y condiciones particulares que las rijan.

Las actividades unipersonales presuponen el compromiso del estudiante de realizarlas de manera individual. Se considerarán suspendidas todas aquellas actividades en las que el estudiante no se ajuste a este compromiso, independientemente de su papel (emisor o receptor). Igualmente, las actividades que se deban realizar en grupos presuponen el compromiso por parte de los estudiantes que lo integran de realizarlas en el seno del grupo. Se considerarán suspendidas todas aquellas actividad en la que el grupo no haya respetado este compromiso con independencia de su papel (emisor o receptor).

En las actividades realizadas en grupo el docente puede, en base a la información de que disponga, personalizar la calificación para cada integrante del grupo.

Es potestativo de los docentes aceptar o no entregas fuera de los plazos que se indiquen. En caso de que estas entregas fuera de plazo se acepten, es potestativo del docente decidir si aplica alguna penalización y la cuantía de la misma.

Bibliografía


Básica

Enric Sesa and Josep Roure, "Propositional logics: class notes". Pubilicació interna TCM

Josep Roure, "Nombres enters congruents i equacions". Apunts de classe. Publicació interna TCM

Josep Roure, "Graphs class notes". Publicació interna TCM


Complementaria

Robert Sedgewick and Kevin Wayne (2011), "Algorithms", Fourth Edition, Addison-Wesley.