Kursusnavn: Diskret matematik og introducerende algebra

Forkortelse: Dis&Alg 1

Kursusdesignere: Gunnar Forst, Anders Thorup

Størrelse: 7,5 ECTS

Placering: 1. år, blok 3A

Udbydes: Hvert år

Kompetencebeskrivelse: Den studerende skal kunne argumentere logisk og løse problemer

Emner:

Introduktion til grafteori.

---------------------------

1. Grundbegreber: vej i graf, sammenhængende graf, komponenter af graf,

kreds i graf, valens, isomorfi, komplette grafer, bipartite grafer og

deres karakterisering (paritetsargument mm.)

2. Træer, optælling af (labeled) træer (Cayleys formel), fx via

Prüfer-koder

3. Karakterisering af Euler-grafer og grafer med semi-Euler-tur.

Tilstrækkelig betingelse for eksistens af Hamilton-kreds i graf

4. Farvning: af kanter (Königs sætning, Vizings sætning), eller knuder

(nævne Brooks' sætning, knude-kromatisk polynomium, med

beregningsalgoritme)

Elementær kombinatorik.

-----------------------

1. Abstrakte tælleprincipper (spredt ud, og især eksemplificerede!):

bijektiv korrespondance, disjunkt forening, uafhængig parring,

skuffeprincip, paritetsargumenter, optælling ved inklusion/eksklusion

(og fx optælling af surjektive afbildninger)

2. Rekursion: løsning af simple differensligninger, lidt abstrakt

notation (differensoperator, fakultetsfunktion og dalende/stigendede

faktorieler, beskrivelse af ``løsningsrum'')

3. Tælle-tal: binomialkoefficienter, multinomialkoefficienter,

Stirling-tal, partitions-tal, Catalan-tal (og masser af eksempler på

tællesituationer, hvor de dukker op)

4. Tælleproblemer i forbindelse med permutationer: type-statistik, antal

derangements (perm. uden fikspunkter), tårnpolynomier

Om tallene.

-----------

1. Regnereglerne: komposition af tal (kommutativ lov etc.), ordning af tal

(reflexiv etc.), numerisk værdi, nul-reglen

2. Naturlige tal: induktion, fuldstændig induktion, primopløsning

3. Hele tal: division med rest, Euklids algoritme, primtal,

aritmetikkens fundamentalsætning

4. Rationale tal: uforkortelig brøk, fælles nævner

5. Reelle og komplekse tal: modulus og konjugering, geometrisk model,

komplekse enheder

6. Restklasser og kongruens: primisk restklasse, den kinesiske

restklassesætning

Elementær gruppeteori.

----------------------

1. Gruppebegrebet: gruppe og undergruppe, grupper af tal,

restklassegrupper, enhedsrødder, transformationsgrupper, GL_n,

SL_n, O_n, dieder- og kvaterniongruppe

2. Permutationer: cykelfremstilling, transposition, fortegn, S_n og A_n

3. Cykliske grupper: potensregler, cyklisk gruppe, elementorden

4. Sideklasser: Lagrange's Indexsætning, Euler's sætning (Fermat's

lille)

Lærebøger:gunnar Forst vil muligvis skrive noter til den diskrete matematik.

Anders Thorups noter til Mat2 AL kan bruges til gruppeteorien

Forudsætninger: An1, LinAlg, MatE

Undervisningsform: Forelæsninger og øvelser.

Evalueringsform:

Et antal ``uformelle prøver'' afholdt indenfor

den skemalagte undervisningstid (denne form er afprøvet med success på

MatXX); disse kunne fx lægges i slutningen af ugerne 3,5,7, og 9, og

skulle være obligatoriske; Der gives karakter. Såfremt formalia kan bringes på plads kan der medvirke ekstern censor.