Pla docent de l'assignatura

 

 

Catalā English Tanca imatge de maquetació

 

Imprimeix

 

Dades generals

 

Nom de l'assignatura: Grafs

Codi de l'assignatura: 360150

Curs acadčmic: 2021-2022

Coordinaciķ: KOLJA BEN KNAUER

Departament: Departament de Matemātiques i Informātica

crčdits: 6

Programa únic: S

 

 

Hores estimades de dedicaciķ

Hores totals 150

 

Activitats presencials i/o no presencials

60

 

-  Teoria

Presencial

 

30

 

( Presencial i no presencial.)

 

-  Prāctiques de problemes

Presencial

 

15

 

( Presencial i no presencial.)

 

-  Prāctiques de laboratori

Presencial

 

15

 

( Presencial i no presencial.)

Treball tutelat/dirigit

45

Aprenentatge autōnom

45

 

 

Recomanacions

 

Aquest és un curs bàsic que requereix pocs coneixements previs: combinatòria, teoria de conjunts i relacions, i tècniques de programació.

 

 

Competčncies que es desenvolupen

 

   -

Tenir i comprendre els coneixements bāsics de la matemātica.

   -

Capacitat de reunir i d'interpretar dades rellevants que permetin d'emetre informes raonats i obtenir conclusions en problemes científics o d'altres āmbits que requereixin eines matemātiques.

   -

Capacitat per transmetre informaciķ, idees, problemes i solucions matemātiques a un públic tant especialitzat com no especialitzat.

   -

Utilitzar recursos bibliogrāfics físics i virtuals.

   -

Saber aplicar els coneixements adquirits i la capacitat d'anālisi a la resoluciķ de problemes en contextos acadčmics i professionals.

   -

Capacitat per treballar en equip.

   -

Assimilar conceptes matemātics nous en termes d'altres ja coneguts.

   -

Cončixer algunes de les aplicacions de la matemātica a altres branques de la cičncia i la tecnologia.

   -

Desenvolupar programes informātics propis que implementin algoritmes senzills.

   -

Utilitzar aplicacions informātiques per a la resoluciķ de problemes matemātics.

   -

Entendre i utilitzar correctament el llenguatge matemātic.

   -

Saber identificar errors en raonaments incorrectes.

   -

Capacitat de comprendre problemes, abstreure'n l'essčncia i formular-los matemāticament per facilitar-ne l'anālisi i la resoluciķ.

   -

Saber seleccionar i aplicar el procés matemātic adequat per a cada problema.

   -

Capacitat de construir un model matemātic en situacions simples de la realitat.

Objectius d'aprenentatge

 

Referits a coneixements

— Conèixer els conceptes bàsics de matemàtica discreta: grafs, vèrtexs i relacions d’adjacència, arbres, existència de camins d’Euler i Hamilton, coloració de grafs, aparellaments.

— Ser capaç de dur a terme una modelització i resolució mitjançant l’ordinador de problemes d’optimització de rutes, interconnexió, assignació, etc.

 

Referits a habilitats, destreses

— Conèixer els resultats bàsics sobre arbres i grafs: nombre de vèrtexs i arestes, classificació, etc.

— Conèixer criteris per decidir quan és eulerià o hamiltonià un graf.

 

 

Blocs temātics

 

1. Arbres, camins, cicles

2. Hamiltonicitat

3. Grafs eulerians

4. Coloració de grafs

5. Planarietat

6. Aparellaments

7. Digraf

8. Morfismes, grups i grafs de Cayley

9. Àlgebra lineal de matrius d’incidència i d’adjacència

10. Algoritmes i codificació

11. Fonaments del comptatge

 

 

Metodologia i activitats formatives

 

Els estudiants assisteixen a 2 hores setmanals de classes teòriques, 1 hora de sessions de resolució de problemes i 1 hora de sessions amb tasques de programació.

Durant les sessions de problemes, els estudiants interactuen entre ells i presenten les solucions als companys amb rigor matemàtic. Aquests problemes tenen com a objectiu proporcionar una millor comprensió dels continguts introduïts a les classes teòriques.

Les tasques de programació se centren en la implementació de nocions i algoritmes treballats a les sessions teòriques sobre C++.

 

 

Avaluaciķ acreditativa dels aprenentatges

 

Avaluació continuada

L’avaluació continuada consisteix en sessions de resolució de problemes (30 % de la nota final), tasques de programació (30 %) i un examen final (40 %).

Les sessions de problemes s’organitzen de la següent manera: el professorat dona un llistat de problemes als estudiants perquè els treballin individualment una setmana abans de la sessió de problemes. A classe, els estudiants presenten les solucions a la pissarra dels problemes que han sabut resoldre. Cada estudiant rep els punts corresponents al nombre d’exercicis que ha solucionat correctament.

Les tasques de programació consisteixen en tres treballs que s’han de fer a casa (10 % de la nota final) i que s’han de lliurar mitjançant el Campus Virtual. L’última tasca de programació es pot substituir per una activitat d’Aprenentatge de Serveis (ApS), que consisteix a triar un tema amb l’ajuda del professorat i presentar-lo a alumnes de batxillerat.

 

Avaluaciķ única

L’avaluació única consisteix en un examen final (70 % de la nota final) i una tasques de programació (30 %).

IMPORTANT

Les tasques de programació s’han de lliurar mitjançant el Campus Virtual de l’assignatura. Els estudiants han de ser els autors del programari. No es permet l’ús de programari fet per altres estudiants.