Kombinatorisk Optimering og Lineær Algebra

- en vei innen Master studiet i Matematikk eller Computational Science

Likte du lineær algebra? La oss anta at svaret er "ja"!

Du kan mye om lineære likninger Ax=b. Men hva med lineære ulikheter der hver likning erstattes av tilsvarende ulikhet?

Ofte er vi bare interessert i å finne en ikkenegativ løsning av Ax=b. Hvordan kan vi gjøre det? Og hva hvis vi vil ha en heltallig løsning?

Ofte vil vi også at løsningen skal være optimal: den skal minimere en viss funksjon f(x). Hvordan løser vi slike problemer?

I geometri har du sett punktmenger i planet og rommet som trekanter, kuber, pyramider etc. , alle er eksempler på polyedre. Men det er også polyedre i n-rommet. Så hva er det?

Grafteori er den viktig del av matematikken. En graf kan tegnes i planet som et visst antall punkter der visse par av punkter er forbundet med en linje. Mange viktige problemer kan oppfattes som optimering i grafer. Hva slags problemer?

..... jo, f.eks. (i) korteste vei i et veinettverk evt. datanettverk, (ii) billigste flyrute, (iii) klassifisering i billedanalyse (medisinske bilder, satelittbilder), (iv) ulike dynamiske beslutningsproblemer i økonomi, (v) enkelte geometriske approksimasjonsproblemer, etc.

Å forstå/løse et optimeringsproblem handler mye om å forstå den matematiske strukturen ved nettopp det problemet. Her er det mange analyseutfordringer knyttet til spesielle problemklasser. Gjerne motivert av anvendelser.

Her kan du bli en matematisk problemløser! Og lære å løse problemer med anvendelser innen mange områder av vårt moderne samfunn.

Masteroppgaven tilpasses din bakgrunn og interesser. Spennvidde fra anvendte oppgaver med algoritmer/programmering over til teoretiske oppgaver f.eks. innen kombinatorisk matriseteori eller studiet av klasser av polyedre.

Studiets oppbygging:

Studiet baseres på bachelor studiet MIT Matematikk, informatikk og teknologi med retning Matematikk eller Computational Science. For generelle opptakskrav til Master studiet i Matematikk se ...(peker)..., og for Master studiet i Computational Science se ...(peker).... En mulig studieplan i Kombinatorisk Optimering og Lineær Algebra innen matematikk kan f.eks. se slik ut

Master delen:

10. semester Hovedoppgave

9. semester Fritt valgt emne Hovedoppgave

8. semester Spesialpensum (Kombinatorisk matriseteori, Konveksitet, Grafteori eller Optimering) Fritt valgt emne Hovedoppgave

7. semester INF-MAT 5360: Matematisk optimering INF-MAT 3350/4350: Numerisk lineær algebra MAT 4500: Topologi

10 studiepoeng 10 studiepoeng 10 studiepoeng

Bachelor delen med retning Matematikk i MIT ser da slik ut:

6. semester MAT2200: Grupper, ringer og kropper MAT2000: Prosjektarbeid i matematikk Fritt valgt emne

5. semester MAT2300: Analyse 2 Fritt valgt emne Ex.phil

4. semester MAT1300: Analyse 1 INF-MAT 3370/4370 Lineær optimering INF-MAT 2350: Numeriske beregninger

3. semester MAT1120: Lineær algebra STK1110: Statistiske metoder og dataanalyse 1 Fritt valgt emne

2. semester MAT1110: Kalkulus og lineær algebra STK1100: Sannsynlighetsregning og statistisk modellering INF1010: Objektorientert programmering

1. semester MAT1100: Kalkulus MAT-INF1100: Modellering og beregninger INF1000: Grunnkurs i objektorientert programmering

10 studiepoeng 10 studiepoeng 10 studiepoeng

For denne studieveien er kursene INF-MAT 3370 Lineær optimering og INF-MAT 4... Matematisk optimering obligatoriske. I tillegg anbefales sterkt INF-MAT 3350 Numerisk lineær algebra.

Diskrete metoder: ved å kombinere opplegget over med matematisk logikk (MAT 3600 Matematisk logikk), algoritmeanalyse (INF 1020 Algoritmer og datastrukturer, INF 3200 Algoritmer og effektivitet) eller kryptografi/algebra får man en bred bakgrunn i diskrete metoder. Det grunnleggende emnet MAT 1030 Diskret matematikk kan også være nyttig her.

Kontinuerlige metoder: For de som vil ha fokus på beregninger i kontinuerlige problemer, f.eks. geometrisk modellering anbefales INF-MAT 2350 Numeriske beregninger, INF 1020 Algoritmer og datastrukturer, INF 3320 Metoder i grafisk databehandling og diskret geometri, INF-MAT 4... Splines.

Veiledning:

Veileder i denne studieveien er Geir Dahl. Ta kontakt hvis du har spørsmål!. På veileders nettside kan du lese mer om Kombinatorisk Optimering og Lineær Algebra og du finner også informasjon om forskningaktivitet her.