Curs 2014-15

Àlgebra Lineal i Matemàtica Discreta

Titulació: Codi: Tipus:
Grau en Enginyeria Informàtica 21404 Bàsica 1r curs
Grau en Enginyeria Telemàtica 21294 Bàsica 1r curs
Grau en Enginyeria en Sistemes Audiovisuals 21593 Bàsica 1r curs

 

Crèdits ECTS: 8 Dedicació: 200 hores Trimestre: 1r i 2n

 

Departament: Dept. de Tecnologies de la Informació i les Comunicacions
Coordinador: Vanesa Daza
Professorat:

Vanesa Daza, Luís Ferraz, Gabriela Ghimpeteanu, Raquel Gil, Nikolaos Makriyannis, Esmeralda Ruiz, Javier Vázquez
Idioma:

Vanesa Daza (CAT)

Luís Ferraz (CAT)

Gabriela Ghimpeteanu (CAST)

Raquel Gil (CAT)

Nikolaos Makriyannis CAST)

Esmeralda Ruiz (CAT)

Javier Vázquez (CAT)

 
Horari:
Campus: Campus de la Comunicació - Poblenou

 

Presentació de l'assignatura

L’assignatura d’Àlgebra Lineal i Matemàtica Discreta és una de les assignatures de fonaments matemàtics que es cursa dins dels estudis del Grau en Enginyeria en Sistemes Audiovisuals, del Grau en Enginyeria Telemàtica i del Grau en Enginyeria en Informàtica. En aquests graus, Àlgebra Lineal i Matemàtica Discreta s’imparteix en el primer i segon trimestres del primer any dels estudis i és una assignatura bàsica, de 8 crèdits ECTS.

Parteix dels conceptes matemàtics que els estudiants han treballat en la programació del Batxillerat i els consolida i amplia. Juntament amb les altres assignatures de fonaments matemàtics, proporcionarà als estudiants les eines i la base matemàtica per a treballar els conceptes propis del grau. En el present Pla Docent es detallaran les competències i capacitats a que condueix l’aprenentatge de l’assignatura, on paral—lelament al desenvolupament i estudi dels blocs de continguts teòrics en que està organitzada l’assignatura, juguen un paper fonamental els mòduls pràctics i activitats associades basades en exercicis i problemes, on es pretén consolidar la comprensió dels conceptes i tècniques adquirides.

L’assignatura està estructurada en dos grans eixos: un primer dedicat a aspectes fonamentals de l’Àlgebra Lineal i un segon dedicat a alguns àmbits fonamentals de la Matemàtica Discreta de gran aplicabilitat en les Enginyeries relacionades amb les TIC, com serien la Teoria de Grafs o l’Aritmètica. De manera més detallada, el primer eix està enfocat a l’aprenentatge de: (i) les idees bàsiques de l’àlgebra lineal: espais i subespais vectorials, independència lineal, dimensió, bases, aplicacions lineals, determinants, etc.; (ii) la solució de sistemes lineals; (iii) valors i vectors propis. L’eina o idea inicial a partir de la qual es desenvoluparan totes aquestes competències és la solució de sistemes lineals pel mètode d’eliminació de Gauss.

El segon eix està dedicat principalment a desenvolupar les idees essencials de la Teoria de Grafs, amb algunes notes de combinatòria i algoritmes d’Optimització en Xarxes de transport. Contribueix així a l’aprenentatge d’algoritmes importants en la formació d’un enginyer, com per exemple l’algoritme de Dijkstra o l’algoritme de Ford-Fulkerson, servint a més de complement a altres assignatures.

En aquesta assignatura es pretén aportar formació matemàtica i una major maduresa en la capacitat de raonament de l’estudiant, potenciant la seva capacitat d’abstracció. L’assignatura està enfocada a l’aprenentatge d’un conjunt de capacitats i estratègies que permetin a l’alumne analitzar un problema, cercar-ne un model matemàtic per a descriure’l, resoldre’l i analitzar-ne la solució obtinguda.

 

 

Prerequisits

Els coneixements previs que pressuposa aquesta assignatura són els propis d’una base matemàtica de nivell de batxillerat, en particular nocions i procediments bàsics de càlcul, geometria i d’àlgebra lineal, així com una certa familiarització amb l’aritmètica de nombres complexes. Al tractar-se d'una de les dues assignatures (juntament amb Càlcul i Mètodes Numèrics) de Matemàtiques del primer i segon trimestre del primer curs dels tres graus, es reforçarà als estudiants que presenten carències en matemàtiques elementals amb exercicis complementaris per tal d’aconseguir un cert anivellament de tots els estudiants.

