Presentació

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.

Crèdits: 6 ECTS

Inici: 20 febrer 2019

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 a resoldre'ls. A partir d'aquest concepte de dificultat computacional estudiarem els límits pràctics de càlcul d'un ordinador. Definirem diferents famílies de problemes segons la 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 en diferents àmbits, com ara la criptografia.

Objectius i competències

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

Continguts

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

Requisits previs

Pots matricular-te de les assignatures d'aquests títols si:

  • Has superat com a mínim una de les assignatures incloses en el títol propi.

Requisits tècnics

Per al seguiment d'aquesta assignatura és necessari disposar d'un ordinador de sobretaula o portàtil amb connexió a internet (per banda ampla, ADSL o cable) i un monitor amb una resolució mínima de 1.024 x 768 píxels. Per a poder consultar alguns materials també pot ser necessari un lector de DVD.

És recomanable que la CPU (sigui d'un ordinador de sobretaula o d'un portàtil) tingui com a mínim 2 GB de memòria RAM i 2 GHz de velocitat de processador.

És necessari un sistema operatiu Windows XP (o superior), Mac OS o Linux*. També es necessita tenir instal·lat un dels navegadors següents: Internet Explorer 9.0 (o superior), Mozilla Firefox o Chrome.

* A causa de la gran varietat de distribucions que hi ha, no especifiquem totes les versions possibles.

Materials

Els materials didàctics d'aquesta assignatura consten d'apunts en suport paper i en format web, i recursos en xarxa.

Professorat

Jordi Casas Roma

Matrícula i preu

Procés de matrícula

Emplena el formulari de matrícula al que podràs accedir des de la part superior de la pàgina.

Accés al campus

Si no recordes les claus d'accés al campus virtual, les pots recuperar des del següent enllaç.

Formes de pagament

El pagament dels cursos es fa amb targeta.

  • TPVV: pagament amb una targeta de crèdit o de dèbit de qualsevol entitat financera, mitjançant el TPVV (terminal de punt de venda virtual) de «la Caixa».

Informació sobre el desistiment de matrícula

Preu

Concepte Preu
Preu del curs 212,00 €

Matrícula oberta

Matricula't

Inici de docència: febrer 2019

Informació de preu i matrícula