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: 2017-2018

Coordinaciķ: F. Javier Soria de Diego

Departament: Departament de Matemātiques i Informātica

Crčdits: 6

Programa únic: S

 

 

Hores estimades de dedicaciķ

Hores totals 150

 

Activitats presencials

60

 

-  Teoricoprāctica

 

37,5

 

-  Prāctiques de laboratori

 

22,5

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

 

Transversals de la titulaciķ

   -

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.

   -

Utilitzar recursos bibliogrāfics físics i virtuals.

   -

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

   -

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.

   -

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

Específiques de la titulaciķ

   -

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

   -

Entendre i utilitzar correctament el llenguatge matemātic.

   -

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

   -

Saber identificar errors en raonaments incorrectes.

   -

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.

   -

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

   -

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

   -

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

 

 

 

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 i connexiķ

    2. Camins d’Euler

    3. Grafs hamiltonians: el problema del viatjant

    4. Aparellaments

    5. Problemes d’optimitzaciķ en grafs: optimitzaciķ lineal

    6. Grafs plans i coloraciķ

    7. Implementaciķ: estructures de dades i algorismes de grafs

     

     

    Metodologia i activitats formatives

     

    Hi ha dues hores setmanals de teoria i una de tasques de programació. Una quarta hora s’alterna cada quinze dies entre resolució de problemes i tasques de programació.

    Programari necessari: Visual Studio C++ Express

     

     

    Avaluaciķ acreditativa dels aprenentatges

     

    Avaluació

    La nota final (NF) es calcula prenent el 60 % de la part de teoria i problemes més el 40 % de la part de programació.

    La part de teoria i problemes val 60 punts sobre 100 i la de programació 40 punts sobre 100, en la nota final (NF).

    Per aprovar l’assignatura s’han de superar totes dues parts amb almenys 50/100 punts, i aconseguir almenys 30/60 punts en teoria i problemes, i 16/40 punts en programació.

    Avaluació continuada

    La nota de teoria i problemes (60 punts sobre 100) es calcula a partir de l’assistència, participació, resolució de problemes i dos exàmens (un parcial amb P1 punts de 25 i un final amb dues parts amb F1 i F2 punts de 25 cadascuna) que es duen a terme al llarg del semestre.

    En concret, els 60 punts —sobre el total de 100— amb què es valora aquesta part corresponen als apartats següents:

    — 50 punts pels dos exàmens: màx(P1,F1)+F2;
    — 10 punts per la resolució de problemes a classe i per l’assistència.

    La nota de programació (40 punts sobre 100) correspon a la puntuació de les tasques de programació lliurades dins dels terminis indicats al llarg del semestre, en les quals es proposa implementar programes de diferents algorismes en grafs i algunes aplicacions, fent servir les tècniques de programació explicades. Es proposen quatre tasques que puntuen 10 cada una.

    Els alumnes que superin la part de programació tenen la possibilitat d’una reavaluació consistent en un nou examen de teoria i problemes —que pot fer variar només la nota d’aquesta part en la nova nota final de reavaluació (NFR). En la reavaluació no es consideraran els punts obtinguts en l’avaluació continuada. La nota de programació emprada és la mateixa puntuació obtinguda en les tasques de programació ja lliurades dins els terminis indicats al llarg del semestre.

    La nota definitiva es calcula prenent el màxim de les dues notes finals:

    Nota definitiva = màx[NF,NFR].

     

    Avaluaciķ única

    L’avaluació única es calcula a partir de la nota de l’examen final de teoria i problemes (sobre 60 punts) i de la nota obtinguda en les tasques de programació lliurades dins els terminis indicats al llarg del semestre (sobre 40 punts).

    IMPORTANT

    Les tasques de programació s’han de presentar al Campus Virtual de l’assignatura dins els terminis que s’hi publiquen per a cadascuna d’elles, tant si es tracta d’avaluació continuada, única o de reavaluació. No està permès l’ús de programes fets per altres estudiants, tant d’aquest curs com de cursos anteriors. Si el professorat ho creu oportú, la qualificació de les tasques de programació pot comportar una entrevista als alumnes que les hagin lliurat per tal d’esbrinar-ne l’autoria.