Diskret Matematik E3 (TMA 055) - HT04
Home page for
last year's course with links to previous courses
PS
PDF
Schema (OBS! Fr.o.m. Vecka 3 blir det bara tva ovningsgrupper i stallet for tre !!!)
PS
PDF
Kursplan
PS
PDF
Supplementära föreläsningsanteckningar
PS
PDF
Short course summary
PS
PDF
Extra exercises and solutions
Click
here
for a useful website
| Detailed schedule (subject to modification
during course !) |
Vecka 1:
Basic enumerative techniques. The pigeonhole principle. Counting pairs.
The multiplication principle. Permutations and combinations. Choice with
repitition allowed. Combinatorial arguments and identities.
The inclusion-exclusion principle.
Biggs : Chapters 9,10,11 (excluding 11.6, 11.7)
Vecka 2:
Recurrence relations. Deerangements, Stirling and Catalan numbers. Solution of
linear recurrence relations with constant coefficients. Time permitting, we'll
also discuss generating functions.
Biggs : Chapters 12,19. Generating functions are covered in Chapter 25.
Vecka 3:
Introduction to arithmeic. Euclid's algorithm and the fundamental theorem of
arithmetic. Linear Diophantine equations. Relations. Arithmetic modulo n.
Non-liner Diophantine equations.
Biggs : Chapter 8 and part of 13.
Vecka 4:
The theorems of Fermat and Euler. RSA encryption.
Biggs : Chapter 13. RSA encryption is not covered in the text.
Vecka 5:
Introduction to graph theory. Paths and cycles. Graph colouring. Planar graphs.
Biggs : Most of the material (though not all) is in Chapters 15 and 16.
Vecka 6:
Trees. Decision problems and search algorithms. Matchings and network flows.
Biggs : Chapters 17 and 18.
Vecka 7:
Wrapping up of loose ends and revision.
OBS! The miscellaneous exercises at the end of each chapter
in Biggs are often considerably more difficult than those after each section.
Hence, when studying, you should first work on the exercises after
each section. These represent the basic standard expected of you.
Vecka 1:
The following exercises from Biggs will be demonstrated
6.4.2, 10.2.1, 10.4.1, 10.5.4, 10.7.4, 11.1.7, 11.2.2, 11.3.2(iv),
11.4.2.
(In 1989 edition : 2.3.4, 3.2.1, 3.4.1, 3.5.4, 3.7.4, 4.1.7, 4.2.2, 4.3.2(iv),
4.4.2)
Suggestions for self-study : Further exercises from the same sections of the
book, plus the practice probelms for Week 1 from last year's course
(download from homepage for last year).
Vecka 2:
The following exercises from Biggs will be demonstrated
11.5.1, 11.5.4, 19.1.3, 19.2.3.
(In 1989 edition : 4.5.1, 4.5.4, 12.1.3, 12.2.3)
Vecka 3:
Thursday : 19.2.1 (12.2.1).
The exercise will be repeated, but with something non-zero
on the right-hand side (an exponential function or a polynomial in n), and
then repeated yet again using exponential generating functions (EGF).
For a definition of EGF, and further exercises, see
ps
pdf
Friday : 12.1.1, 12.1.2 (5.1.1, 5.1.2) and the following exercises
ps
pdf
Vecka 4:
Tuesday : 4.3.1 and 4.3.2 (1.6.4), plus the following exercises
ps
pdf
OBS! Here are a couple of facts which follow from the fundamental theorem of
arithmetic which are useful in solving many problems
ps
pdf
For self-study, I recommend the exercises in sections 8.4 - 8.7 of Biggs
(1.6 - 1.9 in the old edition). In fact, most of the exercises in 8.7 (1.9) you
should be able to solve without too much difficulty. I will also put a
few of them on the homework.
Thursday : Exercises 13.1.1, 13.1.2, 13.3.1, 13.4.1(ii) (6.1.1, 6.1.2, 6.3.1,
6.4.1(ii)) and the following exercises
ps
pdf
Vecka 5:
Tuesday : 13.2.2 (6.2.2) plus the following exercises
ps
pdf
Thursday : the following exercises
ps
pdf
followed by revision exercises, chosen in consultation with the participants.
Vecka 6:
Tuesday : 15.1.2, 15.2.1, 15.3.1, 15.4.3, 15.8.5, 15.8.6.
Thursday : 15.5.1, 15.5.2, 15.6.2(i)(ii), 15.7.1, 15.8.7
Vecka 7:
Tuesday : 16.3.3, 16.4.3, 16.6.1 plus the Ford-Fulkerson algorithm for the
network drawn on the board in Monday's lecture.
Thursday :
Here is a document which should help you when planning your strategy for how
to study for the exam
ps
pdf
| Övningstentor
(the first one is probably too hard) |
Om du har kommentarer, påpekanden eller annat att säga
om kursen, tryck
här
Peter Hegarty
<hegarty@math.chalmers.se>
Last modified: Tue Oct 7 18:24:07 MET DST 2003