Per a un bon seguiment de l’itinerari formatiu planificat en aquesta assignatura, s’espera de l’estudiant que entengui que l’aprenentatge en aquesta matèria es basa en el propi treball i el desig d’aprendre i entendre. L’aprenentatge de l’assignatura li reforçarà el domini del llenguatge científic i el raonament abstracte. Se li demana l’autoexigència en els raonaments i l’elaboració de treball, així com la capacitat d’esforç i la participació constructiva.

 

Competències

Competències generalsCompetències específiques

Instrumentals

1. Capacitat de comprendre i analitzar enunciats matemàtics.
2. Capacitat d’identificar la metodologia adequada per analitzar un problema i trobarne la solució.
3. Capacitat per aplicar els coneixements a l'anàlisi de situacions i la resolució de problemes.
4. Capacitat d’abstracció
5. Capacitat de sistematització.

Sistèmiques

6. Capacitat per progressar en els processos de formació i aprenentatge de manera autònoma i contínua
7. Capacitat de motivació per la qualitat i per l'assoliment
8. Capacitat per cercar solucions més adequades segons les característiques de cada problema/situació/context
9. Capacitat per inferir nocions matemàtiques.

Eix d'Àlgebra lineal:

1. Entendre l’àlgebra i la geometria bàsica dels nombres complexos.
2. Dominar els conceptes de vector i matriu i les operacions amb vectors i matrius.
3. Conèixer la geometria dels sistemes lineals, la seva resolució, els conceptes d'espai vectorial i canvis de base.
4. Comprensió i domini del mètode d’eliminació Gaussiana per a la resolució de sistemes d’equacions lineals.
5. Entendre el concepte d’espai vectorial.
6. Entendre el concepte de base d’un espai vectorial.
7. Comprensió dels quatre subespais vectorials fonamentals.
8. Comprensió del concepte i tècnica dels canvis de base.
9. Entendre els concepte d’ortonormalització d’una base, en particular domini del mètode de Gram-Schmidt.
10. Comprensió de les rotacions i transformacions bàsiques.
11. Domini del concepte de valor i vector propi.
12. Ser capaç d'aplicar les tècniques de diagonalització de matrius.
13. Estudiar els valors i vectors propis, les matrius simètriques i la seva diagonalització.


Eix de Matemàtica Discreta:

14. Dominar els diferents models de grafs

15. Estudi de les propietats característiques dels grafs, tals l’isomorfisme, planaritat, connexitat, i el principi de les mans encaixades.

16. Comprensió del concepte d’Arbre.

17. Estudi de diferents algoritmes de cerca

18. Domini del concepte d’arbre generador i d’algoritmes per a calcular-ne.

19. Estudi dels camins de cost mínim i del algorisme de Dijkstra. 

20. Estudi de propietats bàsiques sobre grafs tals com coloracions, conjunt independents, recobriments, camins i cicles hamiltonians.

21. Conèixer el teorema de tall mínim-flux màxim. Conèixer i saber implementar l’algoritme de Ford-Fulkerson per resoldre el problema del flux màxim en una xarxa.

22. Conèixer les eines bàsiques per al comptatge d’entitats combinatòries

 

 

 

Avaluació

Durant el transcurs del curs es farà una avaluació continuada a través de les activitats d’aprenentatge proposades. Es pretén amb això una efectiva retroalimentació informativa per als estudiants, ajudar a la verificació de l’adquisició de les diferents competències detectant a temps dificultats i proporcionant feedback als estudiants per orientar el seu aprenentatge i introduir les modificacions necessàries.

Aquests mecanismes d’avaluació, estan estructurats en dos grans eixos, d’acord amb l’estructura d’aprenentatge de l’assignatura:

Eix d’Àlgebra lineal

Per tant, la nota corresponent a l’eix d’Àlgebra Lineal es calcula com

20%(control parcial) + 80%(control final) = nota eix d’Àlgebra Lineal

Aquesta nota ha de ser almenys de 5 per aprovar l’eix d’Àlgebra Lineal.

La participació a les sessions de seminari serà avaluada. Aquells alumnes que participin de manera activa poden obtenir fins a un punt extra de la qualificació final de l’eix.

