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

Esteu aquí

Inici » Estudis » Graus » Grau en Intel·ligència Artificial » Pla d'estudis » Assignatures » 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 ( )
  • Ramon Sangüesa Sole ( )

Altres

  • Sergio Álvarez Napagao ( )

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: CB2, CT4, CE03, CE13, CE14, CG2, CG4,
  2. Conèixer els algoritmes bioinspirats i evolutius
    Competències relacionades: CB2, CE03, CE13, CE14, CG2, CG4,
  3. Conèixer els mètodes de planificació automàtica
    Competències relacionades: CT4, CE03, CE13, CE14, CG2, CG4, CB2,
  4. Ser capaç d'analitzar problemes i escollir la millor estratègia algorítmica
    Competències relacionades: CB2, CE03, CE13, CE14, CG2, CG4, CG8,

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)
Tipus: entrega
Teoria
0h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
0h

Examen parcial


Objectius: 1 2 4
Setmana: 8
Tipus: examen de teoria
Teoria
2h
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)
Tipus: entrega
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)
Tipus: examen de teoria
Teoria
0h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
4h

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


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àsica:

Complementaria:

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.