Algoritmos Básicos para la Inteligencia Artificial

Usted está aquí

Inicio » Estudios » Grados » Grado en Inteligencia Artificial » Plan de estudios » Asignaturas » Algoritmos Básicos para la Inteligencia Artificial
Créditos
6
Tipos
Obligatoria
Requisitos
Esta asignatura no tiene requisitos, pero tiene capacidades previas
Departamento
CS
Web
https://sites.google.com/upc.edu/abia
This course introduces and allows to master the various families of problem-solving algorithms used in Artificial Intelligence. Special emphasis is put on searching in a space of possible configurations (state space, solution space, variable space, plan space). Problem-solving algorithms based on evolutionary and bio-inspired methods are also studied.
The goal is for students to be able to analyze a problem and take advantage of and / or adapt the most appropriate algorithm for solving it.

Profesorado

Responsable

  • Javier Vazquez Salceda ( )
  • Ramon Sangüesa Sole ( )

Otros

  • Santiago Marco Sola ( )
  • Sergio Álvarez Napagao ( )

Horas semanales

Teoría
2
Problemas
0
Laboratorio
2
Aprendizaje dirigido
0
Aprendizaje autónomo
6

Competencias

Competencias Transversales

Transversales

  • CT4 [Avaluable] - Trabajo en equipo. Ser capaz de trabajar como miembro de un equipo interdisciplinar, ya sea como un miembro más o realizando tareas de dirección, con la finalidad de contribuir a desarrollar proyectos con pragmatismo y sentido de la responsabilidad, asumiendo compromisos teniendo en cuenta los recursos disponibles.

Básicas

  • CB2 - Que los estudiantes sepan aplicar sus conocimientos a su trabajo o vocación de una forma profesional y posean las competencias que suelen demostrarse por medio de la elaboración y defensa de argumentos y la resolución de problemas dentro de su área de estudio.

Competencias Técnicas

Específicas

  • CE03 - Identificar i aplicar els procediments algorítmics bàsics de les tecnologies informàtiques per a dissenyar solucions a problemes, analitzant la idoneïtat i complexitat dels algorismes proposats.
  • CE13 - Evaluar la complejidad computacional de un problema, identificar estrategias algorítmicas que puedan conducir a su resolución y recomendar, desarrollar e implementar aquella que garantice el mejor rendimiento de acuerdo con los requisitos establecidos.
  • CE14 - Dominar los fundamentos, paradigmas y técnicas propias de los sistemas inteligentes y analizar, diseñar y construir sistemas, servicios y aplicaciones informáticas que utilicen dichas técnicas en cualquier ámbito de aplicación, incluido la robótica.

Competencias Técnicas Genéricas

Genéricas

  • CG2 - Utilizar los conocimientos fundamentales y metodologías de trabajo sólidas adquiridos durante los estudios para adaptarse a los nuevos escenarios tecnológicos del futuro.
  • CG4 - Razonar, analizando la realidad y diseñando algoritmos y formulaciones que la modelen. Identificar problemas y construir soluciones algorítmicas o matemáticas válidas, eventualmente nuevas, integrando el conocimiento multidisciplinar necesario, valorando distintas alternativas con espíritu crítico, justificando las decisiones tomadas, interpretando y sintetizando los resultados en el contexto del dominio de aplicación y estableciendo generalizaciones metodológicas a partir de aplicaciones concretas.
  • CG8 - Observar un ejercicio ético de la profesión en todas sus facetas, aplicando criterios éticos en el diseño de sistemas,algoritmos, experimentos, utilización de datos, de acuerdo con los sistemas éticos recomendados por los organismos nacionales e internacionales, con especial énfasis en seguridad, robustez, privacidad, transparencia, trazabilidad, prevención de sesgos (de raza, género, religión, territorio, etc.) y respeto a los derechos humanos.

Objetivos

  1. Conocer los principales algoritmos de búsqueda y exploración de espacios de configuración
    Competencias relacionadas: CG2, CG4, CT4, CB2, CE03, CE13, CE14,
  2. Conocer los algoritmos bioinspirados y evolutivos
    Competencias relacionadas: CG2, CG4, CB2, CE03, CE13, CE14,
  3. Conocer los métodos de planificación automática
    Competencias relacionadas: CG2, CG4, CT4, CB2, CE03, CE13, CE14,
  4. Ser capaz de analizar problemas y escoger la mejor estrategia algorítmica
    Competencias relacionadas: CG2, CG4, CG8, CB2, CE03, CE13, CE14,