Eix de Matemàtica Discreta

· Control Parcial: control d’exercicis, problemes, i preguntes teòriques per tal de fer un seguiment dels conceptes explicats a les classes de teoria. El control representarà el 20% de la qualificació de l’eix de matemàtica discreta. Els blocs de contingut avaluables durant aquest primer control seran l’1 i el 2. Aquest control no és recuperable al juliol.
· Control Final: prova on s’avaluen els blocs de continguts 1, 2, 3, 4 i 5, és a dir, sobre tot l’eix de Matemàtica Discreta. Constarà d’exercicis i problemes representatius on s’hauran d’aplicar tots el conceptes de teoria i demostrar un domini de les competències desenvolupades en l’eix de matemàtica discreta. Representa un 80% de la qualificació de matemàtica discreta. En cas contrari, l’estudiant disposa d’una segona oportunitat al mes de juliol.

Per tant, la nota corresponent a l’eix de matemàtica discreta es calcula com

20%(control parcial) + 80%(control final) = nota eix de matemàtica discreta

Aquesta nota ha de ser almenys de 5 per aprovar l’eix de matemàtica discreta.

La participació a les sessions de seminari serà avaluada. Aquells alumnes que participin de manera activa poden obtenir fins a un punt extra de la qualificació final de l’eix.

La Nota Final de l’assignatura Àlgebra Lineal i Matemàtica Discreta s’obté fent la mitjana de:

A més, es tenen en compte els següents criteris:

 

Continguts

Blocs de contingut

L’assignatura està estructurada quatre blocs de continguts per a l’eix d’Àlgebra Lineal i cinc blocs de contingut per a l’eix de Matemàtica Discreta:

Eix I: Àlgebra lineal
- Bloc de contingut 1. Resolució de Sistemes d’equacions lineals.
- Bloc de contingut 2. Els espais vectorials i els seus subespais.
- Bloc de contingut 3. Els espais vectorials euclidians.
- Bloc de contingut 4. Diagonalització

Eix II: Matemàtica Discreta
- Bloc de contingut 5. Elements de teoria de grafs.
- Bloc de contingut 6. Arbres i grafs dirigits acíclics
- Bloc de contingut 7. Camins i altres propietats dels grafs.
- Bloc de contingut 8. Optimització de fluxos en xarxes
- Bloc de contingut 9. Eines de comptatge

Organització i concreció dels continguts

Bloc de contingut 1. Resolució de Sistemes d’equacions lineals.

ConceptesProcediments

1. Nombres complexos
2. Funcions. Inverses. Graf d’una funció.
3. Vectors i Matrius.
4. Equacions lineals. Sistemes.
5. La geometria dels sistemes d’equacions lineals.
6. Sistemes singulars.

- Propietats algebraiques i geomètriques bàsiques dels complexos.
- Diferenciació dels diferents tipus de funcions.
-Demostracions per reducció a l'absurd.
-Operacions amb vectors i matrius.

-El mètode de Gauss.
-Càlcul de la matriu inversa

Bloc de contingut 2. Els espais vectorials i els seus subespais

ConceptesProcediments

1. Els subespais vectorials
3. Els quatre subespais fonamentals.
4. Independència lineal. Bases. Dimensió.

- Càlcul dels quatre subespais fonamentals de A
- Càlcul d’independència lineal de vectors.

Bloc de contingut 3. Els espais vectorials euclidians

ConceptesProcediments

1. El Determinant
2. Canvis de Base
3. Ortogonalització.
4. Rotacions. Matrius ortogonals.

- Càlcul de determinants.
- Canvis de base.
- El mètode de Gram-Schmidt.

Bloc de contingut 4. Diagonalització

ConceptesProcediments

1. Aplicacions lineals
2. Valors i vectors propis
2. Diagonalització
3. Matrius simètriques.

- El nucli i la imatge d’una aplicació lineal A
- El polinomi característic.
- Càlcul de valors i vectors propis
- Procediment de diagonalització

Bloc de contingut 5. Elements de teoria de grafs

ConceptesProcediments

1. Grafs.
2. Isomorfisme de grafs. Subgrafs. Grafs complets. Grafs bipartits.
3. El principi de les mans encaixades.
4. Grafs planars. Teorema de Euler
5 Eines bàsiques per al contatge

- Estratègies d’utilització de caracterització, propietats i igualtats sobre grafs per deduir-ne altres propietats.
- Demostracions.

