• Descripció

Aquesta assignatura fonamenta molts dels processos directament implicats en l'Enginyeria d'Informàtica, tant pel que fa al programari com al maquinari, des de l'estudi de les estructures de la informació a la construcció de circuits i l'ús més eficient d'aquestes estructures; fins i tot pot proporcionar eines per conèixer els seus límits. De fet, l'origen i el desenvolupament d'aquesta nova branca matemàtica ha anat sempre lligat a l'evolució de la informàtica i, per això, la seva mútua dependència no és casual.

• Informació prèvia a la matrícula

És molt convenient haver cursat de forma recent els cursos de matemàtiques corresponents a Batxillerat o nivell equivalent. En cas que no sigui així, s'aconsella cursar prèviament el curs d'Iniciació a les Matemàtiques per a Enginyeries que ofereix la UOC.

S'aconsella cursar Fonaments de programació abans d'aquesta assignatura. 

• Objectius i competències

Globalment, els objectius bàsics que s'han d'assolir són:

1.      Entendre els principis bàsics de comptar com el de l'addició, el de la multiplicació, el de les capses i el de la inclusió-exclusió. Aplicar-los correctament.

2.      Reconèixer quan un tipus de mostra és ordenada i utilitzar els recursos adients per a fer-ne el recompte.

3.      Reconèixer quan un tipus de mostra no és ordenada i utilitzar els recursos adients per a fer-ne el recompte.

4.      Reconèixer els problemes de distribucions i particions on poden utilitzar-se els nombres multinomials  i resoldre'ls amb el seu ajut.

5.       Identificar la funció generadora d'un problema combinatori.

6.      Saber reconèixer els problemes que admeten una formulació recursiva i una resolució a través de les equacions recurrents.

7.      Entendre el concepte d'algorisme per resoldre un problema i saber calcular la seva complexitat.

8.      Entendre el concepte de graf i modelar certes situacions amb grafs.

9.      Identificar els grafs més habituals i descriure les seves característiques fonamentals.

10.  Saber aplicar, reproduir i simular els algorismes d'exploració d'un graf, sense ajut de cap eina.

11.  Entendre la noció de connectivitat i aplicar-la correctament.

12.  Saber calcular les distàncies dins d'un graf amb l'ajut dels algorismes adients.

13.  Saber caracteritzar els arbres i, específicament, els arbres amb arrel. Saber aplicar els algorismes de determinació d'un arbre generador minimal.

14.  Identificar els grafs eulerians i hamiltonians i caracteritzar-los.

 15.  Entendre el problema del viatjant de comerç. Conèixer i saber aplicar l'algorisme de resolució aproximada d'aquest problema.

Els objectius de cada mòdul es troben en el material associat a l'assignatura.

• Continguts

• Llista dels materials de què disposa l'assignatura

• Materials

L'assignatura s'ha estructurat en vuit 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:

1. Material imprès. Aquest material està constituït pels 8 mòduls de l'assignatura editat en paper per la UOC.

2. Material interactiu ("Estudi d'algorismes") per a la 2a part de l'assignatura, 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 Recursos, concretament a Eines i elements de suport - Explicacions complementàries.

3. Llibre de problemes que podeu trobar en l'apartat Eines i elements de suport - Recull d'exercicis de matemàtica discreta 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.