Contenidos

  1. Introducción a la resolución de problemas mediante búsqueda
    Introducción a las metodologías de resolución automática de problemas. Representación como espacio de estados. Algoritmos básicos no informados de búsqueda en el espacio de estados. Limitaciones.
  2. Búsqueda Heurística
    Conocer y comprender los métodos de búsqueda guiada por funciones heurísticas. Propiedades que deben cumplir las funciones heurísticas.
  3. Búsqueda Local
    Se presentan y estudian algoritmos de búsqueda local y su motivación. Se presentan como métodos heurísticos para resolver problemas de optimización computacionalmente difíciles, utilizando estrategias para maximizar o minimizar algunos criterios que caracterizan las posibles soluciones.
  4. Búsqueda con Adversario. Juegos
    Los juegos se presentan como una extensión de las estrategias de minimización y maximización. También se exploran desde la perspectiva más general de la teoría de juegos, centrándose en una amplia taxonomía que incluye juegos competitivos, cooperativos, de suma cero, infinitos, repetidos, etc., con una exploración de conceptos y condiciones de equilibrio.
  5. Introducción a la satisfacción de las restricciones
    Problem-solving methods for constraint satisfaction are presented as a way of exploring space using the constraints imposed on the set of variables that characterize the problem and its possible solutions.
    Methods of backpropagation and propagation of constraints are presented, studied and compare and they are also connected with logical forms of expressing the satisfaction of constraints.
  6. Planificación Automática
    Se presentan estrategias para explorar la secuencia de acciones a lo largo del tiempo con el fin de lograr de manera eficiente los objetivos de los agentes inteligentes. Están relacionados con la optimización en un espacio multidimensional. Se presentan los principales algoritmos de planificación relacionándolos con estrategias de exploración, búsqueda y optimización: planificación clásica, temporal, probabilística y jerárquica por ejemplo, y se representan como una exploración en un espacio de planes. También se estudia la reutilización de planos. Se presenta un lenguaje de planificación para poder empezar a planificar ejercicios y proyectos.

Actividades

Actividad Acto evaluativo


Resolución del problemas con Búsqueda Heurística

El alumno no sólo deberá atender a las exposiciones del profesor, sino también hacer ejercicios prácticos sobre el uso de los algoritmos de Búsqueda, y participar en las discusiones con el profesor y sus compañeros sobre cuándo es mejor utilizar cada uno de los algoritmos. En el laboratorio el alumno deberá aplicar lo aprendido a un problema de dificultad media.
  • Teoría: Presentación teórica de búsqueda y de los principales algoritmos.
  • Problemas: Ejercicios de búsqueda y programación y resolución de problemas con búsqueda heurística.
  • Laboratorio: Desarrollo de programas acotados para explorar las diversas estrategias de búsqueda.
  • Aprendizaje autónomo: Estudio y práctica de estrategias de búsqueda.
Objetivos: 1 4
Contenidos:
Teoría
6h
Problemas
0h
Laboratorio
6h
Aprendizaje dirigido
0h
Aprendizaje autónomo
12h

Resolución del problemas con Búsqueda Local

El alumno no sólo deberá atender a las exposiciones del profesor, sino también hacer ejercicios prácticos sobre el uso de los algoritmos de Búsqueda, y participar en las discusiones con el profesor y sus compañeros sobre cuándo es mejor utilizar cada uno de los algoritmos. En el laboratorio el alumno deberá aplicar lo aprendido a un problema de dificultad media.
Objetivos: 1 2 4
Contenidos:
Teoría
7h
Problemas
0h
Laboratorio
5h
Aprendizaje dirigido
0h
Aprendizaje autónomo
12h

Práctica 1: Resolución de problemas con Búsqueda en un espacio de configuraciones

Realización de la práctica sobre algoritmos de Búsqueda. Los alumnos realizarán la mayor parte de la práctica de forma autónoma en horas no presenciales. Se dedican unas horas presenciales con el profesor para guiar la resolución y resolver dudas. Al finalizar la práctica debe entregarse un informe.
Objetivos: 1 4
Contenidos:
Teoría
0h
Problemas
0h
Laboratorio
2h
Aprendizaje dirigido
0h
Aprendizaje autónomo
16.5h

Resolución de problemas de Búsqueda con Adversario. Juegos

El alumno no sólo deberá atender a las exposiciones del profesor, sino también hacer ejercicios prácticos sobre el uso de los algoritmos de Búsqueda, y participar en las discusiones con el profesor y sus compañeros sobre cuándo es mejor utilizar cada uno de los algoritmos. En el laboratorio el alumno deberá aplicar lo aprendido a un problema de dificultad media.
Objetivos: 1 4
Contenidos:
Teoría
3h
Problemas
0h
Laboratorio
3h
Aprendizaje dirigido
0h
Aprendizaje autónomo
6h

Entrega Práctica 1: Resolución de problemas con Búsqueda en un espacio de configuraciones

Entrega del informe sobre la práctica de algoritmos de búsqueda que los alumnos han realizado.
Objetivos: 1 4
Semana: 7 (Fuera de horario lectivo)
Teoría
0h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
0h

Examen Parcial


Objetivos: 1 2 4
Semana: 8
Teoría
2h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
0h

