• Descripció

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.

• L'assignatura en el conjunt del pla d'estudis

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).

• Camps professionals en què es projecta

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.

• Coneixements previs

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ó.

• Informació prèvia a la matrícula

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

• Pràctiques de programació
• Lògica
• Àlgebra

• Objectius i competències

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.

• Continguts

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

• Consulta dels recursos d'aprenentatge de la UOC per a l'assignatura

• Informació addicional sobre els recursos d'aprenentatge i eines de suport

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 tres tipus de material essencial i un material opcional però racomanat:

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, publicada a l'aula, proposa un calendari detallat d'estudi dels mòduls i de realització d'activitats d'aprenentatge.
3. 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.

• Informacions sobre l'avaluació a la UOC

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 realitzats.

La manca d'autenticitat en l'autoria o d'originalitat de les proves d'avaluació; la còpia o el plagi; l'intent fraudulent d'obtenir un resultat acadèmic millor; la col·laboració, l'encobriment o l'afavoriment de la còpia, o la utilització de material, programari o dispositius no autoritzats durant l'avaluació, entre altres, són conductes irregulars en l'avaluació que poden tenir conseqüències acadèmiques i disciplinàries greus.

Aquestes conductes irregulars poden comportar el suspens (D/0) en les activitats avaluables que es defineixin en el pla docent -incloses les proves finals- o en la qualificació final de l'assignatura, sigui perquè s'han utilitzat materials, programari o dispositius no autoritzats durant les proves, com ara xarxes socials o cercadors d'informació a internet, perquè s'han copiat fragments de text d'una font externa (internet, apunts, llibres, articles, treballs o proves d'altres estudiants, etc.) sense la citació corresponent, o perquè s'ha dut a terme qualsevol altra conducta irregular.

Així mateix, i d'acord amb la normativa acadèmica, les conductes irregulars en l'avaluació també poden donar lloc a la incoació d'un procediment disciplinari i a l'aplicació, si escau, de la sanció que correspongui, de conformitat amb l'establert a la normativa de convivència de la UOC.

En el marc del procés d'avaluació, la UOC es reserva la potestat de:

• Sol·licitar a l'estudiant que acrediti la seva identitat segons l'establert a la normativa acadèmica.
• Sol·licitar a l'estudiant que acrediti l'autoria del seu treball al llarg de tot el procés d'avaluació, tant avaluació contínua com avaluació final, per mitjà d'una prova oral o els mitjans síncrons o asíncrons que estableixi la Universitat. Aquests mitjans tindran per objecte verificar els coneixements i les competències que garanteixin l'autoria; en cap cas no implicaran una segona avaluació. Si no és possible garantir l'autoria de l'estudiant, la prova serà qualificada amb D, en el cas de l'avaluació contínua, o amb un Suspens, en el cas de l'avaluació final.

  A aquests efectes, la UOC pot exigir a l'estudiant l'ús d'un micròfon, una càmera o altres eines durant l'avaluació; és responsabilitat de l'estudiant assegurar que aquests dispositius funcionen correctament.

• Consulta del model d'avaluació