Matemātica Discreta (MD)
| Professors Responsables: |
JOAN TRIAS PAIRO (avtrias ma2.upc.edu)
|
|
Crèdits: 7.5 (3.0 T 3.0 P 1.5 L)
| |
Departament:
MAII
|
Tipus d'assignatura
Assigatura de la Fase de Selecció
Requisits de l'assignatura
|
AL
- Pre-correquisit per la EI , ETIG , ETIS
|
|
Objectius docents
Les aplicacions de la matemātica discreta a la informātica han
fet que s'inclogui aquesta assignatura en el nou pla d'estudis. Hi ha diverses
opinions sobre el que hauria de contenir un curs de matemātica discreta.
En el nostre cas, tenint en compte que ens trobem en uns estudis d'enginyeria
en informātica s'ha cregut convenient incloure en el programa una part
de teoria de grafs i una introducciķ a la combinatōria
enumerativa.
Entre d'altres raons destaquem que en l'anālisi d'algoritmes i la
determinaciķ de la complexitat computacional apareixen sovint problemes
combinatoris. Molts d'aquests problemes admeten traducciķ a teoria de
grafs. A més, la teoria de grafs permet modelitzar estructures de dades
i estudiar problemes de xarxes i d'optimitzaciķ.
Amb aquest programa s'intenta que l'alumne conegui les eines i resultats
bāsics de la teoria de grafs i de la combinatōria enumerativa que
podran ser-li d'utilitat en els estudis d'informātica.
Programa
1. Conceptes bāsics (Durada: 2 setmanes)
- Grafs, multigrafs, pseudografs.
- Isomorfismes. Tipus de grafs.
- Grau. Matriu d'adjacčncia.
- Subgrafs. Operacions amb grafs.
2. Recorreguts (Durada: 2 setmanes)
- Recorreguts. Circuits. Camins. Cicles.
- Distància. Connexió.
- Ponts i vèrtexs de tall. Connexitat.
- Grafs eulerians.
- Grafs hamiltonians.
3. Arbres (Durada: 2 setmanes)
- Definiciķ. Propietats bāsiques. Carateritzaciķ
- Arbres generadors. Condiciķ d'existčncia. Arbre generador
minimal. Algoritmes de Kruskal i Prim.
- Arbres dirigits. Arbres amb arrel. Arbres m-aris.
- Enumeraciķ d'arbres.
4. Altres temes de grafs (Durada: 2 setmanes)
- Planaritat: grafs planars. Fķrmula d'Euler. Caracteritzaciķ
dels grafs planars: Teorema de Kuratowski.
- Coloraciķ: grafs k-colorables. Teorema dels cinc colors.
Coloraciķ de mapes. Teorema dels quatre colors. Coloraciķ
d'arestes.
5. Objectes i nombres combinatoris (Durada: 4 setmanes)
- Cardinal de la unió i del producte cartesià de conjunts.
- Principi de les caselles.
- Aplicacions. Aplicacions injectives.
- Subconjunts i multiconjunts. Els nombres binomials. Igualtats
combinatòries. Teorema del binomi.
- Particions d'un conjunt. Nombres de Stirling de segon tipus. Aplicacions
exhaustives. Nombres multinomials.
- Particions d'un enter.
- Principi d'inclusió-exclusió.
6. Successions recurrents (Durada: 2 setmanes)
- Relacions recurrents.
- Equacions recurrents lineals.
Avaluació
En l'avaluaciķ de l'assignatura es tindrā en compte el
següent:
La qualificaciķ de les sessions de Laboratori (L).
Control de teoria-problemes (P)
La qualificaciķ de l'examen final (F).
La qualificaciķ de l'assignatura serā N=0.2L+0.2P+0.6F.
Bibliografia
Bibliografia bàsica
- BIGGS, N.L Matemática Discreta Vicens Vives, 1994
- BRUNAT,J.M Combinatoria
i teoria de grafs Edicions UPC, 1996
- COMELLAS i altres Matemàtica
Discreta Edicions UPC, 1994
- Joan Trias Pairķ Matemātica Discreta. Problemes resolts Edicions UPC, 2001
Bibliografia complementària
- ANDERSON, I Introducción a la
Combinatoria Vicens Vives, 1993
- KNUTH, D.E Algoritmos fundamentales,
Vol. I Reverté, 1986
- CHARTRAND G., LESNIAK L Graphs and
digraphs Wadsworth and
Brooks/Cole, 1986
- GAVRILOV G.P., SAPOZHENKKO A.A Problemas de matemàtica discreta Mir, 1980
- GOULD
R Graph theory Benjamin-Cummings, 1988
- GRAHAM R.L., KNUTH D.E., PATASHNIK O Concrete
mathematics Addison-Wesley, 1989
- GRIMALDI, R.P Matemáicas discreta y
combinatoria Addison-Wesley, 1989
- HARARY F Graph theory Addison-Wesley
, 1969
- ROBERTS F.S Applied combinatorics Prentice Hall, 1984
- ROSEN,
K.H Discrete Mathematics and its Applications (Segona ) McGraw-Hill
, 1991
- TUCKER A Applied combinatorics Wiley, 1984
- WILSON, R. J Introducción a la teoría de
grafos Alianza, 1972
Informació complementària
CLASSES PRACTIQUES
Les classes prāctiques consistiran bāsicament en la
resoluciķ de problemes, perō no es limitaran a la resoluciķ
d'aquests per part del professor a la pissarra. És indispensable que
l'alumne hagi intentat abans de resoldre els problemes a fi d'aclarir els dubtes
que puguin sorgir i adquirir una certa habilitat en la resoluciķ de
problemes. Amb aquesta finalitat els alumnes disposaran de col.leccions de
problemes de cada tema, alguns dels quals es faran a classe. Els altres es podran
utilitzar per al treball personal de l'alumne.
CLASSES DE LABORATORI
Les classes de laboratori consistiran en la resoluciķ d'un problema amb
l'ajut d'algun programa de cālcul simbōlic i numčric.
Algunes d'aquestes sessions serviran per avaluar l'assignatura.
|
