SF2715 Tillämpad kombinatorik 6,0 hp

Kombinatoriska objekt, kombinatoriska bevis, formella potensserier, rekursioner, genererande funktioner, RSK-algoritmen, enumeration under gruppverkan, elementär graf- och nätverksteori, graffärgningsteori, topologisk grafteori, felrättande koder.

Efter genomgången kurs ska studenten vara förtrogen med grundläggande kombinatoriska metoder och teorier vilka ligger till grund för såväl fortsatta studier inom området som tillämpningar inom närliggande discipliner, i synnerhet datalogi. Konkret innebär det att studenten ska

• Känna till diverse kombinatoriska standardobjekt och -talföljder som exempelvis permutationer, partitioner, Belltal, Catalantal, ...
• Utföra beräkningar med, och härleda egenskaper hos, formella potensserier
• Härleda rekursioner, genererande funktioner och explicita uttryck för kombinatoriskt definierade talföljder
• Uppställa kombinatoriska bevis för identiteter och olikheter
• Behärska RSK-algoritmen och kunna utnyttja den för att härleda egenskaper hos permutationer och tablåer
• Tolka vissa räkneproblem i termer av enumeration under gruppverkan samt använda Burnsides lemma och Pólyateori för att lösa dem
• Använda några klassiska grafalgoritmer för att finna delgrafer med lämpliga egenskaper
• Bestämma maximala flöden i nätverk och redogöra för hur denna metod hänger samman med satser av Menger, König och Hall samt lösa vissa problem genom att formulera dem i termer av nätverksflöden
• Beräkna, och härleda egenskaper hos, kromatiska tal och polynom samt identifiera vissa problem som graffärgningsproblem
• Använda satser av Euler, Kuratowski-Wagner och Appel-Haken för att härleda egenskaper hos (icke-)planära grafer
• Konstruera, utföra kalkyl med och härleda egenskaper hos vissa koder
• Bestämma, tolka och jämföra olika gränser för möjliga kodprestanda.

SF1631 Diskret matematik eller motsvarande.

Peter J. Cameron, "Combinatorics: Topics, Techniques, Algorithms", Cambridge University Press, 1994.

När kurs inte längre ges har student möjlighet att examineras under ytterligare två läsår.

Examinator beslutar, baserat på rekommendation från KTH:s handläggare av stöd till studenter med funktionsnedsättning, om eventuell anpassad examination för studenter med dokumenterad, varaktig funktionsnedsättning.

Examinator får medge annan examinationsform vid omexamination av enstaka studenter.

Skriftlig/muntlig tentamen, eventuellt med möjlighet till kontinuerlig examination.

• Vid grupparbete har alla i gruppen ansvar för gruppens arbete.
• Vid examination ska varje student ärligt redovisa hjälp som erhållits och källor som använts.
• Vid muntlig examination ska varje student kunna redogöra för hela uppgiften och hela lösningen.