Matemática discreta

A matemática discreta axuda a entender a computación xa que se estuda temas como lóxica, demostracións, probas por indución, teoría de conxuntos, algoritmos, teoría de grafos, técnicas de cálculo, etc.

A conexión coa Intelixencia Artificial (IA) é que a IA baséase notablemente na computación dixital e a matemática discreta pode mostrar como a IA pode chegar a inferir certos comportamentos. Tamén, a matemática discreta proporciona unha vía para codificar e describir os problemas da IA (aprendizaxe automática, toma de decisións, procesamento da linguaxe natural, resposta a preguntas, recuperación de información).

Con esta materia preténdese:
- contribuír á formación integral dos futuros graduados en Intelixencia Artificial, posibilitándolles unha sólida e axeitada formación en competencias propias da matemática discreta.
- potenciar o emprego de distintas representacións (simbólica, gráfica, matricial) e de distintos razoamentos (indutivo, recursivo, dedutivo) como medios para favorecer a integración de conceptos e procedementos derivados dos contidos propios da materia.
- coñecer os conceptos básicos da teoría de conxuntos.
- familiarizarse coas matemáticas involucradas no pensamento algorítmico (especificación, verificación e complexidade).
- entender e saber manexar as álxebras de Boole.
- alentar as actitudes de crítica ante diferentes tipos de solucións, de busca, de perseveranza e esforzo ante as dificultades, de comunicación utilizando a terminoloxía adecuada.

Na parte práctica, empregarase o programa de software de código aberto SageMath para iniciarse na programación de diferentes algoritmos relacionados coa materia.

TEMA 1. Introdución á teoría de conxuntos

Conxuntos: elementos e pertenza. Subconxuntos: partes dun conxunto. Representación de conxuntos: diagramas de Venn. Operacións con conxuntos: propiedades. Produto cartesiano de conxuntos. Aplicacións entre conxuntos: composición. Tipos de aplicacións: inxectiva, sobrexectiva e bixectiva.

Docencia Presencial
Horas expositivas / prácticas: 3 / 2

Actividades de aprendizaxe autónoma/ titoría
Horas estudo / resolución de problemas / prácticas ordenador / titoría : 3 / 1 / 1 / 0,5

TEMA 2. Razoamento matemático e indución

Estratexias de demostración. Indución matemática.

Docencia Presencial
Horas expositivas / prácticas: 2 /2

Actividades de aprendizaxe autónoma/ titoría
Horas estudo / resolución de problemas / prácticas ordenador / titoría : 3 / 1 / 1 / 0,25

TEMA 3. Algoritmos e números.

Algoritmos: complexidade. Números primos. Divisibilidade. Algoritmo de Euclides. Congruencias. Sistemas de numeración. Aritmética computacional con enteiros grandes. Criptografía de clave pública. Algoritmo RSA.

Docencia Presencial
Horas expositivas / prácticas: 7 / 6

Actividades de aprendizaxe autónoma/ titoría
Horas estudo / resolución de problemas / prácticas ordenador / titoría : 5 / 2 / 2 / 0,5

TEMA 4. Combinatoria

Técnicas básicas de enumeración: Principios de adición, multiplicación e do pombal. Permutacións e combinacións. Teorema do binomio. Principio de inclusión-exclusión.

Docencia Presencial:
Horas expositivas / prácticas: 6 / 3

Actividades de aprendizaxe autónoma/ titoría
Horas estudo / resolución de problemas / prácticas ordenador / titoría: 4 / 2 / 2 / 0,5

TEMA 5. Recursividade

Definicións recursivas. Algoritmos recursivos. Indución estrutural. Verificación de programas. Técnicas avanzadas de enumeración: relacións de recorrencia. Resolución de relacións de recorrencia. Funcións xeratrices.

Docencia Presencial
Horas expositivas / prácticas: 5 / 3

Actividades de aprendizaxe autónoma/ titoría
Horas estudo / resolución de problemas / prácticas ordenador / titoría: 4 / 2 / 2 / 0,5

TEMA 6. Grafos

Tipos de grafos. Representación de grafos. Conexión. Camiños eulerianos e hamiltonianos. Grafos planos. Colorado de grafos. Árbores. Algoritmos en grafos.


