Àlgebra Lineal i Matemàtica Discreta (21593)
Titulació/estudi: Grau en Enginyeria en Informàtica, Grau en Enginyeria en Sistemes Audiovisuals i Grau en Enginyeria Telemàtica
Curs: 1r.
Trimestre: 1r, 2n
Nombre de crèdits ECTS: 8 crèdits
Hores dedicació estudiant: 200 hores
Llengua o llengües de la docència: català i castellà
1. 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. 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, que estan basats en exercicis i problemes, on es pretén consolidar la comprensió dels conceptes i tècniques adquirides, complementant-los també amb algunes pràctiques amb ordinador.
Àlgebra Lineal i Matemàtica Discreta està dedicada a una introducció a l'Àlgebra Lineal així com a una introducció a la Teoria de Grafs i a optimització de fluxos en xarxes. Està estructurada en dos grans blocs. El primer 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 bloc està dedicat 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, entre elles les del bloc d'assignatures d'algorítmica, programació i estructures de dades. L'aprenentatge es planteja amb un enfocament pràctic, que inclou l'estudi de múltiples algoritmes de grafs i unes pràctiques amb ordinador.
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.
2. Competències a assolir
| Competències generals | Competè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 trobar-ne la solució. 3. Habilitat d'expressar idees i conceptes matemàtics de forma oral i escrita de manera precisa. 4. Capacitat d'abstracció 5. Capacitat de sistematització. Interpersonals 6. Capacitat de treball en equip tant resolent problemes plantejats com profunditzant en determinats continguts. 7. Capacitat de comunicar idees de forma precisa, tant de forma oral com escrita Sistèmiques 8. Capacitat per treballar autònomament en la resolució de problemes 9. Capacitat per aprendre dels errors propis i dels altres 10. Capacitat per cercar solucions més adequades segons les característiques de cada problema/situació/context 11. Capacitat per inferir nocions matemàtiques. |
Bloc I: Àlgebra lineal 1. Entendre l'àlgebra i la geometria bàsica dels nombres complexos. Bloc II: Teoria de Grafs i optimització en xarxes 11. Familiaritzar-se i entendre els elements de la Teoria de Grafs. |
3. Continguts
3.1. Blocs de contingut
L'assignatura està estructurada quatre blocs de continguts per al bloc o part d'Àlgebra Lineal i cinc blocs de contingut per a la part de Teoria de Grafs i Optimització en Xarxes:
Bloc 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ó
Bloc II: Teoria de grafs i optimització en xarxes
- Bloc de contingut 5. Elements de teoria de grafs.
- Bloc de contingut 6. Arbres.
- Bloc de contingut 7. Grafs Eulerians i Hamiltonians.
- Bloc de contingut 8. Camins i cicles de cost mínim.
- Bloc de contingut 9. Optimització de fluxos en xarxes.
3.2. Organització i concreció dels continguts
Bloc de contingut 1. Resolució de Sistemes d'equacions linials.
| Conceptes | Procediments |
|
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. 7. La descomposició LU |
- 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. - Mètode LU. - Càlcul de la matriu inversa. |
Bloc de contingut 2. Els espais vectorials i els seus subespais
| Conceptes | Procediments |
|
1. Els subespais vectorials 2. El nucli i la imatge d'una aplicació lineal A 3. Els quatre subespais fonamentals. 4. Independència lineal. Bases. Dimensió. |
- Càlcul dels quatre subespais fonamentals de A. |
Bloc de contingut 3. Els espais vectorials euclidians
| Conceptes | Procediments |
|
1. El Determinant 2. Canvis de Base 3. Ortogonalització. 4. Rotacions. Matrius ortogonals. |
- El polinomi característic - El mètode de Gram-Schmidt |
Bloc de contingut 4. Diagonalització
| Conceptes | Procediments |
|
1. Valors i vectors propis 2. Diagonalització 3. Matrius simètriques. |
- Càlcul de valors i vectors propis - Procediment de diagonalització |
Bloc de contingut 5. Elements de teoria de grafs
| Conceptes | Procediments |
|
1. Grafs i multigrafs. 2. Isomorfisme de grafs. Subgrafs. Grafs complets. Grafs bipartits. 3. El principi de les mans encaixades. 4. Grafs planars. Teorema de Euler. Teorema de Kuratowski. 5 Representació d'un graf en un ordinador. |
- Estratègies d'utilització de caracterització, propietats i igualtats sobre grafs per deduir-ne altres propietats. - El mètode del cercle-corda. - Demostracions per inducció. - Demostracions per reducció a l'absurd. |
Bloc de contingut 6. Arbres
| Conceptes | Procediments |
|
1. Definicions i resultats bàsics. Caracteritzacions. Arbres amb arrel. Arbres m-aris. Arbres equilibrats. 2. Cerques en arbres. Cerques en profunditat y en extensió. 3. Arbres generadors. Arbres generadors de cost mínim. |
- Caracteritzacions. - Algoritmes de cerques en profunditat i en extensió. - Algoritmes de Kruskal i de Prim. |
Bloc de contingut 7. Grafs Eulerians i Hamiltonians
| Conceptes | Procediments |
|
1. Circuits i recorreguts Eulerians. 2. Cicles i camins Hamiltonians. 3. El problema del viatjant de comerç. |
- Algoritme de Fleury per a l'obtenció d'un circuit Eulerià. - Algoritme de Robert i Flores per a l'obtenció d'un cicle Hamiltonià. - El mètode de Branch and Bound. . |
Bloc de contingut 8. Camins i Cicles de cost mínim
| Conceptes | Procediments |
|
1. Camins de cost mínim. 2. Coloració de grafs. 3. El problema de la vigilància d'una galeria d'art. |
- Algoritme de Dijkstra. - Algoritme de Floyd. - Obtenció de conjunts maximals de vèrtexs independents. Algoritme de Bron i Kerbosch. |
Bloc de contingut 9. Optimització de Fluxos en xarxes
| Conceptes | Procediments |
|
1. Els grafs a les xarxes de comunicacions. 2. Optimització de Fluxos en Xarxes. |
- Algoritmes d'optimitazió - Max Flow Min Cut. Algoritme de Ford i Fulkerson |
4. 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ó, tots ells obligatoris en l'avaluació continuada, són els que segueixen i estan estructurats en dos grans blocs, d'acord amb l'estructura d'aprenentatge de l'assignatura:
Bloc I: Àlgebra lineal
- Lliurament d'exercicis: es tracta de tres col·leccions de problemes, anàlegs als que es realitzen a les classes de pràctiques (de pissarra), que els estudiants hauran de lliurar en grups de fins a 3 persones.
- Controls de teoria: seran dos controls de preguntes curtes o de tipus test per tal de fer un seguiment dels conceptes explicats a les classes de teoria.
- Control de problemes (un): es farà al voltant de sisena setmana, amb exercicis de dificultat anàloga als de les col·leccions d'exercicis lliurats. Aprovar aquest control comporta eliminar matèria de cara a l'examen final tipus A.
Es considerarà aprovada l'avaluació continuada del Bloc d'Àlgebra Lineal si s'ha tret un mínim de 4 en cadascun dels tres punts anteriors (lliurament de problemes, controls de teoria i control de problemes). En cas contrari (si qualsevol de les tres notes anteriors es inferior a 4) es considera l'avaluació continuada del Bloc d'Àlgebra Lineal suspesa.
L'examen final 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 el bloc d'àlgebra lineal, i dependrà de si l'alumne ha aprovat o suspès l'avaluació continuada:
- Els alumnes que hagin aprovat l'avaluació continuada només hauran de fer un examen (tipus A) que comptarà un 35% de la nota, mentre que el lliurament de problemes comptarà un 20%, els controls de teoria un 20% i el control de problemes un 25%.
- Els alumnes amb l'avaluació continuada suspesa realitzaran un examen teòric i més llarg (tipus B, de dificultat superior al tipus A). Constarà de dues parts: un test de preguntes teòriques, que comptarà un 20% per la nota final del bloc d'àlgebra lineal, i un examen més llarg de problemes que comptarà un 80%.
Bloc II: Teoria de grafs i optimització en xarxes
Els mecanismes d'avaluació, tots ells obligatoris en l'avaluació continuada d'aquest bloc, són:
- Lliurament d'exercicis: es tracta de dues col·leccions de problemes, anàlegs als que es realitzen a les classes de pràctiques (de pissarra), que els estudiants hauran de lliurar en grups de fins a 3 persones.
- La realització de 4 pràctiques d'ordinador a les sessions de problemes que requeriran la realització d'un estudi previ. Els informes de les pràctiques s'hauran d'entregar al acabar la sessió corresponent. La nota de pràctiques quedarà ponderada pel nombre de pràctiques a les què s'assisteixi presencialment.
- Controls de teoria: seran dos controls on-line de preguntes curtes o de tipus test per tal de fer un seguiment dels conceptes explicats a les classes de teoria.
- Control de problemes (un): es farà al voltant de quinzena setmana, amb exercicis de dificultat anàloga als de les col·leccions d'exercicis lliurats.
Es considerarà aprovada l'avaluació continuada del Bloc de Grafs si s'ha tret un mínim de 4 en cadascun dels quatre punts anteriors (lliurament de problemes, pràctiques, controls on-line de teoria i control d'exercicis). En cas contrari (si qualsevol de les quatre notes anteriors es inferior a 4) es considera l'avaluació continuada del Bloc de Grafs suspesa.
L'examen final 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 el bloc de grafs, i dependrà de si l'alumne ha aprovat o suspès l'avaluació continuada:
- Els alumnes que hagin aprovat l'avaluació continuada només hauran de fer un examen (tipus A), focalitzat en la segona part del temari, que comptarà un 35% de la nota, mentre que el lliurament de problemes comptarà un 15%, les pràctiques un 15%, els controls on-line de teoria un 15% i el control de problemes un 20%.
- Els alumnes amb l'avaluació continuada suspesa realitzaran un únic examen (tipus B, de dificultat superior al tipus A). Constarà de dues parts: un test de preguntes teòriques, que comptarà un 20% per la nota final del bloc de teoria de grafs i optimització en xarxes, i un examen de problemes que comptarà un 80%.
La Nota Final de l'assignatura Àlgebra Lineal i Matemàtica Discreta s'obté fent la mitjana de:
- la nota del Bloc I d'àlgebra lineal, sempre que aquesta sigui major o igual a 4,
- la nota del Bloc II de grafs, sempre que aquesta sigui major o igual a 4
A més, es tenen en compte els següents criteris:
- Per aprovar l'assignatura s'ha de treure una Nota Final superior o igual a 5 (cinc).
- Al final del Bloc II de grafs hi haurà addicionalment un examen "de recuperació" del Bloc I d'àlgebra lineal.
-
En cas que es suspengui o no es presenti a l'examen de la convocatòria ordinària, l'alumne es podrà presentar a la convocatòria de setembre i se li guardaran les notes dels lliuraments que ha entregat durant el curs.
5. Bibliografia i recursos didàctics
5.1. Bibliografia bàsica
- G. STRANG, Linear Algebra and its Applications, Harcourt Brace Jovanovich International Edition, 1986.
- F. CEDO i V. GISIN, Àlgebra Bàsica, Manuals de la UAB, 1997.
- 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.
5.2. Bibliografia complementària
- M. CASTELLET i I. LLERENA, Àlgebra Lineal i Geometria, Manuals de la 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.
- M. BRUNAT BLAY, Combinatoria i Teoria de Grafs,Edicions de la UPC.
- X. FRANCH GUTIÉRREZ, Estructuras de Datos, Edicions UPC, 1994.
- 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.
5.3. Recursos didàctics
A cada sessió de teoria li correspondrà una material docent que el professor lliurarà l'alumne a través de l'Aula Global.
Per a cada sessió de problemes 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 pràctica.
6. Metodologia
A primer curs del grau tenim dos grups de teoria. Aquests grups de teoria es desdoblen en 3 grups de pràctiques i, al seu torn, cada grup de pràctiques es desdobla en dos seminaris de la meitat dels estudiants.
El fet de diferenciar entre tres tipus de sessions 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.
Bloc I: Àlgebra lineal
- Sessió 1 [T(1)]: Introducció a l'assignatura. Nombres complexes. Funcions.
- Sessió 2 [T(2)]: Vectors i matrius. Geometria dels sistemes d'equacions lineals.
- Sessió 3 [T(3)]: Resolució de sistemes d'equacions lineals, Mètode de Gauss.
- Sessió 4 [T(4)]: Resolució de sistemes d'equacions lineals. Descomposició LU. Càlcul de la matriu inversa.
- Sessió 5 [T(5)]: Els espais vectorials i els seus subespais. Els quatre subespais fonamentals. Independència lineal. Bases.
- Sessió 6 [T(6)]: Determinants. Canvis de base.
- Sessió 7 [T(7)]: Espais vectorials Euclidians. Ortogonalització. El mètode de Gram-Schmidt. Matrius ortogonals.
- Sessió 8 [T(8)]: Valors i vectors propis. Diagonalització.
-
Sessió 9 [T(9)]: Diagonalització. Matrius simètriques.
Bloc II: Teoria de grafs i optimització en xarxes
- Sessió 10 [T(10)]: Introducció. Grafs i subgrafs. Models de grafs.
- Sessió 11 [T(11)]: Grafs planaris i grafs duals. Representació de grafs en un ordinador.
- Sessió 12 [T(12)]: Arbres. Cerques.
- Sessió 13 [T(13)]: Arbres de cost mínim. Connectivitat.
- Sessió 14 [T(14)]: Grafs Eulerians. Grafs Hamiltomians.
- Sessió 15 [T(15)]: Camins i cicles de cost mínim.
- Sessió 16 [T(16)]: Recobriments i Coloració de grafs.
- Sessió 17 [T(17)]: Els grafs a les xarxes de comunicacions.
-
Sessió 18 [T(18)]: Optimització de Fluxos en Xarxes.
Sessions de problemes:
Són dotze sessions d'una hora i mitja (o 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. Desprès, en els problemes successius són els estudiants els que resolen els problemes i surten a la pissarra per tal d'explicar els seus companys com ho han fet. Tant els estudiants com el professor han de verificar que el problema ha estat ben resolt i poden proposar qüestions.
Bloc I: Àlgebra lineal
- Sessió 1 [P(1)]: Funcions, Vectors i matrius. Interpretació de les matrius com un cas particular d'aplicacions lineals.
- Sessió 2 [P(2)]: Descomposició LU. Càlcul de la matriu inversa.
- Sessió 3 [P(3)]: Càlcul dels quatre subespais fonamentals.
- Sessió 4 [P(4)]: Canvis de base.
- Sessió 5 [P(5)]: El mètode de Gram-Schmidt.
-
Sessió 6 [P(6)]: Exercicis de Valors i vectors propis i Diagonalització. Autoavaluació i co-avaluació
Bloc II: Teoria de grafs i optimització en xarxes
En aquest bloc algunes de les sessions es realitzaran amb l'ajut d'un ordinador. Per a la realització d'aquestes l'alumne haurà de realitzar un estudi previ abans de realitzar la sessió. Durant la sessió, l'alumne haurà de ser capaç d'analitzar els resultats obtinguts mitjançant les simulacions. Al finalitzar la sessió, l'alumne haurà d'entregar un informe al professor.
- Sessió 7 [P(7)]: Problemes de principi de les mans encaixades, d'isomorfismes en grafs i el mètode del cercle-corda.
- Sessió 8 [P(8)]. Pràctica d'ordinador sobre arbres i arbres generadors.
- Sessio 9 [P(9)]. Problemes sobre grafs Eulerians i Hamiltonians.
- Sessió 10 [P(10)]. Pràctica d'ordinador sobre camins i cicles de cost mínim.
- Sessió 11 [P(11)]. Pràctica d'ordinador sobre coloració de grafs.
-
Sessió 12 [P(12)]. Pràctica d'ordinador sobre optimització de flux en xarxes.
Sessions de seminaris:
Aquestes són vint sessions en petit grup, màxim quinze estudiants, d'una hora de duració. En aquestes sessions es realitzen diferents tipus d'activitats guiades pel professor que ha impartit les sessions plenàries.
Bloc I: Àlgebra lineal
- Sessió 1 [S(1)]: Números complexos, Funcions.
- Sessió 2 [S(2)]: Resolució de sistemes d'equacions lineals. Mètode de Gauss.
- Sessió 3 [S(3)]: Independència lineal y rang d'un sistema.
- Sessió 4 [S(4)]: Determinants.
- Sessió 5 [S(5)]: Ortonormalització.
- Sessió 6 [S(6)]: Matrius ortogonals, rotacions.
- Sessió 7 [S(7)]: Valors i vectors propis.
- Sessió 8 [S(8)]: Diagonalització.
- Sessió 9 [S(9)]: Matrius simètriques.
-
Sessió 10 [S(10)]: Repàs.
Bloc II: Teoria de grafs i optimització en xarxes
- Sessió 11 [S(11)]: Aplicacions, exemples pràctics i problemes resolts de forma conjunta de les sessions de teoria 10 i 11. Resolució de qüestions que plantegen els propis estudiants.
- Sessió 12 [S(12)]: Aplicacions, exemples pràctics i problemes resolts de forma conjunta del tema tema d'arbres, arbres generadors, i connectivitat...
- Sessió 13 [S(13)]: Aplicacions, exemples pràctics i problemes resolts del tema Eulerià i Hamiltonià.
- Sessió 14 [S(14)]: Aplicacions, exemples pràctics i problemes resolts del tema de camins i cicles de cost mínim. El Problema del Viatjant. Algorisme de Branch & Bound.
- Sessió 15 [S(15)]: Control de teoria.
- Sessió 16 [S(16)]: Aplicacions, exemples pràctics i problemes resolts de forma conjunta a la pissarra sobre coloració de grafs.
- Sessió 17 [S(17)]: Aplicacions, exemples pràctics i problemes resolts de la teoria de grafs a les xarxes de comunicacions.
- Sessió 18 [S(18)]: Aplicacions, exemples pràctics i problemes resolts de forma conjunta de la teoria d'optimització de fluxos en xarxes.
- Sessió 19 [S(19)]: Repàs general a tots els conceptes que s'han vist a classe. Resolució de qüestions que plantegen els propis estudiants.
-
Sessió 20 [S(20)]: Control de teoria.
7. Programació d'activitats
Els horaris de classe, i el detall sobre si cada sessió serà de teoria de pràctiques o seminaris es troba publicat a l'apartat "Calendari i Horaris" de la web de l'ESUP http://www.upf.edu/esup