høst
2013
MAT-1005 Diskret matematikk - 10 stp
Innhold
Kurset er et introduksjonskurs i matematikk som spesielt dekker matematiske strukturer som har anvendelser i informatikk. Det gis en introduksjon til fundamentale begreper i matematikk som mengder og funksjoner og inkluderer logikk og ulike bevisteknikker. Andre emner som vektlegges er kombinatorikk med sannsynlighetsregning og grafteori. Det gis en innføring i bruk av Mathematica som numerisk, symbolsk og grafisk verktøy, og for enkel programmering.Hva lærer du
Emnet er en introduksjon i matematikken som spesielt dekker diskrete matematiske strukturer som har anvendelser i informatikk og elektronikk. Etter fullført kurs skal studentene:- 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.
Eksamen
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.
Ny ordinær eksamen:
Gitt at kontinuasjonseksamen eller utsatt eksamen allerede blir arrangert vil øvrige studenter samtidig kunne ta ny ordinær eksamen.
Arbeidskrav: Obligatoriske øvelser kreves godkjent for adgang til å avlegge eksamen.
For mer informasjon, se forøvrig:- Utfyllende bestemmelser for eksamener ved Fakultet for naturvitenskap og teknologi
- Forskrift for eksamener i Tromsø
Pensum
Pensumliste for MAT-1005 Diskret matematikk, høsten 2013
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.
Error rendering component
- Om emnet
- Studiested: |
- Studiepoeng: 10
- Emnekode: MAT-1005
- Ansvarlig enhet
- Institutt for matematikk og statistikk
- Kontaktpersoner
-
- Tidligere år og semester for dette emnet