close

Se connecter

Se connecter avec OpenID

Chapter 1

IntégréTéléchargement
Chapter 1 - 2
Elementary Notions and Notations
1
Section 1.3 Ordered Structures
• Tuples: Have order and can have
repetitions.
• For example, (6, 7, 6) is a 3-tuple and ( ) is
the empty tuple.
• We write (x1, …, xn) = (y1, …, yn) to mean
xi = yi for 1 ≤ i ≤ n.
2
Cartesian Product
• Cartesian Product: A ╳ B = {(x, y) | x ∊ A
and y ∊ B}.
• The definition extends to more than two
sets. For example, A ╳ B ╳ C = {(x, y, z) | x
∊ A, y ∊ B, z ∊ C}.
• Notation: A0 = {( )}, A1 = {(x) | x ∊ A}, and in
general, An = {(x1, …, xn) | xi ∊ A}.
• Quiz (1 minute). Does (A ╳ B) ╳ C = A ╳ (B
╳ C)?
3
Lists
• Lists: Are like tuples but there is no random access.
• For example, <a, b, a, c> is a list with 4 elements and <>
is the empty list.
• The operations on lists are head, tail, and cons. For
example,
head(<a, b, a, c>) = a
tail(<a, b, a, c>) = <b, a, c>
cons(a, <b, a, c>) = <a, b, a, c>
• The set of lists whose elements are in A is denoted by
lists(A).
• Quiz (1 minute). For L = <<a>, b, <c, d>>, find head(L)
and tail(L).
4
Strings
• Strings: Are like lists, but are represented as juxtaposed
elements from a given alphabet.
• For example, if A = {a, b}, then some strings over A are:
a, b, aa, ab, ba, bb, aaa, bbb.
• The empty string is denoted by ∧.
• The concatenation of two strings is their juxtaposition.
For example, the concatenation of
ab and bab is abbab.
• For any string s we have s∧ = ∧s = s.
• If s is a string, sn denotes the concatenation of s with
itself n times. Also s0= ∧. For example, (ab)3 = ababab.
5
Languages
• A language is a set of strings, usually
taken over some alphabet.
• Notation: If A is an alphabet, then the set
of all strings over A is denoted by A*.
• Example. Some languages over A are: Ø,
{∧}, A, and A*.
• Example. {abna | n ∊ N} = {aa, aba, abba,
abbba, … } is a language over {a, b}.
6
Language Operations
• Let L and M be languages. The product of
L and M, denoted LM, is the language
LM = {st | s ∊ L and t ∊ M}.
• Notation: L0 = {∧}; and Ln = {s1…sn| si ∊ L}.
7
Quizzes
• Quiz (1 minute). What are the products LØ
and L{∧}?
• Quiz (1 minute). Solve for L in the equation
{∧, a, b}L = {∧, a, b, aa, ba, aba, bba}.
8
closure
• The closure L* is the set of all possible
concatenations of strings in L. So
L* = L0 U L1 U … U Ln U …
• Quiz (1 minute). What are {∧}* and Ø*?
9
Example
• Examine the structure of an arbitrary string x ∊ L*(ML)*.
• A solution: Use the definitions to write x in terms of
strings in L and M.
1. Since x ∊ L*(ML)*, it follows that x = uv where u ∊ L* and
v ∊ (ML)*.
2. Since u ∊ L*, either u = ∧ or u = s1…sn for some n where
si ∊ L.
3. Since v ∊ (ML)*, either v = ∧ or v = r1t1 …rktk for some k
where ri ∊ M and ti ∊ L.
So x has one of four forms: ∧, s1…sn, r1t1 …rktk, or s1…snr1t1
…rktk .
10
Relations
• A relation is a set of tuples. If R is a relation and (x1, …,
xn) ∊ R, we write R(x1, …, xn).
• We can usually represent a relation as a subset of some
cartesian product.
• Example. Let R = {(0, 0), (1, 1), (4, 2), (9, 3), …, (n2, n),
…} = {(n2, n) | n ∊ N}. We might call R the “is square of”
relation on N. Notice also that R ⊂ N ╳ N.
• Notation: If R is binary, we can use infix to represent
pairs in R. For example, from the previous example, we
have (9, 3) ∊ R. So we can also write
R(9, 3) or 9 R 3 or 9 is square of 3.
11
Relational Databases
• A relational database is a relation where
the indexes of a tuple have associated
names called attributes.
12
Example
• Let Students = {(x, y, z) | x is a Name, y is a Major, and z
is Credits}.
• Who are the people majoring in CS?
{x | (x, CS, z) ∊ Students, for some z}.
Note: We need “for some z” to indicate that z is a
variable.
• How many math majors are upper division students?
| {x | (x, math, z) ∊ Students and z ≥ 90} |.
• What is the major of AbeLincoln?
{y | (AbeLincoln, y, z) ∊ Students, for some z}.
• What is the history department database of names and
their credits?
{(x, z) | (x, history, z) ∊ Students}.
13
Counting Tuples (or strings or lists)
• Product Rule: | A ╳ B | = | A | | B | and | An |
= | A | n.
• Example. If A = {a, b} and B = {1, 2, 3},
then
A ╳ B = {(a, 1), (a, 2), (a, 3), (b, 1), (b, 2),
(b, 3)}.
So | A ╳ B | = 6 = (2)(3) = | A | | B |.
14
Example
• Count the number of strings of
length 8 over A = {a, b, c} that
begin with either a or c and
have at least one b.
• A Solution: Split the problem
up into easier problems and
combine the results (divide
and conquer).
• Let U be the universe
consisting of the strings over A
of length 8 that begin with
either a or c.
• Let B be the subset of U
consisting of strings with no
b’s.
• Then the set of strings to count
is U – B, as pictured.
U-B
U
B
15
Example (cont’d)
• It is easy to calculate the cardinality of U – B:
| U – B | = | U | – | U ∩ B | = | U | – | B | (since B is a
subset of U)
• It is also easy to count U because it has the same
cardinality as the set {a, c} ╳ A7, which is
| {a, c} ╳ A7 | = | {a, c} | | A7 | = | {a, c} | | A |7 = (2)37.
• It is also easy to count B because it has the same
cardinality as the set {a, c}8, which is
| {a, c}8 | = | {a, c} |8 = 28.
• So we have the answer:
| U – B | = | U | – | U ∩ B | = | U | – | B | = (2)37 – 28,
which is 4118.
16
Section 1.4 Graphs and Trees
• A graph is set of objects called vertices or
nodes where some pairs of objects may
be connected by edges. (A directed graph
has edges that point in one direction.)
17
Example
• Draw a graph of the
South American countries
that touch the Pacific
Ocean and their
neighbors, where the
vertices are countries and
an edge indicates a
common border.
• Vertices = {Co, V, E, Br, P,
Bo, Ch, A}
• Edges = {{Co, V}, {Co, E},
….}.
Co
V
E
Br
P
Bo
Ch
A
18
Some definitions
• A path from vertex x0 to xn is a sequence of
edges that we denote by vertices x0, x1, …, xn,
where there is an edge from xi–1 to xi for 1≤ i ≤ n.
• The length of a path is the number of edges.
• A cycle is a path with distinct edges that begins
and ends at the same vertex.
• Example. A, Bo, A, is not a cycle since the
edge{A, Bo} occurs twice. A, Bo, Br, A, is a
cycle.
19
Quiz (1 minute)
• What is a longest path from A to V with
distinct edges and no cycles?
• Answer: The length is 6. For example, A,
Bo, Br, P, E, Co, V.
20
n-colorable
• A graph is n-colorable if it’s vertices can be
colored with n colors with distinct colors for
adjacent vertices. The chromatic number
of a graph is the smallest such n.
• Quiz (1 minute). What is the chromatic
number of the example graph?
21
Graph Traversals
• A graph traversal starts at some vertex v
and visits all vertices x that can be
reached by a path from v to x. But don’t
visit any vertex more than once.
22
Breadth-First
• If the graph has n vertices then start with a
vertex v and do the following:
for k := 0 to n – 1 do visit(v, k) od
where visit(v, k) visits all x not visited if
there is a path from v to x of length k.
23
A
Quizzes
B
C
• Use the pictured graph for the
E
following quizzes.
G
• Quiz (1 minute). Find a breadthfirst traversal that starts at F.
• One answer: F, H, D, G, B, A, E, C.
• Quiz (1 minute). Find a breadthfirst traversal that starts at C.
• One answer: C, A, E, D, B, F, H, G.
D
F
H
24
Depth-First
• Start at a vertex v and call the procedure
D(v), which is defined as follows:
D(v): if v has not been visited then
visit(v);
for each edge from v to x
do D(x) od
fi
25
Quizzes
• Quiz (1 minute). Find a depth-first
traversal of the pictured graph that starts
at F.
• One answer: F, H, G, D, B, A, C, E.
• Quiz (1 minute). Find a depth-first
traversal of the pictured graph that starts
at E.
• One answer: E, D, F, H, G, A, C, B.
26
Trees
• A tree is a connected graph (a path
between any two points) with no cycles.
Most trees are oriented so that they look
like upside-down trees, such as the tree
pictured.
• The top node is the root, the nodes directly
below a node are its children, the node
directly above a node is the parent, the
bottom nodes are leaves, and the height
or depth of the tree is the length of the
longest path of distinct edges from root to
a leaf.
• Example. For this tree the root is A. The
children of A are B, C, D. D is the parent of
G. The height or depth of the tree is 3. The
leaves are E, F, C, H, I.
A
B
E
C
D
F
G
H
I
27
A Recursive Definition
• Any node of a tree is the root of a subtree.
• One way to represent a tree is as a list whose
head is the root of the tree and whose tail is the
list of subtrees, where each subtree is
represented in the same way.
• Example. The pictured tree can be represented
by the list
<A, <B, <E>, <F>>, <C>, <D, <G, <H>, <I>>>>.
28
Expression Tree
• Any algebraic expression can be
represented as a tree.
• For example, the tree for the
expression
(x – y) + log(z + w) is pictured to
the right.
• Quiz (1 minute). Do a depth-first
(left to right) traversal.
• Answer: + – x y log + z w. This is
the prefix form of the expression.
+
log
-
x
y
+
z
w
29
Binary Trees
• A binary tree is either empty, denoted by <>, or
each node has two subtrees that are binary
trees and are called the left and right subtrees of
the node.
• If a binary tree is not empty, we’ll represent it as
a list of the form <L, x, R>, where x is the root
and L and R are the left and right subtrees,
respectively.
• Example. The binary tree with a single node x is
denoted by <<>, x, <>>.
30
binary search tree
• A binary search tree represents
ordered information, where the
predecessors and successors
of a node are in its left and
right subtrees, respectively.
• Example. A binary search tree
for the first six prime numbers
is pictured.
7
3
2
11
5
13
31
Spanning Trees
• A spanning tree for a connected graph is a
tree whose nodes are the nodes of the
graph and whose edges are a subset of
the edges of the graph.
• A minimal spanning tree minimizes the
sum of weights on the edges of all
spanning trees.
32
Example
• Use Prim’s algorithm to
construct a minimal spanning
tree for the pictured graph,
starting with node D.
• Solution: A minimal spanning
tree is constructed in 4 steps
B
B
1
1
A
2
C
D
2
C
B
1
3
1
2
D
C
2
3
E
B
A
B
1
1
1
1
D
3
A
2
D
D
C
E
2 33
The End of Chapter 1 – 2
34
Auteur
Документ
Catégorie
Без категории
Affichages
4
Taille du fichier
154 Кб
Étiquettes
1/--Pages
signaler