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 la UOC per a l'assignatura   Informació addicional sobre els recursos d'aprenentatge i eines de suport   Informacions sobre l'avaluació a la UOC   Consulta del model d'avaluació  
Aquest és el pla docent de l'assignatura per al segon semestre del curs 2022-2023. Podeu consultar si l'assignatura s'ofereix aquest semestre a l'espai del campus Més UOC / La universitat / Plans d'estudis). 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
  • Àlgebra

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

Lògica d'enunciats PDF
Recorreguts i connectivitat PDF
Grafs eulerians i grafs hamiltonians PDF
Fonaments de grafs PDF
Arbres PDF
Conceptes previs: funcions i algorismes PDF
Complexitat computacional PDF
Els nombres PDF
Elements d'àlgebra lineal i geometria PDF
Problemes intractables 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 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.

Amunt

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 o dispositius no autoritzats durant l'avaluació, entre d'altres, són conductes irregulars que poden tenir conseqüències acadèmiques i disciplinàries greus.

D'una banda, si es detecta alguna d'aquestes conductes irregulars, pot 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 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 practicat qualsevol altra conducta irregular.

De l'altra, i d'acord amb les normatives acadèmiques, les conductes irregulars en l'avaluació, a més de comportar el suspens de l'assignatura, poden donar lloc a la incoació d'un procediment disciplinari i a l'aplicació, si escau, de la sanció que correspongui.

La UOC es reserva la potestat de sol·licitar a l'estudiant que s'identifiqui o que acrediti l'autoria del seu treball al llarg de tot el procés d'avaluació pels mitjans que estableixi la Universitat (síncrons o asíncrons). 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ó i que s'asseguri que funcionen correctament.

La verificació dels coneixements per garantir l'autoria de la prova no implicarà en cap cas una segona avaluació.

Amunt

Aquesta assignatura es pot superar únicament mitjançant la realització d'un examen final (EX). La nota final de l'avaluació contínua (AC) complementa la nota de l'examen final (EX) mitjançant l'encreuament d'acord amb la fórmula corresponent. La fórmula d'acreditació de l'assignatura és la següent: EX + AC o EX .

 

Amunt