Aktuella teman och algoritmer inom kombinatorik, 7,5 hp

Innehåll

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, solrosor, antikedjor, 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
• 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  (Sperners sats, Erdős--Ko--Rados sats, Erdős--Rados solroslemma, Turáns sats)
• redogöra ingående för Moser-Tardos algoritm och dess egenskaper
• 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 Turáns sats, Sperners sats, Erdős--Ko--Rados sats och 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.