Información general


Tipo de asignatura: básica

Coordinador: Ana Beatriz Pérez Zapata

trimestre: Tercer trimestre

Créditos: 6

Profesorado: 

Alfonso Palacios González
Carlos Bonet Papell 

Idiomas de impartición


  • Català

Esta asignatura se imparte en catalán, pero la bibliografía y la documentación es mayoritariamente en inglés. 

Competencias


competencias básicas
  • B1_Que los estudiantes hayan demostrado tener y comprender conocimientos en un área de estudio que tenga su base en la educación secundaria general, y se acostumbre a encontrar a un nivel que, aunque con el soporte de libro de texto avanzados, incluya también algunos aspectos que implican conocimientos procedentes de la vanguardia de su campo de estudio

     

  • B3_Que los estudiantes tengan la capacidad de reunir e interpretar datos relevantes (normalmente dentro de su área de estudio), para emitir juicios que incluyan una reflexión sobre temas relevantes de carácter social, científico o ético

     

Competencias específicas
  • EFB1_Capacidad para la resolución de los problemas matemáticos que puedan plantearse en la ingeniería. Aptitud para aplicar los conocimientos sobre: ​​álgebra lineal, cálculo diferencial e integral, métodos numéricos, algorítmica numérica, estadística y optimización

     

  • EFB3_Capacidad para comprender y dominar los conceptos básicos de matemática discreta, lógica, algorítmica y complejidad computacional, y su aplicación para la resolución de problemas propios de la ingeniería

     

competencias transversales
  • T1_Que los estudiantes conozcan un tercer idioma, que será preferentemente el inglés, con un nivel adecuado de forma oral y por escrito, de acuerdo con las necesidades que tendrán las graduadas y graduados en cada titulación

     

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 puesto 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 vamos a estudiar 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 de la misma forma que existe el imperativo y funcional, en bases de datos, en el diseño y verificación de sistemas y en la inteligencia artificial entre d 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 pueden usarse para validar la corrección de la solución propuesta a problemas computacionales. 

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 la Covidien-19. De esta forma se asegurará la consecución de los mismos conocimientos y competencias que se especifican en este plan docente.

Contenidos


  1. Lógica proposicional
    1. Razonamiento, lenguaje natural y lenguaje proposicional
    2. El lenguaje de la lógica proposicional, CP0
    3. Formalización de sentencias e interpretación de enunciados
    4. Teoría de modelos (tautologías, contradicciones y contingencias)
    5. Teoría de la demostración
    6. Razonamientos válidos e inválidos, consistencia e inconsistencia, contraejemplos
    7. formas normales
    8. El método de resolución
    9. resolución Lineal
  2. Teoría de grafos
    1. Definiciones básicas: caminos, conectividad y distancia, Isomorfismo entre grafos
    2. Representación de grafos
    3. Algoritmos sobre grafos: recorridos en profundidad y anchura (DFS, BFS)
    4. Dígrafos y dags
    5. ordenación topológica
    6. Árboles de expansión mínima: algoritmos de Prim y Kruskal
    7. Caminos más cortos: algoritmo de Dijkstra

Sistema de evaluación


La calificación final es la media de la nota de las dos partes de la asignatura

ACTIVIDAD y PES

  1. Examen de Lógica 45% - 50%
  2. Examen de Grafos 45% - 50%
  3. Resolución de problemas de lógica en clase 0% - 5%
  4. Resolución de problemas de grafos en clase 0% - 5%

Para aprobar la asignatura las notas de las dos partes de la asignatura deben ser iguales o superiores a 5

La resolución de problemas es voluntaria

recuperación

  • Sólo se pueden recuperar los exámenes, no la participación en clase
  • El estudiante sólo puede presentarse a la recuperación si se ha presentado en el examen ordinario. 

 

Bibliografía


Básico

K. Erciyes, "Discrete Mathematics and Graph Theory, a concise study company and guide (Undergrate Topics in Computer Science)". Springer, 2021. ISBN 978-3-030-61114-9

Kenneth H. Rosen, "Discrete Mathematics and its Applications". Eighth Edition. McGraw-Hill-Education, 2019. ISBN 978-1-260-09199-1.

Complementario

Robert Sedgewick y Kevin Wayne, "Algorithms", Fourth Edition, Addison-Wesley, 2011. ISBN 978-0321573513.

Gabriel Valiente, "Algoritmos en Trees and Graphs: With Python Code (Textos en Computer Science)". Second Edition. Springer, 2021. ISBN 

978 - 3030818845

K. Erciyes, "Algebraico Graph Algoritms, en practical gunide usando Python (Undergrate Topics in Computer Science)". Springer, 2021. ISBN 978-3-030-87885-6