Bloc de contingut 6. Arbres i grafs dirigits acíclics

ConceptesProcediments

1. Definicions i resultats bàsics. Caracteritzacions. Arbres amb arrel.
2. Cerques en profunditat y en extensió.
3. Arbres generadors. Arbres generadors de cost mínim.
4. Grafs dirigits acíclics

- Caracteritzacions.
- Algorismes de cerques en profunditat i en extensió
- Algorismes de Kruskal i de Prim.

Bloc de contingut 7. Camins i altres propietats dels grafs

ConceptesProcediments

1. Camins, connexitat. camins de cost mínim.
2. Coloració de grafs. Conjunts independents. Recobriments. Camins i cicles hamiltonians.

- Algorisme de Dijkstra.

Bloc de contingut 8. Optimització de Flux en xarxes

ConceptesProcediments

1. Xarxes de transport i comunicacions.
2. Optimització de Fluxos en Xarxes.
3 Teorema del flux maxim-tall mínim
4. Emparellaments en grafs bipartits

- Algorisme de Ford i Fulkerson
- Algorisme per a trobar un emparellament màxim

Bloc de contingut 9. Comptatge

ConceptesProcediments

1. Eines bàsiques de comptatge

- Inducció

- Reducció a l'absurd

 

Metodologia

A primer curs dels graus tenim dos grups de teoria. En alguns casos, depenent del número d’alumnes matriculat, es pot desdoblar algun grup de teoria, de manera que es realitzen de manera paral—lela dos subgrups d’un mateix grup (p.e. els subgrups 1A i 1B per al grup 1). Cada grup de teoria es divideix en 3 grups de pràctiques i, al seu torn, cada grup de pràctiques es divideix en dos seminaris. El fet de diferenciar entre tres tipus de sessions diferents ens permetrà potenciar i avaluar les diverses competències que pretenem que assoleixin al llarg de l’assignatura. En això cal emfatitzar en el fet que les sessions de seminaris afavoreixen fortament l’assoliment de competències transversals.

 

Sessions plenàries:

Es tracta de divuit sessions de dues hores de duració on assisteix tot el grup. El pes de la sessió el porta el professor que es dedicarà a explicar en pissarra els conceptes teòrics de l'assignatura per poder-los aplicar desprès a la pràctica. El professor s'encarregarà de proposar i resoldre exemples de problemes tipus per tal de clarificar la teoria i per tal que els estudiants tinguin una primera aproximació a allò que es trobaran a la classe de problemes.

Eix I: Àlgebra lineal
· Sessió 1: Presentació de l'assignatura. Nombres complexes.

· Sessions 2 i 3: Geometria dels sistemes d’equacions lineals. Resolució de sistemes d'equacions lineals, Mètode de Gauss. 

·Sessió 4. Vectors Matrius i determinants

· Sessió 5: Els espais vectorials i els seus subespais. Independència lineal. Bases.

· Sessió 6: Canvis de base. Els quatre subespais fonamentals.

· Sessió 7: Espais vectorials Euclidians. Ortogonalització. El mètode de Gram-Schmidt. Matrius ortogonals, rotacions.

· Sessió 8: Aplicacions lineals.

· Sessió 9: Valors i vectors propis. Diagonalització. Matrius simètriques

Eix II: Matemàtica Discreta

Sesssions de problemes:

A l’eix d’Àlgebra Lineal són sis sessions de dues hores de duració amb trenta estudiants en les quals el professor de pràctiques proposa una sèrie de problemes a realitzar d'una col·lecció que els estudiants tindran prèviament i deuen haver preparat. La dinàmica general d'aquestes sessions és la següent: En primer lloc, el professor realitza un exercici típic per tal de recordar els conceptes teòrics que s'apliquen i donar un mètode de resolució a seguir.

A l’eix de matemàtica discreta són dotze sessions de d’una hora de duració amb trenta estudiants en les quals el professor de pràctiques proposa una sèrie de problemes a realitzar d'una col·lecció que els estudiants tindran prèviament i deuen haver preparat. La dinàmica general d'aquestes sessions és la següent: En primer lloc, el professor realitza un exercici típic per tal de recordar els conceptes teòrics que s'apliquen i donar un mètode de resolució a seguir.

Sessions de seminaris:

