Probeklausur-loesung 2013 Jünger PDF

Preview

Summary

Pr♦❢✳❉✐♣❧✳✲■♥❢✳❉r✳▼✳❉❛♥✐❡❧❏ü♥❣❡r❙❝❤♠✐❞t ❙♦♠♠❡rs❡♠❡st❡r✷✵✶✸Pr♦❜ ❡❦❧❛✉s✉r■♥❢♦r♠❛t✐❦③✉r ❱♦r❧❡s✉♥❣■❉❡❝❦❜❧❛tt✶✺✳✵✼✳✷✵✶✸ ❇✐tt❡◆❛♠❡♥♦t✐❡r❡♥❙✐❡❞✐❡❢♦❧❣❡♥❞❡♥❆♥❣❛❜ ❡♥✐♥❞❡✉t❧✐❝❤❡r❇❧♦ ❝❦s❝❤r✐❢t✿ ❱♦r♥❛♠❡▼❛tr✐❦❡❧♥✉♠♠❡r Prü❢✉♥❣s♥✉♠♠❡r❙t✉❞✐❡♥❣❛♥❣ ❊♠❛✐❧ •t❡♥✱❉✐❡●❡❜ ❡♥❑❧❛✉s✉r♠❡❧❞❡♥❙✐❡❞✐❡s❡s❙✐❡❜ ❡st❡❤ts✐❝❤❇❧❛tt❜✐tt❡❛✉s...

Description

•

• • • • • • • •

Σ

Σ

O Ω

12n

=

O (n2 )

7n2

=

Ω (n )

2n

=

O (3n )

23 log(n2 + 7)

=

Θ (log n)

Θ

1+1+1+2

2n + 8 = O (n) 7n2 = Ω (n2 ) 5n log(n10 ) = O (n log n) 3n 6= O (2n ) f, g : N → N

f = O (g) ⇐⇒ g = Ω (f ) 2+2+2+4+5

n0 = 8

c=3

n ≥ n0 = 8 0 ≤ 2n + 8 ≤ 3n

n≥8

= cn n0 = 1

c=7

n ≥ n0 = 1 7n2 ≥ cn2 ≥ 0

n0 = 1

c = 50

n ≥ n0 = 1

0 ≤ 5n log(n10 ) = 50n log n ≤ c(n log n) a, k ∈ Z log(ak ) = k log a

3n = O (2n )

c>0

n0 ∈ N

n ≥ n0 0 ≤ 3n ≤ c · 2n n ≥ n0 3n ≤c 2n   n 3 ≤c 2 3 n log2 ≤ log2 c 2 log2 c =: c′ n≤ log2 1.5

⇐⇒ ⇐⇒ ⇐⇒ n

c′

n ≥ n0

(∗)

f = O (g) ⇐⇒ ∃c ≥ 0 ∀n ≥ n0 : 0 ≤ f (n) ≤ cg(n) 1 ⇐⇒ ∃c ≥ 0 ∀n ≥ n0 : 0 ≤ f (n) ≤ g(n) c ⇐⇒ ∃c′ ≥ 0 ∀n ≥ n0 : g(n) ≥ c′ f (n) ≥ 0 ⇐⇒ g = Ω (f )

∗

L

L

O 3+5+2

O (1)

Θn n 2

h5, 3, 1, 6, 4, 8, 7i

T = (V, E) s(v)

v∈V n Θ(

n

) n

Θ(

log n

)

12 + 4 + 2 + 2 + 5

v∈V •

w

•

w

TL (v) TR (v)

s(w) ≤ s(v)

v v

s(w) > s(v)

v v

v

v v w := w v

v

w

w:E→N δG (S) S ⊆ V δG (S)

G = (V, E) T = (V, ET ) G G A ∩ δ(S) = ∅ uv ∈ E G A ∪ uv

A ⊆ ET uv 21 + 14

T T =∅

(4, 6)

T = T ∪ {(4, 6)}

(1, 2)

T = T ∪ {(1, 2)}

T = T ∪ {(5, 6)}

(5, 6)

(4, 5)

T = T ∪ {(1, 3)}

(1, 3)

(2, 3)

T = T ∪ {(2, 4)}

(2, 4)

n−1 G

uv ∈ ET

uv

T uv ∈ / ET ET ∪ {uv}

T T

P

u

v

P ∪ {uv} =: C

uv ∈ δG (S) S

C

u P

δG (S) ∩ A = ∅

S xy ∈ /A

T ′ = (T \ {xy}) ∪ {uv } δG (S)

v xy xy ∈ δG (S) uv e ∈ δG (S)

xy ∈ δG (S) w(uv) ≤ w(e)

w(T ′ ) = w(T ) − w(xy) + w(uv ) ≤ w(T ) − w(uv) + w(uv ) = w(T ) T′

(l + r )/2

l == r

A, a, l, m − 1

a == A[m]

A, a, m + 1, r

10

x>0 k

x

k≥0

xk

xk •

k=0

1

•

k=1

x

•

k>1

x | · x ·{z· · · · x} k

xk

xk =

xk

 1,     x,

k=0 2

k 2

 (x ) ,    k−1 x · (x2 ) 2 O(log k)

k=1 k>1 k>1

k mod 2 = 0 k mod 2 = 1

10 + 10...