høst 2018

MAT-1005 Diskret matematikk - 10 stp

Sist endret: 25.02.2019

Ansvarlig fakultet

Fakultet for naturvitenskap og teknologi

Studiested

Tromsø |

Søknadsfrist

1. juni for emner som tilbys i høstsemesteret. 1. desember for emner som tilbys i vårsemesteret.

Emnetype

Emnet er obligatorisk i studieprogrammene Informatikk - bachelor og Informatikk - master (5-årig), sivilingeniør samt studiretningen Matematikk - Lektorutdanning for trinn 8-13 - master (5-årig). Det kan også tas som enkeltemne.

Opptakskrav

Generell studiekompetanse og følgende spesielle opptakskrav:
Matematikk R1 + R2 og i tillegg enten:

  • Fysikk 1 + 2 eller
  • Kjemi 1+ 2 eller
  • Biologi 1 + 2 eller
  • Informasjonsteknologi 1 +2 eller
  • Geofag 1 + 2 eller
  • Teknologi og forskningslære 1 + 2

Søknadskode 9336 - enkeltemner i realfag.

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.

Undervisnings- og eksamensspråk

Norsk

Undervisning

Forelesninger: 40 t
Øvelser: 30 t

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.

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 ved UiT Norges arktiske universitet Tromsø

Eksamensdato

Skriftlig prø
ve 30.11.2018

Eksamensdato er foreløpig og vil kunne bli endret. Endelig eksamensdato kunngjøres på uit.no/eksamen og i studentweb primo mai for vårsemesteret og primo november for høstsemesteret

Timeplan

Pensum

Pensumliste for MAT-1005 Diskret matematikk, høsten 2018
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.



Kontakt
Prof.-Andrei-Prasolov

Andrei Prasolov


Professor
Telefon: +4777644016 andrei.prasolov@uit.no