| TATA12 |
Kombinatorikens grunder, 5 p
/Enumerative Combinatorics/ |
||
OBS! |
Vartannatårskurs. Ges 2005 |
||
Prel. schemalagd
tid: |
|||
|
Utbildningsområde: Naturvetenskap Ämnesgrupp: Matematik Nivå (A-D):D |
|||
| Datavetenskap Matematik, diskret matematik |
|||
|
Mål:
Ge förtrogenhet med kombinatorikens grundläggande metoder och kunna tillämpa dem på nya progblem. Att se strukturen i kombinatoriska lösningar där den oinsatte bara ser snygga tricks. |
|||
| Förkunskaper: (gäller studerande antagna till program som kursen ges inom, se 'För:' ovan) Linjär algebra. Det underlättar om man har läst Diskret Matematik TATA35 eller motsvarande. OBS! Tillträdeskrav för icke programstudenter omfattar vanligen också tillträdeskrav för programmet och ev. tröskelkrav för progression inom programmet, eller motsvarande. |
|||
| Organisation: Föreläsningar och seminarier. |
|||
| Kursinnehåll: Kursen inleds med en strukturerad genomgÃ¥ng av de grundläggande kombinatoriska metoderna för enumerativa heltalsproblem. Förutom de 12 "basfallen" inkluderar detta metoder sÃ¥som inklusion-exklusion, Tornpolynom och determinantmetoden (Lindströms Lemma) som är nÃ¥gra av de vanligaste verktygen. Kursen innehÃ¥ller ocksÃ¥ teori om listors omordningar (permutationsteori) med bl.a. den fundamentala transformationen, inversioner, mönsterundvikande permuationer, permutationsstatistik, descentklasser, fixpunktsfriapermutationer m.m Kursen behandlar sedan grundläggande teori om partialordnade mängder, lattice och incidence algebran över sÃ¥dana. Möbius inversionsformel för godtyckliga pomängder (generaliserar bÃ¥de Inkl-Exkl. och Möbiusinv. i talteorin). Ã"ven samband mellan Möbiusfunktionen och topologisk kombinatorik sÃ¥som hyperplansarrangemang och beräknandet av t.ex. undre gränser för sorteringsalgoritmers komplexitet. Kursen avslutas med att alla deltagarna hÃ¥ller föredrag om nÃ¥got ytterligare ämne frÃ¥n kombinatoriken. |
|||
| Kurslitteratur: "Enumerative Combinatorics Vol. 1", av Richard P. Stanley, Cambridge University Press. Utdelat material under kursens gång. |
|||
| Examination: | |||
| UPG1 UPG2 |
Inlämningsuppgifter (U,3,4,5) Muntlig presentation (U,G) |
4 p 1 p |
|
Undervisningsspråk är Svenska.
Institution: MAI.
Studierektor: Arne Enquist
Examinator:
Ansvarig utbildningsnämnd: UND
Engelsk kursplan
Om inget annat anges ovan gäller betygsskala enligt avsnitt a8.5 i de gemensamma bestämmelserna.
Kursplanen gäller för 2005 enligt beslut av ansvarig utbildningsnämnd.
 |
||||||
| ||||||