Diskret Matematik E3 (TMA 055) - HT05
Home page for
last year's course with links to previous courses
PS
PDF
Schema (OBS! Vi börjar med två övningsgrupper.
Antalet kan utökas om det visar sig att behovet finns.)
PS
PDF
Kursplan (OBS! Viktig notis angående kursboken. Annars
är det samma kursplan som i fjol.)
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.
Biggs : Chapters 6.4, 10 (except 10.3), 11.1 - 11.3 (see also Ch.19, though we
won't go into this chapter any deeper).
Grimaldi : Chapters 1.1 - 1.4, 5.5.
Vecka 2:
The inclusion-exclusion principle.
Recurrence relations. Derangements. Solution of
linear recurrence relations with constant coefficients.
Biggs : Chapters 11.4, 11.5, 19.1, 19.2.
Grimaldi : 8.1, 8.2, 8.3, 10.1, 10.2.
Vecka 3:
Linear recurrence relations with constant coefficients (continued). Stirling
and Catalan numbers. Introduction to arithmeic. Euclid's algorithm and the
fundamental theorem of
arithmetic. Linear Diophantine equations.
Biggs : Chapters 25.4-25.6, 8.
Grimaldi : 10.3, 1.5, 5.3, 4.
Vecka 4:
Relations. Modular arithmetic. Non-linear Diophantine equations.
Biggs : 13.1, 13.2.
Grimaldi : 14.1, 14.2, 14.3 (see also 5.1).
Vecka 5:
Invertible elements in Z_n. The theorems of Fermat and Euler. The Chinese
Remainder Theorem. Introduction to public-key cryptography.
Biggs : 13.3. CRT is an exercise in 13.6. RSA is not covered in this book.
Grimaldi : 14.3, 14.4, 16.2, 16.3, 16.4 (OBS!!! Grimaldi's treatment of these
subjects is far more abstract algebraic than mine will be. Hence, I actually
recommend that you not use the book, unless you want to get a deeper insight
into the subject for your own benefit. I will post lists of recommended
exercises).
Vecka 6:
RSA encryption. Introduction to graphs - Paths and cycles, Euler/Hamilton paths
and cycles, Planar graphs, Graph coloring.
Biggs : Chapters 15,16.
Grimaldi : 16.4,11,12.
Vecka 7:
Monday : More on planar graphs and graph coloring. Trees and search
algorithms (Euler cycles, path, minimal spanning tree, Dijkstra's
algorithm for shortest paths).
Wednesday : 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 will be demonstrated (download
ps
pdf)
6.4.2(B), 10.2.1(B), 10.5.2(B), 10.7.4(B), 10.7.5(B), 1.3.7(G),
11.1.7(B), 11.2.2(B), 11.3.2(iv)(B).
Suggestions for self-study : Further exercises from same sections of Biggs,
exercises from Grimaldi on handout,
plus the practice problems for Week 1 from last year's course
(download from homepage for last year).
Vecka 2:
The following exercises will be demonstrated (download
ps
pdf)
11.5.1(B), 11.5.4(B), 11.4.2(B), 8.1.8(G), 8.2.7(G), 19.1.3(B), 10.1.2c(G),
10.2.1e(G), 19.2.3(B) or 10.2.11(G).
Suggestions for self-study : Handouts from Grimaldi.
Vecka 3:
The week's exercises can be downloaded here
ps
pdf
Vecka 4:
Tuesday : No exercises will be demonstrated today ; you may study on your own.
Here are some recommended exercises on arithmetic from the sections of
Grimaldi recently handed out :
Section 4.3 : 2,7,10,11,13.
Section 4.4 : 1(b),6,8,10,13,17,19.
Section 4.5 : 1(b),6,8,13,14,18,19,21,26,27.
OBS! Here are a couple of facts which follow from the fundamental theorem of
arithmetic which are useful in solving many problems
ps
pdf
Thursday : The following exercises will be demonstrated
ps
pdf
Vecka 5:
Tisdag : Följande uppgifter kommer att demonstreras
ps
pdf
Torsdag : Följande uppgifter kommer att demonstreras
ps
pdf
Vecka 6:
Tisdag : Följande uppgifter kommer att demonstreras
ps
pdf
Torsdag : Följande uppgifter kommer att demonstreras
ps
pdf
Vecka 7:
Tisdag : Följande uppgifter ska demonstreras (de flesta har bilder
med sig så jag avstår från att skriva ut dem) :
15.5.1(B), 15.5.2(B), 16.3.3(B), 16.4.3(B), 16.6.1(B), 11.4.14(a)(b) (G).
Torsdag : Repitition.
Följande är lösningar till demonstrationsuppgifter som vi (jag
eller David) inte hann fram till under lektionerna
ps
pdf
Here is an updated version of the 2004 document which should help you when
planning your strategy for how to study for the exam
ps
pdf
| Kommentarer på gamla tentor |
On the homepages for the last two years you will find five exams plus three
"practice exams". The exam ??/04/05 has mysteriously disappeared (I will
see if the secretary has a copy) and "Övningstenta 4" probably
never existed.
Otherwise, basically all the questions on these exams are examinable material.
The only exceptions are question 4(ii) on each of 20/10/04 and 15/01/05.
These two exams are at the same level as you can expect this time. The exams
from 2003 and the practice exams are generally at a higher level.
In the language of "Level 1,2,3" in the study document above, we
can make the following summary :
Övningstenta 1 : #5 is the only Level 1 question. All others are
essentially Level 3.
Övningstenta 2 : #1,6 are Level 3. Rest are Level 1.
Övningstenta 3 : #3 is Level 2, #4,5(ii),6 are Level 3.
20/10/03 : #4,6 are Level 3. Rest are Level 1.
10/01/04 : #4 is Level 2, #5(i),6 are Level 3.
22/04/04 : #4,5(iii) are Level 2, #6 is Level 3.
OBS! The solutions to some of the questions concerning recurrence relations
on the old exams use the method of generating functions, which was not
introduced this year. Here are corresponding
solutions which do not use this method
ps
pdf
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