Kursen behandlar aktuella teoretiska och algoritmiska resultat i kombinatorik. Den inleds med en översikt över klassiska probabilistiska metoder, som första- och andramomentsmetoden och lokala lemmat, och andra grundläggande begrepp och resultat i extremal kombinatorik, som mängdsystem, grafpartitioner och Turánproblem. Kursen går sedan vidare med en fördjupad behandling av följande teman från forskningsfronten:
Moser-Tardos algoritm och derandomisering av probabilistiska algoritmer i allmänhet
samtida skärpningar av solroslemmat och deras tillämpningar inom datavetenskap och slumpgrafer
metoden med hypergrafcontainrar och dess tillämpningar
Vapnik-Chervonenkisdimension och dess tillämpningar inom statistisk inlärning och komputationell geometri
Förväntade studieresultat
För godkänd kurs ska den studerande kunna
Kunskap och förståelse
redogöra ingående för den probabilistiska metoden i kombinatorik
formulera och bevisa klassiska satser i extremal kombinatorik
redogöra ingående för Moser-Tardos algoritm och dess egenskaper
formulera Ahlweiss-Lowett-Wu-Zhangs olikhet för solroslemmat och ge en detaljerad skiss av beviset
beskriva en containeralgoritm och ge en detaljerad skiss av ett bevis för en sats med hypergraf containrar
ge en rigorös definition av Vapnik-Chervonenkisdimension, och formulera och bevisa Sauer-Shelahs lemma
Färdighet och förmåga
tillämpa klassiska probabilistiska metoder för att lösa kombinatorikproblem
tillämpa solroslemmat på problem inom kombinatorik och datavetenskap
tillämpa metoden med hypergrafcontainrar på kombinatoriska problem
tillämpa Vapnik-Chervonenkisteori och Sauer-Shelahs lemma på problem inom kombinatorik och diskret geometri
självständigt lösa avancerade problem inom kombinatorik
Värderingsförmåga och förhållningssätt
genomföra matematiskt stringenta resonemang inom probabilistik och kombinatorik
kritiskt tillämpa resultat och metoder inom extremal och probabilistisk kombinatorik på typiska problem inom området
Behörighetskrav
För tillträde till kursen krävs 90 hp i matematik eller datavetenskap, varav minst 60 hp i matematik inkluderande en kurs i diskret matematik omfattande minst 7,5 hp och en kurs i statistik omfattande minst 7,5 hp som inkluderar grundläggande sannolikhetslära. Engelska 5/A och svenska för grundläggande behörighet för högskolestudier (om kursen ges på svenska).
Undervisningens upplägg
Undervisningen bedrivs i form av föreläsningar och lektioner.
Examination
Kunskapsredovisningen sker i form av en skriftlig inlämningsuppgift och ett skriftlig prov. På båda delarna ges något av omdömena Underkänd (U), Godkänd (G) eller Väl godkänd (VG). På hela kursen ges något av betygen Underkänd (U), Godkänd (G) eller Väl godkänd (VG). För att bli godkänd på hela kursen krävs att samtliga examinerande delar är godkända. För att få betyget Väl godkänd (VG) måste man har fått omdömet Väl Godkänt (VG) på samtliga examinerande delarna.
Avsteg från kursplanens examinationsform kan göras för en student som har beslut om pedagogiskt stöd på grund av funktionsnedsättning. Individuell anpassning av examinationsformen ska övervägas utifrån studentens behov. Examinationsformen anpassas inom ramen för kursplanens förväntade studieresultat. Efter begäran av studenten ska kursansvarig lärare, i samråd med examinator, skyndsamt besluta om anpassad examinationsform. Beslutet ska sedan meddelas studenten.
Den som erhållit betyget godkänt på kursen kan ej examineras för högre betyg. För studerande som inte blivit godkänd vid ordinarie provtillfälle anordnas ytterligare provtillfälle. En student som utan godkänt resultat har genomgått två prov för en kurs eller en del av en kurs, har rätt att få en annan examinator utsedd, om inte särskilda skäl talar emot det (HF 6 kap. 22 §). Begäran om ny examinator ställs till prefekten vid Institutionen för matematik och matematisk statistik. Examination baserad på denna kursplan garanteras under två år efter studentens förstagångsregistrering på kursen.
Tillgodoräknande Student har rätt att få prövat om tidigare utbildning eller motsvarande kunskaper och färdigheter förvärvade i yrkesverksamhet kan tillgodoräknas för motsvarande utbildning vid Umeå universitet. Ansökan om tillgodoräknande skickas in till Studentcentrum/Examina. Mer information om tillgodoräknande finns på Umeå universitets studentwebb, www.student.umu.se, och i högskoleförordningen (6 kap). Ett avslag på ansökan om tillgodoräknande kan överklagas (Högskoleförordningen 12 kap) till Överklagandenämnden för högskolan. Detta gäller såväl om hela som delar av ansökan om tillgodoräknande avslås.
Övriga föreskrifter
I en examen får denna kurs ej ingå tillsammans med en annan kurs med likartat innehåll. Vid osäkerhet bör den studerande rådfråga studierektor i matematik och matematisk statistik.