A l’eix d’Àlgebra Lineal són 4 sessions de dues hores de duració en petit grup, d’uns quinze estudiants. En aquestes sessions es realitzen diferents tipus d'activitats guiades pel professor de seminari. Es proposaran exercicis amb anterioritat, que els alumnes hauran de preparar per a la sessió. En començar la sessió els mostraran als professors responsables de la sessió i treballaran a la sessió sobre la resolució d’aquests exercicis o d’altres que derivin d’aquests. No es pot participar a la sessió si no s’han preparat els exercicis proposats per a la sessió. Els estudiants poden participar a la pissarra per tal d'explicar els seus companys la seva resolució.  

A l’eix de matemàtica discreta són 8 sessions d’una hora de duració en petit grup, d’uns quinze estudiants. En aquestes sessions es realitzen diferents tipus d'activitats guiades pel professor de seminari. Es proposaran exercicis amb anterioritat, que els alumnes hauran de preparar per a la sessió. En començar la sessió els mostraran als professors responsables de la sessió i treballaran a la sessió sobre la resolució d’aquests exercicis o d’altres que derivin d’aquests. No es pot participar a la sessió si no s’han preparat els exercicis proposats per a la sessió. Els estudiants poden participar a la pissarra per tal d'explicar els seus companys la seva resolució.  

Sesssions no presencials:

Les sessions presencials només representen una part relativament petita del que representa les hores que l’estudiant ha de dedicar a l’assignatura. Cal afegir doncs a aquestes, les sessions no presencials, que l’estudiant ha d’aprofitar per copsar els coneixements de les sessions plenàries, realitzar exercicis i problemes i aquelles activitats requerides per a les sessions pels professors de l’assignatura. S'ha habilitat la plataforma Piazza per a fomentar la participació i discussió entre els alumnes.

 

Recursos

Bibliografia bàsica (suport paper i electrònic)

. D. LAY, Álgebra Lineal y sus aplicaciones, Pearson.
· K.H. ROSEN, Discrete Mathematics and its Applications
· J.KLEINBERG, E. TARDOS, Algorithm Design, Addison Wensley 2005.


Bibliografia complementària (suport paper i electrònic)
· M. CASTELLET i I. LLERENA, Àlgebra Lineal i Geometria, Manuals dela UAB, 1990.
· F.R. GANTMACHER, Théorie des Matrices,Editions J. Gabay, 1990.
· P. HALMOS, Finite-Dimensional Vector Spaces,Springer Verlag.
· AUBANELL, A. BENSENY i A. DELSHAMS, Útiles Básicos de Cálculo Numérico, Ed. Labor, 1993.
· W. K. NICHOLSON, Algebra Lineal con aplicaciones, Mc Graw Hill, 2003.
· J.M. BASART i MUÑOZ, Grafs: Fonaments i Algorismes,Manuals de la UAB, 13, 1994.
· N.L. BIGGS, Discrete Mathematics
· M. BRUNAT BLAY, Combinatoria i Teoria de Grafs,Edicions de la UPC.
· J. GIMBERT, R. MORENO, J.M. RIBÓ i M. VALLS, Apropament a la Teoria de Grafs i als seus Algorismes, EINES 23, 1998.
· TUCKER, Applied Combinatorics, Wiley, 1995.
G. STRANG, Linear Algebra and its Applications, Harcourt Brace Jovanovich International Edition, 1986. (també: http://ocw.mit.edu/courses/mathematics/18-06-linear-algebra-spring-2005/ )

· G. STRANG, 18.06 Linear Algebra Course, MIT Open Courseware, http://ocw.mit.edu/courses/mathematics/18-06-linear-algebra-spring-2005/index.htm

· I.V. PROSKURIAKOV, 2000 Problemas de Álgebra Lineal, Ed. Reverté, 1991.
· J.R. EVANS, E. MINIEKA, Optimization Algorithms for Networks and Graphs, Marcel Dekker, 1992.
· R. BHARATH, Computers and Graph Theory,Ellis Horwood, 1991
· J. FÀBREGA, Teoria de Grafs,Edicions de la UPC, 1997.
· J.A. BONDY, U.S.R. MURTY, Graph Theory with Applications (http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html

 

Recursos didàctics. Material docent de l’assignatura
· Per a cada sessió de problemes (pràctiques i seminaris) hi haurà una col·lecció de problemes que el professor lliurarà l’alumne a través de l’Aula Global abans de la realització de la sessió.