Grafs i complexitat Codi:  05.569    :  6
Consulta de les dades generals   Descripció   L'assignatura en el conjunt del pla d'estudis   Camps professionals en què es projecta   Coneixements previs   Informació prèvia a la matrícula   Objectius i competències   Continguts   Consulta dels recursos d'aprenentatge de què disposa l'assignatura   Recursos d'aprenentatge i eines de suport   Informacions sobre l'avaluació a la UOC   Consulta del model d'avaluació  
ATENCIÓ: Aquest és el pla docent de l'assignatura per al primer semestre del curs 2020-2021. Us servirà per planificar la matrícula. Un cop comenci la docència, heu de consultar-lo a l'aula. (El pla docent pot estar subjecte a canvis.)

Moltes situacions es poden descriure en forma de jerarquia o xarxa entre diferents entitats: xarxa social, xarxa de carreteres, càrrecs en una organització, xarxa de computadors, connexions en un circuit... Matemàticament, aquesta noció de jerarquia o xarxa s'anomena graf. En aquesta assignatura, estudiarem el concepte de graf, les seves propietats i els problemes més usuals que s'hi poden plantejar. Aquests conceptes seran de gran aplicació en molts problemes del camp de la informàtica.

Per altra banda, alguns problemes que ens pot interessar resoldre sobre un graf són computacionalment complexos: un ordinador necessitaria molt temps de càlcul o espai de memòria per resoldre'ls. En la segona part de l'assignatura estudiarem els límits pràctics de càlcul d'un ordinador a partir d'aquest concepte de dificultat computacional. Definirem diferents famílies de problemes segons la seva complexitat i presentarem alguns exemples de problemes complexos, dins i fora de la teoria de grafs. Veurem que alguns d'aquests problemes complexos són molt freqüents en el camp de la informàtica i que tenen aplicacions a diferents àmbits, com ara la criptografia.

Amunt

Grafs i Complexitat és una assignatura obligatòria del grau en Enginyeria Informàtica.

Abans de cursar-la, es recomana haver cursat prèviament les assignatures de Pràctiques de programació (per estar familiaritzat amb el desenvolupament d'algorismes) i Lògica (per estar familiaritzat amb la notació lògica).

L'ús de grafs per modelar problemes és molt habitual en el camp de la informàtica. Per aquest motiu, utilitzareu els conceptes de grafs en múltiples assignatures dins el grau, com per exemple les assignatures de xarxes de computadors o les assignatures de l'itinerari de Computació.

Alguns dels problemes complexos que hem estudiat en aquesta assignatura també apareixen en altres assignatures:

  • En les assignatures, d'Intel·ligència Artificial i Aprenentatge Computacional es presenten estratègies per calcular solucions aproximades a problemes complexos de forma eficient.
  • A Criptografia s'utilitzen problemes computacionalment complexos per garantir la seguretat dels mecanismes de xifrat i desxifrat.
  • L'assignatura Disseny d'Estructures de Dades aplica de forma pràctica els conceptes de grafs i complexitat al camp de la programació. Disseny d'Estructures de Dades estudia com desenvolupar programes eficients: presenta diferents estructures de dades i algorismes per a problemes freqüents (alguns d'ells, problemes sobre grafs), així com els criteris per escollir el més adequat a cada situació.
  • L'assignatura Modelat de Sistemes estudia com resoldre problemes d'optimització complexos en l'àmbit de la logística i la planificació, també conegut com investigació operativa (operations research).

Amunt

Els conceptes de grafs s'utilitzen de forma transversal en molts àmbits de la informàtica, per modelar circuits, xarxes, organitzacions jeràrquiques, etc.

Pel que fa a la complexitat, els conceptes de cost temporal i espacial són fonamentals per a qualsevol programador.

Els problemes més complexos presentats en l'assignatura són rellevants per professionals en l'àmbit de la investigació operativa i la intel·ligència artificial. També són importants per professionals de la seguretat informàtica, per tal de saber avaluar la seguretat d'alguns criptosistemes.

Amunt

L'assignatura requereix coneixements bàsics d'algorísmica: la comprensió d'algorismes en pseudocodi i la capacitat de proposar algorismes que resolguin problemes nous. També són molt útils nocions sobre el càlcul del cost temporal d'un algorisme, tot i que es repassen aquests conceptes en el primer mòdul de l'assignatura.

A més, pel correcte seguiment de l'assignatura és important entendre la notació matemàtica i conèixer els conceptes de conjunt i funció.

Amunt

Abans de cursar aquesta assignatura, és molt recomanable haver cursat prèviament les assignatures següents:

  • Pràctiques de programació
  • Lògica

Amunt

Les competències generals del Grau que es posen de manifest en aquesta assignatura són:

  • Capacitat per utilitzar els fonaments matemàtics, estadístics i físics per comprendre els sistemes TIC.
  • Capacitat per analitzar un problema en el nivell d'abstracció adequat a cada situació i aplicar les habilitats i coneixements adquirits per a resoldre'l.

