MAT-1005 Diskret matematikk - 10 stp

Generell studiekompetanse eller realkompetanse + Matematikk R1 eller (S1+S2) og enten Matematikk (R1+R2) eller Fysikk (1+2) eller Kjemi (1+2) eller Biologi (1+2) eller Informasjonsteknologi( 1+2) eller Geologi (1+2) eller Teknologi og forskningslære (1+2).

Søknadskode 9336 - enkeltemner i realfag.

• Kunne lese og forstå matematiske argumenter og selv kunne skrive enkle bevis, herunder også induksjonsbeviser.
• Beherske matematikkens basale strukturer som mengder og funksjoner mellom disse.
• Kunne forstå betydningen av uendelige følger og summasjoner og spesielt beherske aritmetiske og geometriske følger.
• Beherske tallteoretiske algoritmer som Euklids algoritme og rask eksponentiering, og også forstå viktigheten i disse for offentlig nøkkel kryptering.
• Kjenne til offentlig nøkkel krypteringsmetoden RSA.
• Beherske basale kombinatoriske telleteknikker som produkt- og summeregel og ha god forståelse av når disse kan brukes.
• Anvende dueslagsprinippet for å løse oppgaver i en rekke sammenhenger.
• Kunne bruke rekursjonsligninger til å løse avanserte telleproblemer.
• Kunne bruke inklusjons-eksklusjons prinsippet i konkrete oppgaver.
• Kjenne til hvordan diskrete strukturer som mengder, permutasjoner, relasjoner, matriser, grafer, trær og endelige tilstandsmaskiner brukes til modellering.
• Kjenne til begreper og problemer som korteste veg på grafer, utspenningstrær og fargetall for grafer.
• Kunne besvare hvorvidt en gitt graf har Euler eller Hamilton sti og veg.
• Beherske Huffmankoding til å finne effektiv koding av alfabeter.
• Beherske Dijkstras algoritme for å finne korteste veg på vektede grafer og Prims og Kruskals algoritme for å finne minimale utspenningstrær.
• Beherske boolsk algebra og kunne designe enkle boolske funksjoner med gitt output til bruk i elektroniske kretser.
• Beherske Karnaugh map og Quine-McCluskeys metode for minimalisering av kretser.
• Forstå hvordan endelige tilstandsmaskiner kan brukes til språkgjenkjenning.

En skriftlig eksamen av 4 timers varighet som teller 100 %.

Karakterskala: Bokstavkarakterer A-F.

Kontinuasjonseksamen:
Studenter som ikke har bestått siste ordinære eksamen tilbys kontinuasjonseksamen tidlig i påfølgende semester, dersom emnet inngår som obligatorisk i studieprogrammet.

Utsatt eksamen:
Studenter med gyldig forfall tilbys utsatt eksamen tidlig i påfølgende semester.

Arbeidskrav: Obligatoriske øvelser kreves godkjent for adgang til å avlegge eksamen.

Eksamensdato er foreløpig og vil kunne bli endret. Endelig eksamensdato kunngjøres ved oppslag på det enkelte fakultet primo mai for vårsemesteret og primo november for høstsemesteret.

Pensumliste for MAT-1005 Diskret matematikk 1, høsten 2015
UiT Norges arktiske universistet, Institutt for matematikk og statistikk

Lærebok: Kenneth H. Rosen, "Discrete Mathematics and its Applications", 7th ed.
(Global Edition, ISBN 0071315012, www.mhhe.com/rosenGE).

Fra kapittel 1, The Foundations: Logic, and Proofs
1.1 Propositional Logic
1.2 Applications of Propositional Logic
1.3 Propositional Equivalences

Fra kapittel 2, Basic Structures: Sets, Functions, Sequences, Sums, and Matrices
2.1 Sets
2.2 Set Operations
2.3 Functions
2.4 Sequences and Summations

Fra kapittel 3, Algorithms
3.1 Algorithms

Fra kapittel 4, Number Theory and Cryptography
4.1 Divisbility and Modular Arithmetic
4.2 Integer Representations and Algorithms
4.3 Primes and Greatest Common Divisors
4.4 Solving Congruences
4.5 Applications of Congruences
4.6 Cryptography

Fra kapittel 5, Induction and Recursion
5.1 Mathematical Induction (unntatt s. 319-325)

Fra kapittel 6, Counting
6.1 The Basics of Counting
6.2 The Pigeonhole Principle
6.3 Permutations and Combinatorics
6.4 Binomial Coefficients and Identities (unntatt s. 408-409)

Fra kapittel 7, Discrete Probability
7.1 An Introduction to Discrete Probability

Fra kapittel 8, Advanced Counting Techniques
8.1 Applications of Recurrence Relations
8.2 Solving Linear Recurrence Relations (bare homogene) (unntatt s. 502-508)
8.5 Inclusion-Exclusion

Fra kapittel 9, Relations
9.1 Relations and Their Properties
9.3 Representing Relations
9.5 Equivalence Relations

Fra kapittel 10, Graphs
10.1 Graphs and Graph Models
10.2 Graph Terminology and Special Types of Graphs
10.3 Representing Graphs and Graph Isomorphism
10.4 Connectivity (unntatt s. 659-663)
10.5 Euler and Hamilton Paths (unntatt s. 674-676)
10.6 Shortest-Path Problems
10.8 Graph Coloring

Fra kapittel 11, Trees
11.1 Introduction to Trees
11.2 Applications of Trees, bare s. 726-733
11.4 Spanning Trees (unntatt s. 759-763)
11.5 Minimum Spanning Trees

Fra kapittel Boolean Algebra
(tilgjengelig på nettet)
1 Boolean Functions
2 Representing Boolean Functions
3 Logic Gates
4 Minimization of Circuits

Fra kapittel Modeling Computation
(tilgjengelig på nettet)
1 Languages and Grammars
3 Finite-State Machines with No Output
4 Language Recognition (unntatt "More Powerful Types of Machines")

Tillatte hjelpemidler til eksamen:
Rottmanns tabeller.
Godkjente statistiske tabeller.
To A4-ark (4 sider) med egne notater.
Godkjent kalkulator.