Kursens mål

Länk till officiell kursplan

Denna kurs i kombinatorik är upplagd som en fortsättningskurs till SF1631 Diskret matematik och ska ge ökad förtrogenhet med grundläggande kombinatoriska resonemang, metoder och teorier. Kursen ligger till grund för såväl fortsatta studier i kombinatorik som tillämpningar inom närliggande discipliner, i synnerhet datalogi. Förmågan att resonera kombinatoriskt är av vital betydelse i teoretisk datalogi och kommer även till användning inom andra teoretiskt krävande inriktningar på datateknikprogrammet, exempelvis beräkningsteknik och programsystemteknik.

Efter kursen ska studenten kunna:

• konstruera kombinatoriska bevis för algebraiska identiteter och olikheter.
• 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.
• beskriva och härleda egenskaper hos kombinatoriska standardobjekt (till exempel permutationer och partitioner) och vanligt förekommande kombinatoriska talföljder (till exempel Belltalen och Catalantalen).
• använda RSK-algoritmen för att härleda egenskaper hos permutationer och tablåer.
• använda klassiska algoritmer på en given graf för att finna delgrafer med lämpliga egenskaper.
• bestämma maximala flöden i nätverk, redogöra för kopplingen till satser av Menger, König och Hall samt tolka vissa problem i termer av nätverksflöden.
• beräkna och härleda egenskaper hos kromatiska tal och polynom samt tolka vissa problem i termer av graffärgning.
• använda satser av Euler, Kuratowski-Wagner och Appel-Haken för att härleda egenskaper hos planära och icke-planära grafer.
• tolka vissa räkneproblem i termer av enumeration under gruppverkan samt använda Burnsides lemma och Pólyateori för att lösa problemen.
• 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.

Rekommenderade förkunskaper

SF1631 Diskret matematik (eller motsvarande).