A N N O U N C E M E N T S | |
---|---|
Tue 29 Aug 2017 |
Instructor Verhoeff is not available on Fri 22 Sep.
Please, attend an instruction of another group. |
Tue 29 Aug 2017 |
To practice your problem solving skills for this course:
|
T.Verhoeff@tue.nl
.
[2IT50]
.
To prepare:
Why study relations?
Example (Java):
/** Finds a location of the minimum in given array. */ public static int locateMin(int[] a)The input/output relation is captured by
@post: {@code a.has(\result) && (a[\result] == (\min i; a.has(i); a[i]))}This involves a relation from integer arrays to integer values. Note that a given array can relate to multiple correct results (viz. if the minimum occurs more than once). Therefore, a mathematical function is not appropriate as specification.
That is why it is important to understand properties of
the various types of relations.
For example,
in Java, the method equals()
(defined on the class Object
, from which every other class
inherits) must be implemented
such that it yields an equivalence relation.
See: Java 8 API documentation for Object.equals()
,
which
involves terminology such as
equivalence relation,
reflexive, symmetric, transitive.
Warm-up problems on Brilliant.org:
To prepare:
Is the geometric relation "lies-entirely-on-top-of" transitive? See Paradoxical Triangular Braid.
How can relations appear in (Java) programming?
= != < <= > >=Used as
x R y
.
public static boolean R(X x, Y y) . . .Used as
R(x, y)
.
class X { public boolean R(Y y) . . . }Used as
x.R(y)
Typical example: method
Object.equals()
.
boolean[][] R;Used as
R[x][y]
.
List<List<Boolean>> R;Used as
R.get(x).get(y)
Note that the syntax differs considerably, but the reasoning is all similar.
To prepare:
Function notation is a bit "broken":
If g : C ← B and f : B ← A, then g o f : C ← A
For a ∈ A, we then have a.(g o f) = (a.g).f
Alternative characterizations of injective and surjective functions:
(∀ C, g, h : C → A : f o g = f o h ⇒ g = h)This is a left cancelation law for composition with an injective function.
(∀ C, g, h : B → C : g o f = h o f ⇒ g = h)This is a right cancelation law for composition with a surjective function.
Euler cycles and Hamilton cycles appear in the mathematical sculptures by Koos Verhoeff.
Theorem on parity of number of nodes with odd degree.
Warm-up problems on Brilliant.org:
To prepare:
You can mail me your solutions (worked out as if it was an exam) for exercises 7 and 13.
(∀ x : x ∈ X : x ⊑ y)where X ⊆ U and y ∈ U .
This makes it possible to characterize sup(X) by (cf. Lemma 4.22):
(∀ y : y ∈ U : X ⊑ y ⇔ sup(X) ⊑ y)
To prepare:
During the instruction, we investigated Z11*.
Warm-up problems on Brilliant.org about Group Theory (Ch.5):
Warm-up problems on Brilliant.org about Combinatorics (Ch.6):
The Twelvefold Way (Wikipedia): a systematic classification of 12 related enumerative problems concerning two finite sets.
A very nice (inexpensive and short) booklet on Combinatorics (including Graphs):
Robin Wilson.For the course Discrete Structures, especially Chapters 1, 2, 3, 4, and 6 are relevant.
Combinatorics: A Very Short Introduction.
Oxford University Press, 2016.
(Also available as ebook.)
To prepare:
Warm-up problems on Brilliant.org about Number Theory (Ch.7):