Les competències específiques d'aquesta assignatura són:

  • Conèixer el concepte de graf i els diferents tipus de graf (grafs orientats, grafs ponderats, pseudografs, multigrafs, ...).
  • Conèixer les principals propietats dels grafs i saber analitzar-les en un graf concret.
  • Conèixer els problemes més usuals sobre grafs (cerca de camins, distància mínima, arbre d'expansió minimal, ...), els algorismes que els resolen i saber-los aplicar en un graf concret.
  • Ser capaç de representar i analitzar un problema en termes de la teoria de grafs.
  • Conèixer el concepte de complexitat temporal i espacial d'un algorisme i saber analitzar-la en algorismes concrets.
  • Saber explicar els límits pràctics de càlcul en un ordinador (tractable vs intractable) i la jerarquia de classes de complexitat.
  • Ser capaç de classificar un problema dins la classe de complexitat apropiada.
  • Ser capaç de comparar la complexitat d'un problema amb la d'altres problemes coneguts.
  • Saber reconèixer els problemes intractables més coneguts i freqüents, especialment en el camp de la teoria de grafs.

Amunt

L'assignatura s'estructura en set mòduls:

Mòdul 1. Conceptes previs: funcions i algorismes

  1. Funcions
  2. Algorismes

Mòdul 2. Fonaments de grafs

  1. Caracterització d'un graf
  2. Estructura i manipulació de grafs

Mòdul 3. Recorreguts i connectivitat

  1. Recorreguts
  2. Algorismes d'exploració de grafs
  3. Connectivitat
  4. Distàncies en un graf

Mòdul 4. Arbres

  1. Conceptes bàsics
  2. Arbres generadors
  3. Arbres amb arrel

Mòdul 5. Grafs eulerians i grafs hamiltonians

  1. Grafs eulerians
  2. Grafs hamiltonians

Mòdul 6. Complexitat computacional

  1. El concepte de problema
  2. Mesures de complexitat
  3. Reducció i completesa

Mòdul 7. Problemes intractables

  1. Problemes intractables sobre grafs
  2. Altres problemes intractables

 

Amunt

Fonaments de grafs PDF
Problemes intractables PDF
Arbres PDF
Grafs i complexitat PDF
Complexitat computacional PDF
Conceptes previs: funcions i algorismes PDF
Grafs eulerians i grafs hamiltonians PDF
Recorreguts i connectivitat PDF

Amunt

L'assignatura s'ha estructurat en set mòduls, cadascun dels quals es desenvolupa en aquests apartats: la introducció, els objectius, el cos teòric amb els exercicis i els  exemples corresponents, una col·lecció d'exercicis d'autoavaluació, i bibliografia específica recomanada.

Quant a la forma en què es presenten aquests continguts, s'utilitzen quatre tipus de material essencial:

  1. Mòduls didàctics. Aquest material està constituït pels 7 mòduls de l'assignatura disponibles en format PDF a l'aula de l'assignatura.
  2. Guia d'estudi, disponible a l'apartat Recursos del aula, proposa un calendari detallat d'estudi dels mòduls i de realització d'activitats d'aprenentatge.
  3. Material interactiu ("Estudi d'algorismes") que consisteix en un applet que permet estudiar algunes característiques i simular algorismes associats als diversos tipus de grafs que s'estudiaran. Aquest material  el podeu trobar a l'espai de l'aula Materials i fonts, concretament a Eines i elements de suport - Explicacions complementàries.
  4. Llibre de problemes que podeu trobar en l'apartat Eines i elements de suport - Recull d'exercicis de grafs i complexitat de l'espai de l'aula Recursos. És un material d'especial interès amb problemes de tota l'assignatura, alguns totalment resolts i la resta amb la solució indicada (gran part d'aquests problemes han estat proposats a les PACs i Finals d'edicions anteriors de l'assignatura).

A més, l'assignatura disposa a l'espai Recursos, consultable on-line des de l'aula, diversos tipus de material, organitzats segons la seva importància i tipologia. Al llarg del curs es donaran estratègies per a un ús adequat de tots aquests materials i un millor aprofitament de les seves possibilitats.

Amunt

La Normativa acadèmica de la UOC disposa que el procés d'avaluació es fonamenta en el treball personal de l'estudiant i pressuposa l'autenticitat de l'autoria i l'originalitat dels exercicis fets.

La manca d'originalitat en l'autoria o el mal ús de les condicions en què es fa l'avaluació de l'assignatura és una infracció que pot tenir conseqüències acadèmiques greus.

Es qualificarà l'estudiant amb un suspens (D/0) si es detecta manca d'originalitat en l'autoria d'alguna activitat avaluable (pràctica, prova d'avaluació contínua (PAC) o final (PAF), o la que es defineixi al pla docent), sigui perquè ha utilitzat material o dispositius no autoritzats, sigui perquè ha copiat textualment d'internet, o ha copiat d'apunts, de materials, de manuals o d'articles (sense la citació corresponent), d'altres estudiants, o per qualsevol altra conducta irregular.

La qualificació de suspens (D/0) en les qualificacions finals d'avaluació contínua pot comportar l'obligació de fer l'examen presencial per a superar l'assignatura (si hi ha examen i si superar-lo és suficient per a superar l'assignatura segons indiqui el pla docent).

Quan aquesta mala conducta es produeixi durant la realització de les proves d'avaluació finals presencials, l'estudiant pot ser expulsat de l'aula, i l'examinador farà constar tots els elements i la informació relatius al cas.

D'altra banda, aquesta conducta pot donar lloc a la incoació d'un procediment disciplinari i l'aplicació, si escau, de la sanció que correspongui.

La UOC habilitarà els mecanismes que consideri oportuns per a vetllar per la qualitat de les seves titulacions i garantir l'excel·lència i la qualitat del seu model educatiu.

Amunt

Aquesta assignatura es pot superar per una doble via: d'una banda a partir de l'avaluació contínua (AC), i d'altra banda, mitjançant la realització d'un examen final (EX). Per a fer l'EX no cal haver superat l'AC. La fórmula d'acreditació de l'assignatura és la següent: AC o EX.

 

Amunt