Pla docent de l'assignatura

 

 

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. Trees, paths, cycles

    2. Hamiltonicity

    3. Eulerian graphs

    4. Graph colouring

    5. Planarity

    6. Matchings

    7. Digraphs

    8. Morphisms, groups, and Cayley graphs

    9. Linear algebra of incidence and adjaceny matrix

    10. Algorithms and coding

    11. Basics of counting

     

     

    Metodologia i activitats formatives

     

    Every week there is a block of 2h of theory class, 1h of problems and exercises, and 1h of programming.

    The problems and exercise class is intended to interact and to learn presenting solutions to each other in a mathematically sound way, Moreover, the problems will serve to understand better the content of the theory class. The programming will be concerned with the implementation of notions and algorithms discussed in the theory class in C++.

     

     

    Avaluaciķ acreditativa dels aprenentatges

     

    Avaluació
    The final grade is composed from 30% the points of the problem session, 30% of programming, and 40% of the final exam.

    The problem sessions work as follows:

    1 week before the problem session we give you a list of problems to work on independently. In the session (those present) declare which of the problems they have solved, We will then call people to the black board to present their solutions, and evaluate, You receive the points corresponding to the number of problems you have solved correctly.

    The programming is evaluated by three home works, that you have to submit (each counting 10%) to Campus Virtual. Instead of the last programming homework you can alternatively make an activity d’Aprenentatge Servei (ApS). This is, together with the professor you choose a topic and give a class/presentation about it to students of batxillerat.

     

    Avaluaciķ única

    L’avaluació única is computed by 70% final exam and 30% programming.

    IMPORTANT
    The programming homework has to be submitted through Campus Virtual of the course. The homework has to be coded independently and it is not allowed to use the code of our students.