Docencia Presencial
Horas expositivas / prácticas: 5 / 2

Actividades de aprendizaxe autónoma/ titoría
Horas estudo / resolución de problemas / prácticas ordenador / titoría: 3 / 1 / 1 / 0,5


TEMA 7. Álxebras de Boole
Funcións booleanas e funcións de conmutación. Formas normais disxuntiva e conxuntiva. Portas lóxicas. Minimización de circuítos.


Docencia Presencial
Horas expositivas / prácticas: 2 / 2

Actividades de aprendizaxe autónoma/ titoría
Horas estudo / resolución de problemas / prácticas ordenador / titoría: 3 / 1 / 1 / 0,25

BÁSICA:
Aguado, F., Gago, F. et al., Problemas resueltos de Combinatoria. Laboratorio con SageMath, Paraninfo, 2018.
Rosen, K. H., Matemática Discreta y sus Aplicaciones, McGraw-Hill (5ª ed.) 2004.
Vieites, A.M., Aguado, F. et al., Teoría de Grafos: Ejercicios resueltos y propuestos. Laboratorio con Sage, Paraninfo, 2014.


COMPLEMENTARIA:
Bard, G. V., SageMath for Undergraduates. http://www.gregorybard.com/SAGE.html
García Merayo, F., Matemática discreta, Paraninfo, Thomson Learning, 2001.
García Merayo, F., Hernández, G., Nevot, A., Problemas resueltos de Matemática discreta, 2ª edición ampliada, Paraninfo, 2018.
Grimaldi, R. P., Matemáticas Discreta y Combinatoria, Addison-Wesley Iberoamericana, 1997.
Johnsonbaugh, R., Matemáticas Discretas, Pearson Prentice Hall (6ª ed.) 2005.
Lipschutz, S., Lipson, M., 2000 Solved Problems in Discrete Mathematics, Schaum, Mc-Graw-Hill, 1992.

http://doc.sagemath.org/

Contribuír a alcanzar as competencias básicas, xerais, transversais e específicas recollidas na Memoria do Titulo de Grao en Intelixencia Artificial pola Universidade da Coruña, a Universidade de Santiago de Compostela e a Universidade de Vigo e, en especial, as seguintes ( CG2, CG4, CB2, CB3, CB5, TR3, CE1 e CE3):

TRANSVERSAIS
Dentro do recolleito en TR3:
- Capacidade para crear novos modelos e solucións de forma autónoma e creativa, adaptándose a novas situacións. Iniciativa e espírito emprendedor.

ESPECÍFICAS
Dentro do recolleito en CE1 e CE3:
- Capacidade para utilizar os conceptos e métodos matemáticos que poidan exporse na modelización, formulación e resolución de problemas de intelixencia artificial.
- Capacidade para resolver problemas de intelixencia artificial que precisen algoritmos, desde o seu deseño e posta en funcionamento ata a súa avaliación.

Ademais das competencias anteriores os estudantes deberían alcanzar as seguintes destrezas:

–Cognitivas (saber):
Adquisición dos conceptos básicos da materia: algoritmos, números enteiros, técnicas de reconto, teoría de grafos e álxebras de Boole.
Coñecer aplicacións da matemática discreta á Intelixencia Artificial.

–Procedementais / instrumentais (saber facer):
Manexar a aritmética modular e aplicar os resultados nos diferentes sistemas de numeración, cálculos con enteiros moi grandes e na criptografía de clave pública.
Saber aplicar as técnicas básicas para contar en diversos problemas.
Coñecer algúns algoritmos recursivos e aplicalos en situacións concretas.
Aplicar a teoría de grafos en áreas relativas á Intelixencia Artificial.
Manexar o programa informático SageMath e aplicar os algoritmos aprendidos para resolver os problemas expostos no curso.

–Actitudinais (ser):
Expresión rigorosa e clara, oral e escrita. Razoamento lóxico e identificación de erros nos procedementos. Capacidade de adaptación. Capacidade de abstracción. Capacidade de organización e planificación. Traballar en equipo. Actitude de crítica ante distintos tipos de solucións. Desenvolver a capacidade de análise na resolución de problemas.

