Skriv ut Lukk vindu


 

Høst 2018

MAT-1005 Diskret matematikk - 10 stp


Ansvarlig fakultet

Fakultet for naturvitenskap og teknologi

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.

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.

Søknadsfrist

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

Opptakskrav

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

Søknadskode 9336 - enkeltemner i realfag.


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:

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ø


Dato for eksamen

Skriftlig prøve 30.11.2018

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.


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.

Undervisning Høst 2018
Første oppmøte: Tirsdag 21.08. kl. 14.15, Store aud., Realfagsbygget
Forelesning prof. Andrei Prasolov