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 (jvazquez@cs.upc.edu)
  • Ramon Sangüesa Sole (ramon.sanguesa.i@upc.edu)

Otros

  • Santiago Marco Sola (santiago.marco@upc.edu)
  • Sergio Álvarez Napagao (salvarez@cs.upc.edu)

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: CB2, CT4, CE03, CE13, CE14, CG2, CG4,
    2. Conocer los algoritmos bioinspirados y evolutivos
      Competencias relacionadas: CB2, CE03, CE13, CE14, CG4, CG2,
    3. Conocer los métodos de planificación automática
      Competencias relacionadas: CT4, CE03, CE13, CE14, CG2, CG4, CB2,
    4. Ser capaz de analizar problemas y escoger la mejor estrategia algorítmica
      Competencias relacionadas: CB2, CE03, CE13, CE14, CG2, CG4, CG8,

    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
    0h
    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
    0h

    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ásico

    Complementario

    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.