Utilizaranse as horas de clase expositiva para a presentación dos contidos básicos que compoñen esta materia. Nas clases prácticas en grupos reducidos realizaranse exercicios e prácticas en ordenador. Así mesmo, propoñeranse temas de estudo e problemas para ser resoltos polo alumnado debendo presentar os seus resultados nas titorías e grupos moi reducidos, nos que tamén se ofrecerá soporte para os mesmos.

Abriremos unha aula no Campus Virtual na que, ademais de contar con diversos materiais de apoio, levaremos conta do tratado en cada clase, así como da programación de actividades, algunhas das cales realizaranse en grupos, e outro curso en CoCalc que servirá de apoio e control para as clases interactivas de laboratorio.

Hai unha única convocatoria con dúas oportunidades.

Seguirase un método de avaliación continua, a través de actividades académicas dirixidas, tendo en conta os traballos realizados tanto individualmente como en grupos, e especialmente o realizado co ordenador, no que o alumnado deberá demostrar o seu coñecemento da materia; e un exame final.

Avaliación de competencias:
No traballo grupal avaliaranse as competencias CB3, CE1 e CE3.
Na resolución individual de problemas e prácticas de ordenador avaliaranse as competencias CG2, CB5 e TR3.
Nos cuestionarios en clase ou no curso virtual avaliaranse as competencias CG2, CB5, CE1, CE3 e TR3.
No exame final se avaliarán as competencias CG2, CG4, CB2 e CB5.

As porcentaxes asignadas a cada unha das partes en cada oportunidade son os seguintes:

Primeira oportunidade (xaneiro / febreiro)

• Exame final teórico-práctico: 35%.
• Exame final de prácticas no ordenador: 25%.
• Avaliación continua: 40%. Realizaranse dúas probas durante o cuadrimestre (unha escrita e outra de Sage), ademais de diferentes entregas de exercicios. Tamén se terá en conta a participación nas clases. Os estudantes repetidores deberán realizar tódalas actividades convocadas a través do campus virtual.

Para aprobar a materia será imprescindible realizar os traballos prácticos, presentarse aos exames e obter un total de 5 puntos de media, cun mínimo do 40% tanto no exame final teórico-práctico como no exame final de prácticas no ordenador.

Segunda oportunidade (xuño / xullo)

A avaliación do alumnado basearase nun exame final coas seguintes porcentaxes:

• Exame final teórico-práctico: 35%
• Exame final de prácticas no ordenador: 25%
• Avaliación continua: 40%

Consideraranse presentados aqueles que realicen algún dos exames finais ou participen en polo menos o 75% das actividades da avaliación continua.


Para o caso de realización fraudulenta de exercicios ou probas será de aplicación o recolleito na Normativa de avaliación do rendemento académico dos estudantes e revisión de cualificacións, en particular o recolleito no artigo 16:
A realización fraudulenta dalgún exercicio ou proba esixida na avaliación da materia implicará a cualificación de suspenso na convocatoria correspondente, con independencia do proceso disciplinario que se poida seguir contra a persoa infractora.

Presencial:
30 horas de clases maxistrais (teóricas, exercicios ou problemas)
20 horas de sesións prácticas e de laboratorio en grupos reducidos
3 horas titoría en grupos moi reducidos
2 horas probas parciais
3 horas exame final escrito
2 horas exame final no ordenador

Total (Presencial): 60 horas

Non presencial:
45 horas de estudo autónomo relacionadas coas clases (25 horas para a teoría, 10 para problemas, 10 prácticas de ordenador)
30 horas para traballar nos boletíns de problemas propostos
18 horas para programar en ordenador solucións a problemas propostos
6 horas actividades de avaliación no campus virtual

Total (Non presencial): 99 horas

Carga de traballo total: 159 horas

Asistencia continuada ás clases e laboratorios. Traballar individual ou colectivamente as cuestións indicadas nas clases. Aproveitar vos laboratorios e as titorías tan pronto como xurdan dificultades.

Debe dedicar esforzos para ser capaz de aplicar os razoamentos na resolución de problemas e programar os diferentes algoritmos no paquete de cálculo simbólico establecido.