Algorismes Bàsics per la Intel·ligència Artificial

Crèdits
6
Tipus
Obligatòria
Requisits
Aquesta assignatura no té requisits , però té capacitats prèvies
Departament
CS
Web
https://sites.google.com/upc.edu/abia
L'assignatura dona a conèixer i permet dominar les diverses famílies d'algorismes de resolució de problemes utilitzats en Intel·ligència Artificial. Es fa especial èmfasi en la cerca en un espai de possibles configuracions (espai d'estats, espai de solucions, espai de variables, espai de plans). També e'estudien els algorismes de resolució de problemes basats en mètodes evolutius i bioinspirats.
L'objectiu és que els estudiants siguin capaços d'analitzar un problema i aprofitar i/o adaptar l'esquema algorítmic més adient per la seva resolució.

Professorat

Responsable

  • Javier Vazquez Salceda (jvazquez@cs.upc.edu)
  • Ramon Sangüesa Sole (ramon.sanguesa.i@upc.edu)

Altres

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

Hores setmanals

Teoria
2
Problemes
0
Laboratori
2
Aprenentatge dirigit
0
Aprenentatge autònom
6

Competències

Competències Transversals

Transversals

  • CT4 [Avaluable] - Treball en equip. Ser capaç de treballar com a membre d'un equip interdisciplinari, ja sigui com un membre més o realitzant tasques de direcció, amb la finalitat de contribuir a desenvolupar projectes amb pragmatisme i sentit de la responsabilitat, assumint compromisos tenint en compte els recursos disponibles.

    • Bàsiques

  • CB2 - Que els estudiants sàpiguen aplicar els seus coneixements al seu treball o vocació d'una manera professional i posseeixin les competències que solen demostrar-se mitjançant l'elaboració i defensa d'arguments i la resolució de problemes dins la seva àrea d'estudi.

    • Competències Tècniques

    Específiques

  • CE03 - Identificar i aplicar els procediments algorítmics bàsics de les tecnologies informàtiques per dissenyar solucions a problemes, analitzant la idoneïtat i complexitat dels algoritmes proposats.
  • CE13 - Avaluar la complexitat computacional d'un problema, identificar estratègies algorítmiques que puguin conduir a la seva resolució i recomanar, desenvolupar i implementar aquella que garanteixi el millor rendiment d'acord amb els requisits establerts.
  • CE14 - Dominar els fonaments, paradigmes i tècniques pròpies dels sistemes intel·ligents i analitzar, dissenyar i construir sistemes, serveis i aplicacions informàtiques que utilitzin aquestes tècniques en qualsevol àmbit d'aplicació, inclòs la robòtica.

    • Competències Tècniques Generals

    Genèriques

  • CG2 - Utilitzar els coneixements fonamentals i metodologies de treball sòlides adquirits durant els estudis per adaptar-se als nous escenaris tecnològics de el futur.
  • CG4 - Raonar, analitzant la realitat i dissenyant algoritmes i formulacions que la modelin. Identificar problemes i construir solucions algorísmiques o matemàtiques vàlides, eventualment noves, integrant el coneixement multidisciplinari necessari, valorant diferents alternatives amb esperit crític, justificant les decisions preses, interpretant i sintetitzant els resultats en el context de l'domini d'aplicació i establint generalitzacions metodològiques a partir de aplicacions concretes.
  • CG8 - Observar un exercici ètic de la professió en totes les seves facetes, aplicant criteris ètics en el disseny de sistemes, algoritmes, experiments, utilització de dades, d'acord amb els sistemes ètics recomanats pels organismes nacionals i internacionals, amb especial èmfasi en seguretat, robustesa , privacitat, transparència, traçabilitat, prevenció de biaixos (de raça, gènere, religió, territori, etc.) i respecte als drets humans.

    • Objectius

    1. Conèixer els principals algoritmes de cerca i exploració d'espais de configuracions
      Competències relacionades: CG2, CG4, CT4, CB2, CE03, CE13, CE14,
    2. Conèixer els algoritmes bioinspirats i evolutius
      Competències relacionades: CG2, CG4, CB2, CE03, CE13, CE14,
    3. Conèixer els mètodes de planificació automàtica
      Competències relacionades: CG2, CG4, CT4, CB2, CE03, CE13, CE14,
    4. Ser capaç d'analitzar problemes i escollir la millor estratègia algorítmica
      Competències relacionades: CG2, CG4, CG8, CB2, CE03, CE13, CE14,

    Continguts

    1. Introducció a la resolució de problemes mitjançant cerca
      Introducció a les metodologies de resolució automática de problemes. Representació com a espai d'estats. Algoritmes bàsics no informats de cerca en l'espai d'estats. Limitacions.
    2. Cerca Heurística
      Conèixer i comprendre els mètodes de cerca guiada per funcions heurístiques. Propietats que han de complir les funcions heurístiques.
    3. Cerca Local
      Aprendre esl algoritmes de cerca local i la seva motivació. Es presenten com mètodes heurístics per resoldre problemes d'optimització computacionalment difícils, explorant estratègies de maximització o minimització d'algun criteri que caracteritza les possibles solucions.
    4. Cerca amb Adversari. Jocs
      Es presenten els jocs com una extensió de les estratègies de minimització i maximització. S'exploren també des de la perspectiva més general de teoria de jocs, incidint en una taxonomia àmplia que inclou jocs competitius, cooperativus, de suma zero, infinits, repetits, etc. amb una exploració de conceptes i condicions d'equilibri.
    5. Introducció a la satisfacció de restriccions
      Es presenten els mètodes de solució de problemes per satisfacció de restriccions com una forma d'explorar l'espai a partir de eles restriccions imposades al conjunt de variables que permeten caracteritzar el problema i les seves possibles solucions.
      Es treballen mètodes de backpropagation i propagació de restriccions i es connecten també amb formes lògiques d'expressió i satisfacció de restriccions.
    6. Planificació Automàtica
      Es presenten les estratègies per explorar la seqüenciació d'accions en el temps per tal d'assolir de forma eficient els objectius dels agents intel·ligents. L'estratègia es connecta amb l'optimització en un espai multidimensional. Es presenten els principals algoritmes de planificació connectant-los amb les estratègies d'exploració, cerca i optimització: planificació clàssica, temporal, probabilística, i jeràrquica per exemple, i es connecten amb la exploració en un espai de plans. S'inclou també la reutilització de plans. Es presenta un llenguatge de planificació per poder entomar exercicis i projectes de planificació.

    Activitats

    Activitat Acte avaluatiu


    Resolució de problemes amb Cerca Heurística

    L'alumne no només haurà d'atendre a les exposicions del professor, sino també fer exercicis pràctics sobre l'ús dels algorismes de Cerca, i participar a les discussions amb el professor i els seus companys sobre quan és millor utilitzar cadascun dels algorismes. Al laboratori l'alumne haurà d'aplicar el que ha aprés a un problema de dificultat mitjana.
    • Teoria: Presentació teòrica de cerca i dels algorismes principals.
    • Problemes: Exercicis de cerca i programació i resolució de problemes amb cerca heurística.
    • Laboratori: Desenvolupament de programes acotats per explorar les diverses estratègies de cerca.
    • Aprenentatge autònom: Estudi i pràctica de les estratègies de cerca.
    Objectius: 1 4
    Continguts:
    Teoria
    6h
    Problemes
    0h
    Laboratori
    6h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    12h

    Resolució de problemes amb Cerca Local

    L'alumne no només haurà d'atendre a les exposicions del professor, sino també fer exercicis pràctics sobre l'ús dels algorismes de Cerca, i participar a les discussions amb el professor i els seus companys sobre quan és millor utilitzar cadascun dels algorismes. Al laboratori l'alumne haurà d'aplicar el que ha aprés a un problema de dificultat mitjana.
    Objectius: 1 2 4
    Continguts:
    Teoria
    7h
    Problemes
    0h
    Laboratori
    5h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    12h

    Pràctica 1: Resolució de problemes amb Cerca en un espai de configuracions

    Realització de la pràctica sobre algorismes de Cerca. Els alumnes realitzaràn la major part de la pràctica de forma autònoma en hores no presencials. Es dediquen unes hores presencials amb el professor per guiar la ressolució i per ressoldre dubtes. En acabar la pràctica s'ha d'entregar un informe.
    Objectius: 1 4
    Continguts:
    Teoria
    0h
    Problemes
    0h
    Laboratori
    2h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    16.5h

    Resolució de problemes de Cerca amb Adversari. Jocs

    L'alumne no només haurà d'atendre a les exposicions del professor, sino també fer exercicis pràctics sobre l'ús dels algorismes de Cerca, i participar a les discussions amb el professor i els seus companys sobre quan és millor utilitzar cadascun dels algorismes. Al laboratori l'alumne haurà d'aplicar el que ha aprés a un problema de dificultat mitjana.
    Objectius: 1 4
    Continguts:
    Teoria
    3h
    Problemes
    0h
    Laboratori
    3h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    6h

    Entrega Pràctica 1: Resolució de problemes amb Cerca en un espai de configuracions

    Entrega de l'informe sobre la pràctica d'algorismes de Cerca que els alumnes han realitzat.
    Objectius: 1 4
    Setmana: 7 (Fora d'horari lectiu)
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Examen parcial


    Objectius: 1 2 4
    Setmana: 8
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Satisfacció i Optimització de Restriccions

    L'alumne no només haurà d'atendre a les exposicions del professor, sino també fer exercicis pràctics sobre l'ús dels algorismes de Cerca, i participar a les discussions amb el professor i els seus companys sobre quan és millor utilitzar cadascun dels algorismes. Al laboratori l'alumne haurà d'aplicar el que ha aprés a un problema de dificultat mitjana.
    Objectius: 1 4
    Continguts:
    Teoria
    4h
    Problemes
    0h
    Laboratori
    4h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    10h

    Planificació Automàtica

    L'alumne no només haurà d'atendre a les exposicions del professor, sino també fer exercicis pràctics sobre l'ús dels algorismes de Cerca, i participar a les discussions amb el professor i els seus companys sobre quan és millor utilitzar cadascun dels algorismes. Al laboratori l'alumne haurà d'aplicar el que ha aprés a un problema de dificultat mitjana.
    Objectius: 3 4
    Continguts:
    Teoria
    8h
    Problemes
    0h
    Laboratori
    7h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    15h

    Pràctica 2: Resolució de problemes amb Planificació Automàtica

    Realització de la pràctica sobre Planificació Automàtica. Els alumnes realitzaràn la major part de la pràctica de forma autònoma en hores no presencials. Es dediquen unes hores presencials amb el professor per guiar la ressolució i per ressoldre dubtes. En acabar la pràctica s'ha d'entregar un informe.
    Objectius: 3 4
    Continguts:
    Teoria
    0h
    Problemes
    0h
    Laboratori
    3h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    14.5h

    Entrega Pràctica 2: Resolució de problemes amb Planificació Automàtica

    Entrega de l'informe sobre la pràctica de Planificación Automática que els alumnes han realitzat.
    Objectius: 3 4
    Setmana: 14 (Fora d'horari lectiu)
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Examen Final

    Examen final dels continguts del curs.
    Objectius: 1 2 3 4
    Setmana: 15 (Fora d'horari lectiu)
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Metodologia docent

    Les clases estan dividides en sessions de teoria, problemes i laboratori.

    A les sessions de teoria es desenvoluparan els coneixements de l'assignatura, intercalant l'exposició de nou material teòric amb exemples i la interacció amb els alumnes per tal de discutir els conceptes.

    Les classes de problemes permetran aprofondir en les técniques i algorismes explicats a les sessions de teoria. S'estimularà la participació de l'alumne per tal de comentar les alternatives possibles.

    A les clases de laboratori es desenvoluparan petites pràctiques utilitzant eines i llenguatges propis de la Intel·ligència Artificial que permetran practicar i reforçar els coneixements de les classes de teoria.

    Mètode d'avaluació

    L'avaluació constarà d'un examen parcial, un exàmen final i una nota de laboratori.

    L'examen parcial no és alliberatori i es farà a hores de clase. Les persones que no aprovin o no facin l'examen parcial seran avaluades només amb la nota de l'examen final.

    La nota de laboratori provindrà dels informes que es faran de les pràctiques realitzades.

    El càlcul de la nota final es farà de la següent manera:

    NP = nota del parcial
    NF = nota de l'examen final
    NL = nota de laboratori
    NOTA = max ((NP*0.2 + NF*0.3), NF*0.5) + NL*0.5



    Reavaluació: només es poden presentar a la reavaluació aquelles persones que, havent-se presentat a l'examen final l'hagin suspès. La nota màxima que es pot obtenir a la reavaluació és un 7.


    Avaluació de les competències

    La avaluació de la competència sobre treball en equip (CT4) es basa en el treball realitzat durant les pràctiques de laboratori. La nota A B C D es calcula a partir d'una rúbrica detallada que es donarà als alumnes a l'inici de curs.

    La avaluació de la competència sobre aplicació de coneixements (CB2) es calcula directament a partir de la nota del curs, ja que en tots els actes avaluatoris s'està avaluant de fomra efectiva aquesta competència.

    Bibliografia

    Bàsic

    Complementari

    Capacitats prèvies

    Capacitats prèvies sobre Lògica adquirides a l'assignatura Fonaments Matemàtics (FM) i Coneixement i Raonament Automàtic(CRA):
    - Coneixement dels conceptes bàsics de lògica de proposicions i predicats
    - Capacitat de formular un problema en termes lògics.
    - Coneixements sobre Inferència lògica i resolució. Entendre les estratègies de resolució.

    Capacitats prèvies sobre Algorísmica adquirides a les l'assignatures de Programació i Algorísmia PA1 i PA2.
    - Coneixement de les estructures d'arbres i grafs,
    - Coneixement dels algorismes de recorregut i cerca sobre arbres i grafs.
    - Nocions bàsiques de complexitat algorísmica.