Satisfacción y Optimización de Restricciones

El alumno no sólo deberá atender a las exposiciones del profesor, sino también hacer ejercicios prácticos sobre el uso de los algoritmos de Búsqueda, y participar en las discusiones con el profesor y sus compañeros sobre cuándo es mejor utilizar cada uno de los algoritmos. En el laboratorio el alumno deberá aplicar lo aprendido a un problema de dificultad media.
Objetivos: 1 4
Contenidos:
Teoría
4h
Problemas
0h
Laboratorio
4h
Aprendizaje dirigido
0h
Aprendizaje autónomo
10h

Planificación Automática

El alumno no sólo deberá atender a las exposiciones del profesor, sino también hacer ejercicios prácticos sobre el uso de los algoritmos de Búsqueda, y participar en las discusiones con el profesor y sus compañeros sobre cuándo es mejor utilizar cada uno de los algoritmos. En el laboratorio el alumno deberá aplicar lo aprendido a un problema de dificultad media.
Objetivos: 3 4
Contenidos:
Teoría
8h
Problemas
0h
Laboratorio
7h
Aprendizaje dirigido
0h
Aprendizaje autónomo
15h

Práctica 2: Resolución de problemas con Planificación Automática

Realización de la práctica sobre Planificació Automática. Los alumnos realizarán la mayor parte de la práctica de forma autónoma en horas no presenciales. Se dedican unas horas presenciales con el profesor para guiar la resolución y resolver dudas. Al finalizar la práctica debe entregarse un informe.
Objetivos: 3 4
Contenidos:
Teoría
0h
Problemas
0h
Laboratorio
3h
Aprendizaje dirigido
0h
Aprendizaje autónomo
14.5h

Entrega Práctica 2: Resolución de problemas con Planificación Automática

Entrega del informe sobre la práctica de Planificación Automática que los alumnos han realizado.
Objetivos: 3 4
Semana: 14 (Fuera de horario lectivo)
Teoría
0h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
0h

Examen Final

Examen final de los contenidos del curso.
Objetivos: 1 2 3 4
Semana: 15 (Fuera de horario lectivo)
Teoría
0h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
4h

Metodología docente

Las clases están divididas en sesiones de teoría, problemas y laboratorio.

En las sesiones de teoría se desarrollarán los conocimientos de la asignatura, intercalando la exposición de nuevo material teórico con ejemplos y la interacción con los alumnos para discutir los conceptos.

Las clases de problemas permitirán profundizar en las técnicas y algoritmos explicados en las sesiones de teoría. Se estimulará la participación del alumno para comentar las alternativas posibles.

En las clases de laboratorio se desarrollarán pequeñas prácticas utilizando herramientas y lenguajes propios de la Inteligencia Artificial que permitirán practicar y reforzar los conocimientos de las clases de teoría.

Método de evaluación

La evaluación constará de un examen parcial, un examen final y una nota de laboratorio.

El examen parcial no es liberador de materia y se hará en horas de clase. Las personas que no aprueben o no hagan el examen parcial serán evaluadas sólo con la nota del examen final.

La nota de laboratorio provendrá de los informes que se harán de las prácticas realizadas.

El cálculo de la nota final se hará de la siguiente manera:

NP = nota del parcial
NF = nota del examen final
NL = nota de laboratorio

NOTA = max ((NP*0.2 + NF*0.3), NF*0.5) + NL*0.5

Reevaluación: sólo se pueden presentar a la reevaluación aquellas personas que, habiéndose presentado al examen final lo hayan suspendido. La nota máxima que se puede obtener en la reevaluación es un 7.

Evaluación de las competencias

La evaluación de la competencia sobre trabajo en equipo (CT4) se basa en el trabajo realizado durante las prácticas de laboratorio. La nota ABCD se calcula a partir de una rúbrica detallada que se dará a los alumnos al inicio del curso.

La evaluación de la competencia sobre aplicación de conocimientos (CB2) se calcula directamente a partir de la nota del curso, ya que en todos los actos evaluatorios se está evaluando de forma efectiva esta competencia.

Bibliografía

Básica:

Complementaria:

Capacidades previas

Capacidades previas sobre Lógica adquiridas en la asignatura Fundamentos Matemáticos (FM) y Conocimiento y Razonamiento Autmático (CRA):
- Conocimiento de los conceptos básicos de lógica de proposiciones y predicados
- Capacidad de formular un problema en términos lógicos.
- Conocimientos sobre Inferencia lógica y resolución. Entender las estrategias de resolución.

Capacidades previas sobre Algorítmica adquiridas en les asignaturas de Programación y Algorítimia PA1 y PA2.
- Conocimiento de las estructuras de árboles y grafos,
- Conocimiento de los algoritmos de recorrido y búsqueda sobre árboles y grafos.
- Nociones básicas de complejidad algorítmica.