"
"
"
"
"
" m, n > 0
" NW D(m, n)
{ }
NW D(a, b) = NW D(m, n), a, b e" 1
a = b a = NW D(a, b)
m + n - 2
a > b NW D(a, b) = NW D(a-b, b)
k a b (a - b)
b
a + b
1 a e" 1 b e" 1
m + n - 2
"
"
" n a1, a2, . . . , an
" a , a , . . . , a a1, a2, . . . , an a d"
1 2 n 1
a d" . . . d" a
2 n
2, 7, 4, 5, 1 1, 2, 4, 5, 7
A[j] j
Dane : 2 7 4 5 1
2 4 7 5 1
2 4 5 7 1
W ynik : 1 2 4 5 7
5
1000
N
N n
n
" tj j
" tj
tj = j
" T (n)
n n

T (n) = 3(n - 1) + n + 2 (j - 1) + j - 1 =
j=2 j=2
n(n - 1) n(n + 1) 3 7
= 3(n - 1) + n + 2 + - 1 = n2 + n - 4
2 2 2 2
7 3
n -4
2 2
n n2
O(n2)
O(f(n)) f : N N g :
N N O(f(n)) g " O(f(n)) g = O(f(n))
a, b " R n > b g(n) d" a " f(n) g
f
 n
n
n - 1
n - 1
n = 3
n
" an n

a1 = 1
an+1 = an + 1 + an = 2an + 1
an = 2n - 1
n = 1 21 - 1 = 1 = a1 an = 2n - 1
an+1 = 2an + 1 = 2(2n - 1) + 1 = 2n+1 - 2 + 1 = 2n+1 - 1
O(2n)
" n w1, . . . , wn
w
" 1 d" i d" n w = wi
w = a , ala , b , bela , hela w = bela

wm1 wm2
pn n

p1 = 1
p2n = pn + 1
pn <" log n
log n O(log n)
= 10-3
 O(log n) 21000
O(n) 1000 6 " 104 3.6 " 106
O(n " log n) 140 4893 2 " 105
O(n2) 31 244 1897
n3 10 39 153
O(2n) 9 15 21
O(log n) s1 s10
1
O(n) s2 10 " s2
O(n " log n) s3 10 " s3
n
O(n2) s4 3.16 " s4
n3 s5 2.15 " s5
O(2n) s76 s6 + 3.3
"
"
"
"
 C++















































































 T ord T
succ, pred : T - T
succ T pred
T
(x + y)/z
(x + y) < z
(p and ((s1 + litera) < z)) or not q
n mod m
 T 1, . . . T n T
× . . . ×
 × . . . ×
P (a\w){ a := w }P
P P (a\w) P
a w
P [a\w] P
(b = (x + n) + 1){a := x + n}(b = a + 1)
a := x + n (b = (x + n) + 1)
(b = a + 1)
(n + 1 < k '" n + 1 > 0){n := n + 1}(n < k '" n > 0)
n := n+1 (n+1 < k'"n+1 >
0) (n < k '" n > 0)
P
w
a
w
P { I }Q
P Q I
I P
Q P
Q
P { I }Q, Q{ J }R
P { I; J }R

P Ò! P , P { I }Q, Q Ò! Q , Q { J }R, R Ò! R
P { I; J }S
x y T
z T
(x = a '" y = b) {z := x} (z = a '" y = b)
(z = a '" y = b) {x := y} (z = a '" x = b)
(z = a '" x = b) {y := z} (y = a '" x = b)
(x = a '" y = b) {z := x; x := y; y := z} (y = a '" x = b)
T
x y
x y
(y = a '" x = b)
((x+y)-((x+y)-y)) = b'"(x+y)-y = a {x := x+y} x-(x-y) = b'"x-y = a
x - (x - y) = b '" x - y = a {y := x - y} (x - y) = b '" y = a)
(x - y) = b '" y = a) {x := x - y} x = b '" y = a)
((x+y)-((x+y)-y)) = b'"(x+y)-y = a
(x = a '" y = b) Ò! ((x + y) - ((x + y) - y)) = b '" (x + y) - y = a
(x = a '" y = b) {x := x + y; y := x - y; y := x - y} (x = b '" y = a)
P { }P
P I1; ; I2
Pi { Ii } Pi+1 i = 1, . . . , n
P1 {beginI1; . . . ; Inend} Pn+1
P '" w { I } Q P '" Źw Ò! Q
P {ifwthenI} Q
P '" w { I1 } Q P '" Źw { I2 } Q
P {ifwthenI1elseI2} Q
x
T {ifx < 0thenabs := -xelseabs := x } abs = |x|
 T
(T '" x < 0) Ò! (-x = -x '" x < 0), (abs = -x '" x < 0) Ò! (abs = |x|)
((-x = -x '" x < 0) { abs := -x } (abs = -x '" x < 0)
(T '" x < 0) { abs := -x } (abs = |x|)
(T '" Ź(x < 0)) { abs := x } (abs := |x|).
P '" w { I } P
P {whilewdoI } P '" Źw
P
I w
P
m"n
T { } (a = |n|)
(a = |n|) { } (k = 0 '" x = 0 '" (a = |n|))
(k = 0 '" x = 0 '" (a = |n|)) Ò! (k d" a '" x = k " m)
Q = (k d" a '" x = k " m)
Q '" (k < a) { } Q
Q
Q { } (Ź(k < a) '" Q)
Q { } (k = a '" Q)
(x = a " m '" a = |n|) { }
(iloczyn = n " m)
 I
i t1 d" succ(t2)
P (t1), P (i) { I } P (succ(i)) i = t1, . . . , t2
P (t1) {fori := t1tot2doI } P (succ(t2))
P
I x t1 t2
w
x
n
"
" 1 0
A = [1, 0, 0, 7, 1, 1, 0, 6, 7, 1, 1] 2
 0, 1 2, 3
"
"
"
"
"
"
"
 x
y b t
a t
b
a b

1 n = 0
n! =
n " (n - 1)! n > 0
 "
5
"
",
 n 5
n = 0

n 5
n
n - 1 = 5 - 1 = 4
•"
•" n 5
•", n = 5
",
n 4 4 = 0

n = 4 - 1 = 3
n
•", n = 4
•", n = 5
",
•", n = 1
•", n = 2
•", n = 3
•", n = 4
•", n = 5
",
•" n = 1
•", n = 2
•", n = 3
•", n = 4
•", n = 5
",
•" n = 1
n = 1
1
1
•" n = 2
120
",
"
120
Å„Å‚
ôÅ‚
0 n = 0
òÅ‚
fn = 1 n = 1
ôÅ‚
ół
fn-2 + fn-1 n > 1










x = fi+1 '" y = fi
"
"
" S
p q
p
q p{S}q
" S
p q
p
q
S1
p = (n > 0)
q = (silnia = n!)
p S1
r = (silnia = k!)'"(k d" n)
S1
r while
S
 r (k < n) silnia0
k0 silnia k S silnia1
k1 S
k k1 = k0 + 1 k0 < n k1 = k0 + 1 d" n
silnia k
silnia1 = silnia0 " k1 = k0! " (k0 + 1) = (k0 + 1)! = k1!
r '" (k < n){S}r
r{whilek < ndoS}(k e" n) '" r
while k = n'"silnia = k!
q p{S1}q S1
p q
while n-1 k = n
k = 1
k S1
p q
S2
p = (n > 0)
q = (y = xn)
Q = (xn = y " zm '" m e" 0)
z1 y1 m1 z y m
z2 y2 m2
" m1 = 2 " k y2 = y1
xn = y1 " z1m1 = y1 " (z1 " z1)k = y2 " z2m2;
" m1 = 2 " k + 1 y2 = y1 " z1
xn = y1 " z1m1 = (y1 " z1) " (z1 " z1)k = y2 " z2m2.
m = 0 xn = y " zm = y " 1 = y p{S2}q
m
1 n S2
n > 0
 n
" n
" n n × n
n = 8

64
<" 4 · 109
8
(i1, . . . , i8) 1 d" i1, . . . , i8 d" 8
((1, i1), . . . , (8, i8))
88 <" 107
(i1, . . . , i8) {1, . . . , 8}
8! = 104
 n = 8
"
 n
het[i] = 0 i
het[i] = j > 0 i j


true i
kol[i] =
false i

true i
lewy[i] =
false i

true i
prawy[i] =
false i

true
OK =
false
" n a1, a2, . . . , an
" a , a , . . . , a a1, a2, . . . , an a d"
1 2 n 1
a d" . . . d" a
2 n
" a1, a2, . . . , an b1, b2, . . . , bm
" c1, c2, . . . , cn+m a1, a2, . . . , an, b1, b2, . . . , bm
c1 d" c2 d" . . . d" cn+m
a1, a2, . . . , an, b1, b2, . . . , bm
a1 d" b1 a2 d" b1 a2 d" b2 a2 d" b3 . . .
a1, b1, b2, a2 . . .
n + m - 1
 T
T (n)
 n
n = 2k

0 n = 1
T (n) =
2 · T (n/2) + (n - 1) n > 1
O(f(n)) &!(f(n)) Åš(f(n)) f : N N
g : N N O(f(n))
a, b " R n > a g(n) d" b · f(n) g(n) " O(f(n))
g(n) O(f(n)) g(n) = O(f(n))
g : N N &!(f(n))
a, b " R n > a b · f(n) d" g(n) g(n) "
&!(f(n)) g(n) &!(f(n)) g(n) = &!(f(n))
g : N N Åš(f(n)) g
O(f(n)) &!(f(n))
a, b, c

b n = 1
T (n) =
a · T (n/c) + b · n n > 1
n ck k " N
Å„Å‚
ôÅ‚
O(n) a < c
òÅ‚
T (n) = O(n ln n) a = c
ôÅ‚
ół
O(nlogc a) a > c
a, b, c
1
c
a
b · n n
a = b = c = 2 T (n) = O(n · ln(n))
T (n) = Åš(n · ln(n))
a
r = n = cm
c
m

T (n) = n · b · ri gdzie (m = logc n).
i=0
m
m = 0 n = c0 = 1
0

T (n) = T (1) = b = n · b · ri.
i=0
m = 0
n = cm
T
def T
T (cm+1) = a · T (cm) + b · cm+1 ind.
=
m

= a · n · b · ri + b · cm+1 =
i=0
m

a
= · cm+1 · b · ri + b · cm+1 =
c
i=0
m

a
= b · cm+1( · ri + 1) =
c
i=0
m+1

= b · cm+1( ri + r0) =
i=1
m+1

= b · cm+1 · ri
i=0
"
a < c ri
i=0
1
1-r
m

1
T (n) = n · b · ri d" · b · n = O(n).
a
1 -
c
i=0
a = c ri = 1 i " N n = cm
m
ri = logc n
r=0
T (n) = b · n · logc n = O(n ln n).
 a > c m = logc n
logc
n
r1+logc n - 1
T (n) = n · b · ri = b · n · =
r - 1
i=0
b a
= · (n · ( )1+logc n - n) =
r - 1 c
b a1+logc n
= · (n · ( ) - n) =
r - 1 c · n
a · b c · n
= · (alogc n - ) =
c · (r - 1) a
c · n
= const · (nlogc a - ) = O(nlogc a)
a
const alogc n =
nlogc a a > c logc a > 1
n O(n ln n)
2 3 4
O(n)
O(n ln n)
O(n ln n)
a1, a2, a3
a1 < a2



a2 < a3 a3 < a2


a1 < a2 < a3 a1 < a3 a3 < a2 < a1 a1 < a3


a1 < a3 < a2 a3 < a1 < a2 a2 < a1 < a3 a2 < a1 < a3
{a1, a2, a3}
n
&!(n ln n)
H(n)
n! h 2h
h 2h
n! d" 2H(n)
log2(n!) d" H(n).
n! e" (n)n
3
n
H(n) e" log2(n!) e" log2( )n = n · log2 n - n · log 3 = &!(n · ln n).
3
n
&!(n ln n)
 =< x1, . . . , xm > =< y1, . . . , yn > =< z1, . . . , zk >
x y z

z x
< i1, . . . , ik > zj = xij j = 1, . . . , k

z x y x y
NW P (
x, y)

x y
=< A, B, C, B, D, A, B >, =< B, B, D, C, B, A, A >
x y

=< B, D, A >, z =< D, C > .
z

z
z x y x y
"
x y
" " NW P (
z x, y)
 n 2n
NW P
=< x1, . . . , xm > i d" n i
x
=< x1, . . . , xi >
x xi
=< A, B, C, B, D, A, B >, =< A, B, C, B >, = "
x x4 x0
=< x1, . . . , xm > =< y1, . . . , yn >
x y
=< z1, . . . , zk >" NW P (
z x, y)
xm = yn zk = xm = yn " NW P (
zk-1 xm-1, yn-1)
xm = yn zk = xm " NW P (
z xm-1, y)
xm = yn zk = yn " NW P (
z x, yn-1)
xm = yn zk = xm <

z1, . . . , zk, xm " NW P (
x y z x, y)
zk = xm
zk = yn
" NW P ( zk-1
zk-1 xm-1, yn-1)

xm-1 yn-1
w =< w1, . . . , wk >
xm-1 yn-1 < w1, . . . , wk, xm >

x y z
zk = xm
z xm-1

xm-1 y x y
" NW P (
z x, y)

z " NW P ( gdy xm = yn
xm-1, yn-1)
z1 " NW P ( z2 " NW P ( gdy xm = yn
xm-1, y), x, yn-1)
NW P (
x, y)
c(i, j) =
xi yj
Å„Å‚
ôÅ‚
0 i = 0 j = 0
òÅ‚
c(i, j) = c(i - 1, j - 1) + 1 xi = yj
ôÅ‚
ół
max(c(i - 1, j), c(i, j - 1)) xi = yj

c

x y x y
c(i, j) i, j > 0 c
c(i - 1, j) c(i, j - 1)
"
x y
" c b b(i, j) =

xi yj
b c b
 b c
=< A, B, C, B, D, A, B > =< B, D, C, A, B, A > m = 7 n = 6
x y
j 0 1 2 3 4 5 6
i “! B D C A B A
y
0 “! 0 0 0 0 0 0 0
x
1 A 0 x, 0 x, 0 x, 0 xy, 1 y, 1 xy, 1
2 B 0 xy, 1 y, 1 y, 1 x, 1 xy, 2 y, 2
3 C 0 x, 1 x, 1 xy, 2 y, 2 x, 2 x, 2
4 B 0 xy, 1 x, 1 y, 2 y, 2 xy, 3 y, 3
5 D 0 x, 1 xy, 2 x, 2 x, 2 x, 3 x, 3
6 A 0 x, 1 x, 2 x, 2 xy, 3 x, 3 xy, 4
7 B 0 xy, 1 x, 2 x, 2 x, 3 xy, 4 x, 4
c[7, 6] = 4
4 b[i, j] = x
x y
b[i, j] = y b[i, j] = xy
<
x y
B, C, B, A >" NW P (
x, y)
b " NW P (
z x, y)
 "
z
NW P (
x, y)
" n P = {[si, fi) : 1 d" i d" n}
si, fi " R si < fi i = 1, . . . , n
" A Ä…" {1, . . . , n}
i, j " A i = j [si, fi) )" [sj, fj) = "

fi d"
fj 1 d" i < j d" n
 B Ä…" {1, . . . , n} |B| =
k A Ä…" {1, . . . , n}
Al l A Bl
B l
A
A
l = 1, . . . , k
Al Al *" Bl
k = l Bk = " Ak*"Bk Ä…" A
Ak = A
l = 1 A1 *" B1 =
{1} *" B - {min(B)} f1 d" fmin(B)
fi [s1, f1)
[si, fi) i " B - {min(B)} A1 *" B1 = {1} *" B1
k
1 d" l < k Al*"Bl
l < k
" = Bl Ä…" {j : sj e" fmax(Al)} = ".

i = min{j : sj e" fmax(Al)} Al+1 = Al *" {i} i
si e" fmax(Al) [si, fi)
Al i fi d" fmin(B ) [si, fi)
l
Bl+1 = Bl - {min(Bl)} Al+1 *" Bl+1
"
"
" n i vi
wi w

" A Ä…" {1, . . . , n} wi d" w
i"A

vi
i"A
" n i vi
wi w
" A Ä…" {1, . . . , n} ri " R i " A

ri · wi d" w ri · vi
i"A i"A
 0-1
vi
wi
k k+1
k wi d" w < wi
i=1 i=1
k
w - wi k + 1
i=1
 O(n ln(n))










n n
A
Ä™! 1 Ä™! i 2i Ä™! Ä™! 2i + 1 n Ä™!
A[1]
i 2i 2i + 1
i n < 2i
A[i] d" A[ i/2 ] i = 1, . . . , n
i
j i + 1
j
j e"
w e" 2i O(ln(n))
O(ln(n))
 A[i+1], . . . , A[j]
1 < i < j
A[i], . . . , A[j]
i j
O(n)
1 d" i d" n i
i
W (n) n
m 2m+1 - 1 2m
hn(i) i n

hn(i) d" hn (i) dla n d" n .
2m d" n d" n = 2m+1 - 1

hn (i) = 2m-i.
m m m


W (n) = i · hn(i) d" i · hn (i) = i · 2m-i =
i=1 i=1 i=1
m

i
= 2m · d" c · n = O(n)
2i
i=1
O(n ln(n))
O(n)
n i = 1, . . . , n
O(ln(i))
O(n ln(n))
 2n × 2n L
 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
764.5 7 " 102 + 6 " 101 + 4 " 100 + 5 " 10-1
cyfra reprezentacja
0 0000
1 0001
2 0010
3 0011
4 0100
5 0101
6 0110
7 0111
8 1000
9 1001
1101
0, 1
(1010.1.5)2 1 " 23 + 0 " 22 + 1 " 21 + 0 " 20 + 1 " 2-1
n
n
2
2
x = (43.625)10
43
21 1
625
10 1
1 250
5 0
0 500
2 1
1 000
1 0
0 1
x = (101011.101)2
y = (69.76)10
76
69
1 52
34 1
1 04
17 0
0 08
8 1
0 16
4 0
0 32
2 0
0 64
1 0
1 28
0 1
. . . . . .
y H" (1000101.1100001)2.
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F
E9B.F 14 " 162 + 9 " 161 + 11 " 160 + 15 " 16-1
cyfra reprezentacja cyfra reprezentacja
0 0000 8 1000
1 0001 9 1001
2 0010 A 1010
3 0011 B 1011
4 0100 C 1100
5 0101 D 1101
6 0110 E 1110
7 0111 F 1111
n
n = 8




0 1 0 0 1 1 0 1
77
0
1
0
0
 2
0
2
1
x = 10011000
1 x
01100111
2
1 x 2 x
01100111
+ 1
01101000
2
01101000
2 n = 8
0 d" x d" 127
x




0
-128 d" x d" -1
2 x




1
0 1 0 1 0 0 0 0
80
1 1 0 1 0 0 0 0
-(0110000)2 = -48
2
n 2
2
x = 26 <"
0 0 0 1 1 0 1 0
-x = -26 <"
1 1 1 0 0 1 1 0
2
x = 24 <"
0 0 0 1 1 0 0 0
y = -40 <"
1 1 0 1 1 0 0 0
x + y = -16 <"
1 1 1 1 0 0 0 0
 t
x = 0

x = m " 10c
0.1 d" |m| < 1 c m
c x
x 0 m = 0 c = 0
x = 0.00354
x = 0.354 " 10-2
t t
liczba przyblienie
x x
1
a1 = = 0.166(6) a1 = 0.1667 " 100
6
a2 = 42.5368 a2 = 0.4254 " 102
a3 = 6 042 875 a3 = 0.6043 " 104
a4 = -7.67443 a4 = -0.7674 " 101
µa = |a - a|
|m - m| d" 0.5 " 10-t
a = m " 10c
a
µa = |a - a| = |m " 10c - m " 10c| d" 0.5 " 10-t " 10c
a - a µa
´a = | | =
a |a|
a = m " 10c
a - a 0.5 " 10-t " 10c 0.5 " 10-t " 10c
´a = | | d" d" = 5 " 10-t
a m " 10c 0.1 " 10c
u = 5 " 10-t
a - a
| | d" u
a
Á
a = a(1 + Á)
|Á| d" u
-K -k k = 0.1 " 10-99 K = 0.9999 " 1099
 [-K, K]
K [-k, k]
0 k -k
a =
0.375 " 102 b = 0.225 " 103
0.375
0.225
1875
750
750
0.084375
a " b = 0.8438 " 104
a " b = a " b(1 + Á),
|Á| d" u
 a =
0.357 " 103 b = 0.268 " 104
0.036
0.268
0.304
a + b = 0.304 " 104 Á1 Á2
a + b = a(1 + Á1) + b(1 + Á2)
|Á1|, |Á2| d" u



a " b - a " b a " b - a " b(1 + Á)


= = |Á| d" u


a " b a " b


(a(1 + Á1) " b(1 + Á2))(1 + Á) - a " b

=

a " b


a " b((1 + Á1 + Á2 + Á1 " Á2))(1 + Á) - a " b

= =

a " b
= |(Á1 + Á2 + Á1 " Á2)(1 + Á)| H" 2 " u
2 " u


(a(1 + Á1) + b(1 + Á2)) - (a + b)

d"

a + b
|a| " |Á1| + |b| " |Á2| |a| + |b|
d" d" " u
|a + b| |a + b|
a b
|a|+|b| |a+b|
|a|+|b|
|a+b|
a = 10.0726 b = 10.0789
a = 0.10073 " 102 i b = 0.10079 " 102
a b



a - a 4 " 10-6 " 102


´a = = < 4 " 10-5 d" u(= 5 " 10-5)


a 10.0726


b - b 10-6 " 102

´b = = < 10-5 d" u

b 10.0789


(b - a) - b - a 6.3 " 10-3 - 6 " 10-3

= =
- a) 6.3 " 10-3

(b
0.3 4
= > 4 " 10-2 = " 103 " u
6.3 5
x2 + px + q = 0

-p - p2 - 4q -p + p2 - 4q
x1 = i x1 =
2 2
" = p2 - 4q
p = -6.433 i q = 0.009474.
x1
Ä… = (6.433)2 = 41.38
² = 4q = 0.03790
Å‚ = Ä… - ² = 41.34
"
à = ł = 6.430
Õ1 = -p - Ã = 6.433 - 6.430 = 0.003
Õ1
x1 = = 1.5 " 10-3
2
x1
x1 H" 1.4731 " 10-3
x1
´x1 H" 10-1.
x2
Õ2 = -p + Ã = 6.433 + 6.430 = 12.86
Õ2
x2 = = 6.43
2
x2
x2 H" 6.4313
x2
x1 Õ1
Õ2 x2
x2 x1
x1 " x2 = q

0.009474
x1 = = 0.001473 = 1.473 " 10-3
6.430
´x1 H" 10-4.
p > 0 x1
p < 0 x2
n
Wn(x) = anxn + an-1xn-1 + . . . + a1x + a0,
x2, x3, . . . , xn n - 1
a1x, a2x2, . . . , anxn n
a0 + a1x + . . . + an-1xn-1 + anxn n
2n - 1 n
Pn(x) = anx + an-1
Pn-1(x) = (anx + an-1)x + an-2
 . . .
P1 = P2x + a0
n n
 x S
x S
x S
S
S
x S
x S
S

S
=
S
tail(ogon) head(glowa)


S
=
Q
tailQ headQ

head

x1 x2 x3 xn




" " "
NIL
. . .
head

x1 x2 x3 xn




" " "
NIL
. . .

" " "
NIL
root
x1



" "







x2 x3
" " NIL "







x4 x5 x6
NIL NIL NIL NIL NIL NIL
A
3 71 -4 9
u
?
v
?
A
3 71 -4 9
u
uĆ

"
10 1 0 7
v
?
A
3 71 -4 9
u
uĆ

"
10 1 0 7



v


"
A
3 71 -4 9
u
uĆ

"
10 1 0 7
v
vĆ

"
8 6 2 -3
A
3 71 -4 9
u
vĆ
"
10 1 0 7




v
uĆ




"
8 6 2 -3
A
3 71 -4 9
u
vĆ
"
10 1 0 7




v
uĆ




"
3 71 -4 9
A
3 71 -4 9
u
"


v
uĆ



? 3 71 -4 9
A
3 71 -4 9
u
uĆ

"
6 7 10 4
v
?
? 3 71 -4 9
 v
v
v














 k
n

k1 :
"
k2 k3 k
1
3 ? ?

" "
Nil
k2 :
" " " "
"
? ?

k3 :
"
?
V [k] k k
 n m
O(n + m log(m))
n
O(n)
m
O(m log(m))
m - 1
 m
O(m)
O(m log(m))
k
2k
m 2k d" m k d" log2(m)
log2(m) m
O(m log(m))
 G (V, E) V
E V × V
E
e = (u, v) " E e u
v u v

1 2 3





4 5 6 7



G (V, E) V
E
V {(u, v) : u = v, u, v " V }

E V ×V
(u, v) (v, u)
e = (u, v) " E e
u v u v
u v
1 2 3




4 5 6 7
 v G
G v
v G
G v
v G G v
k u v
G = (V, E) < v0, v1, . . . , vk > v0 = u
vk = v (vi, vi+1) " E i = 0, . . . , k
< v0, v1, . . . , vk > v1, . . . , vk
< v0, v1, . . . , vk >
v0 = vk v1, . . . , vk
u v v u u v

G = (V , E ) G = (V, E) V Ä…" V
E Ä…" E G G E = E )" (V × V )
G = (V, E)
V = {v1, . . . vn} M

1 (vi, vj) " E;
M[i, j] =
0
(vi, vj) G
n O(n2)
k k
A Ak
k
k Ai
i=1
 O(n)
O(n2)
G = (V, E) V = {v1, . . . vn}
vi
vj (vi, vj) " E

" 1 2 7 9
" " " Nil

" 1 4
" Nil

" 2 3 5 6
" " " Nil
A[i] j
(i, j) " E
O(|V |+|E|)






a b a
b








a b a b















a b a b
 G
G
G
G = (V, E)
O(n + m log(m)) |V | = m
|E| = n
"




"
" "




"
"
" "



"
D = (V, E) (v, w) " E v
w w v v w w
v v w v = w w

v
D v
D v v
v
v v
G s
s s
s
G = (V, E) s " V

D = (V , E ) G s

V s G

v " V s v D
s v E
" G = (V, E) s " V
" d Ä„ V
d[v] s v " -1
P [v] v s v Nil
v = s v s
Å„Å‚
ôÅ‚
v
òÅ‚
= v
ôÅ‚
ół
v
v
v
G
v
 1, . . . 9
s 7
v d[v]
s = 7 P [v]
7 v




























"

d P
O(|V |)
O(|V |)
G |E|
2|E|
O(|E|)
G = (V, E)
O(|V | + |E|)
 G = (V, E) s " V ´(u, v)
u v G "
(u, v) " E ´(s, v) d" ´(s, u) + 1
BF S(G, s) ´(s, v) d" d[v] v " V
´(s, v) d" d[v] dla v " V
s
´(s, s) = d[s], ´(s, v) d" " = d[v], dla v " V \ {s}
v
u
´[s, u] d" d[u] v
d[v] := d[u] + 1
d[v] = d[u] + 1 e" ´(s, u) + 1 e" ´(s, v).
v d[v]
BF S
BF S(G, s)
< v1, . . . , vr > v1 vr
d[vr] d" d[v1] + 1
d[vi] d" d[vi+1]
i = 1, . . . , r
 s
vr+1 <
v1, . . . , vr > v1
d[vr+1] := d[v1] + 1
d[vi] d" d[v1] + 1 = d[vr+1]
i = 1, . . . , r d[vr+1] d" d[v1] + 1
BF S
BF S(G, s) v " V
s d[v] = ´(s, v) v " V
v = s s

s v (P (v), v)
v " V s
d[v] e" ´(s, v) = " v

Vk = {v " V : ´(s, v) = k} Vk
k"N
s s
k " N
BF S(G, s)
v " Vk v
v
d[v] k
v = s P [v] Vk-1

v
k = 0 V0 = {s} s
k > 0
Vk-1 v " Vk
 u d[u] P [u]
v1, . . . , vr d[v1] d"
. . . d" d[vr]
d[v] e" k
v
Vk-1 ´(s, v) = k
u " Vk-1 (u, v) " E u
v
u
v
d[v] := d[u] + 1 = k
P [v] := u
v
v
(P [v], v)
s v P [v] " Vk-1
d P BF S(G, s)
D = (VP , EP ) G s
VP = {v " V : P [v] = Nil} *" {s}

EP = {(P [v], v) : v " VP \ {s}}
s
G
" " " "




" " "
" " " " "




" "
" "
" " "



"
" G = (V, E)
" d f P V
P [v] = u v
u
d[v] v
f[v] v
 G = (V, E) GP =
(V, EP ) G
EP = {(P [u], u) : P [u] = Nil}



































 x
d[x]
f[x]
P [x]









kolor P
G
G
u
u
u
O(|V |)
v

|LI(v)| |LI(v)| = O(|E|)
v"V
O(|E|)
G = (V, E)
O(|V | + |E|)
G = (V, E) u, v " V
< d[v], f[v] > < d[u], f[u] >
< d[v], f[v] > < d[u], f[u] > v
u
< d[u], f[u] > < d[v], f[v] > u
v
u, v " V u = v d[u] < d[v]

d[u] > d[v]
d[v] < f[u]
f[u] < d[v]
d[v] < f[u] d[v] u
v u v
u
d[v] v
v
u f[v] < f[u]
d[u] < d[v] < f[v] < f[u].
f[u] < d[v] < d[v], f[v] > < d[u], f[u] >
 v u
G d[u] < d[v] < f[v] < f[u]
G = (V, E) v u
d[u] u u v
Ò! v u
G w u v
GP (V, EP ) d[u] < d[w] w
d[u] u
Ð! d[u] u
u v v u
G
u
v
u w v
f[w] d" f[u] w u v
d[u] (w, v) " E v u
w
d[u] d" d[v] < f[w] d" f[u].
< d[v], f[v] > < d[u], f[u] >
v u
 G = (V, E)
u v (u, v) " E
" G = (V, E)
" V
(u, v) " E u v
x - y x
y




G
f[u] u
 G
G = (V, E) u, v " V u v
u v G <"
V
u <" v wiw gdy u v i v u
u, v " V <"
<" G GT = (V, ET )
G = (V, E)
(u, v) " ET iff (v, u) " E
G GT
" G = (V, E)
" G
G
f
GT
GT
f
GT
G
 G GT DF S
GT DF S
f
GT
G GT
G DF S(G)






























G








GT DF S(GT )






























GT







G = (V, E)
 S G
S
S G u, v " S
w " V u v u w
w v u <" v u v v u
u w w u w <" u u w
S
w u v S
u v S
S G r
S G
v S d[r] r
S r, v " S r v
S
v
r G v
S r S
G
f
G Õ : V V Õ(u) = w
u w f[w]
u
u w oraz f(w) = max{f(v) : u v}.
Õ(u) u
u, v " V
f(u) d" f(Õ(u))
u v f(Õ(u)) e" f(Õ(v))
Õ(u) = ÕÕ(u)
 u u Õ(u) w
u w f(w) f(u) d" f(Õ(u))
f(Õ(u)) = max{f(w) : u w}
f(Õ(v)) = max{f(w) : v w}.
u v
{f(w) : u w} ‡" {f(w) : v w}.
f(Õ(u)) = max{f(w) : u w} e" {f(w) : v w} = f(Õ(v)).
f(Õ(u)) d" f(ÕÕ(u)).
u Õ(u)
f(Õ(u)) e" f(ÕÕ(u)).
f(Õ(u)) = f(ÕÕ(u)).
f
Õ(u) = ÕÕ(u).
Õ(u) u " V u
G
u = Õ(u) u = Õ(u)

Õ(u) d(u) Õ(u)
u Õ(u) Õ(u)
u G Õ(u)
Õ(u)
f(Õ(u)) < d(u) < f(u)
Õ(u)
Õ(u) d(u)
 d(u) u Õ(u)
d(u) u Õ(u)
Õ(u)
u G
d(u) < d(Õ(u)) < f(Õ(u)) < f(u)
t
u Õ(u)
u . . . t . . . Õ(u)

t d(u)
d(t) < d(u)
t Õ(u) Õ(u) t
G f(Õ(u)) < f(t) u t
Õ(u)
Õ(u) d(u)
u " V u Õ(u)
G
Õ(u) u Õ(u) Õ(u) u
u <" Õ(u)
u, v " V u v
G Õ(u) = Õ(v)
Ð!
Ò! u v u v v u
f(Õ(u)) = f(Õ(v))
f Õ(u) = Õ(v)
G
 GT
GT GT G
DF S(GT )
r T
DF S(GT )
r = Õ(r)

f f(r) < f(Õ(r)) Õ(r)
r
r = Õ(r)
S(r) = {w " V : Õ(w) = r}
r v
T v " S(r)
Ð! v r
DF S(GT ) r
T v T
Ò! w " V
f(Õ(w)) > f(r)
f(Õ(w)) < f(r)
w T
r T w
Õ(w)
w T r w GT
w r G Õ(w)
w r f(Õ(w)) < f(r)
 G = (V, E)
W : E R+ G
G
(u, v) " E W (u, v)
u v u v
" G = (V, E)
W
" G = (V, T )
T Ä…" E T

W (T ) = W (e)
e"T
T := "
V {v}
G
(u, v) " E
find(u) = find(v)

T := T *" {(u, v)}
union(u, v) u
v
 T |V |
E O(|E| log(|E|)
E
O(|E| + |V |)
|V |
O(|E| + |V | log(|V |)
|E| e" |V | - 1
G = (V, E) O(|E| log(|E|)
























(4, 2), (5, 3), (2, 3), (3, 6), (4, 8), (4, 7), (8, 9), (4, 1).
 G = (V, E) V
(S, V \ S) S Ä…" V (u, v)
(S, V \S) S V \S (u, v) " E
(S, V \ S) (u, v)
A Ä…" E
(S, V \ S) A
A (S, V \ S) (u, v) " E
A A *" {(u, v)}
G = (V, E)
W : E R+ A Ä…" E
G (S, V \ S) A (u, v) " E
(S, V \ S) (u, v)
A
(S, V \ S) A (u, v) " E
(S, V \ S) (V, T )
A Ä…" T
A *" {(u, v)}
(u, v) " T (u, v) " T

T Ä…" E A *" {(u, v)} Ä…" T (V, T )
(V, T )
u v (V, T ) (u, v) (S, V \S)
(V, T ) (x, y) " T
(S, V \ S) (V, T ) (V, T \ {x, y})

(u, v) T =

(T \ {(x, y)}) *" {(u, v)} (V, T )

W (T ) = W (T ) T

W (T ) d" W (T )


W (T ) - W (T ) = W (e) - W (e) = W (u, v) - W (x, y) d" 0

e"T e"T
(u, v) (x, y)

(S, V \ S) (u, v) W (T ) e" W (T )
 G = (V, E)
W : E R+ A Ä…" E
G C GA = (V, A)
(u, v) " E (C, V \ C) (u, v)
A
C GA (C, V \C)
A
 O(ln n)
O(n)
O(n ln n)
O(|V | + |E|)
O(|V | + |E|)
O(n12)
O(n100)
3 4
Q Ä…" I × S
I S
(i, s) " Q s
i
I = {(G, x, y) : G - graf , x, y " V (G)},
S ((G, x, y), s) "
QNS s G x y
 Q Ä…" I × S S = {0, 1} Q
QNS
QDNS QDNS(G, x, y, k) = 1
G x y k
I
| - | : I - N
i " I |i| " N
Q
Q(i) = 1 i " I
x0, . . . , xl
k G x y
HAM
G HAM(G) = 1 G " HAM G
I Q Ä…" I W
A Q
i " Q w " W A(i, w) = 1
Q Ä…" I
 W
A c > 0
Q(i) = 1 w " W
|w| = O(|i|c) A(i, w) = 1
Q Ä…" I I \ Q Ä…" I
Graf
HAM " NP
k - Kolor Ä…" Graf G " k - Kolor
G k
k - Kolor " NP
k - Klika Ä…" Graf G " k - Klika k
G
k - Klika " NP
I SAT Ä…"
I Õ " SAT v Õ
v(Õ) = 1 x (" Źx x (" (y z) " SAT x '" Źx " SAT
SAT " NP
I T AUT Ä…" I
Õ " T AUT v Õ
v(Õ) = 1 T AUT " co - NP
I = Graf × Graf GIzo Ä…" I (G, G ) " GIzo
G G GIzo " NP
k - P W Ä…" Graf G " k - P W
k W
(i, j) G i " W j " W k - P W " NP
P RIME Ä…" N n " P RIME n
P RIME " P
3 - CNF - SAT " NP
 Q Ä…" I
Q Ä…" I Q d"P Q
f : I - I
i " Q iff f(i) " Q .
Q d"P Q Q Q Q
Q
Q d"P Q
Q " P Q " P
Q " P Q " P
k-Kolor d"P SAT
G = (V, E) V = {1, . . . , n}
ÕG
G ÕG G
k
ÕG
xij dla i = 1, . . . , n, j = 1, . . . , k.
xi,j i
j
n k


Õ1 = xi,j
i=1 j=1
k
n k



Õ2 = Ź(xi,j '" xi,j )
i=1 j,j =1,j=j

k
k



Õ3 = Ź (xi,j '" xi ,j)
j=1
(i,i )"E
 ÕG = Õ1 '" Õ2 '" Õ3 ÕG
G
ÕG W i V
j W (xi,j = 1 i = 1, . . . , n
j = 1, . . . , k G k
C : V {1, . . . , k} G
k W W (xi,j = 1
C(i) = j i = 1, . . . , n j = 1, . . . , k ÕG
ÕG = Õ1 '" Õ2 '" Õ3
SAT d"P k-Kolor
Q Q "
NP Q d"P Q Q Q
Q " NP
 HAM
k - Kolor
k - Klika
SAT
GIzo
k-P W
3 - CNF - SAT
ö
" s1 s2
" true s1
s1 s2
false
Å„Å‚
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚
òÅ‚
=
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚
ół
 true
false
" G = (V, E)
" W Ä…" V
(i, j) " E i " W j " W
 W
(i, j) " E i " W j " W
W
E G
F (u, v)
F
F u v
300
w
n w
n n w
w n
NW D(w, n) > 0 n
w
n 100
p q (p - 1) + (q - 1)
1
10100
w < n wn-1 a"n 1
n
a"n n
 1 < w < n - 1 wn-1 a"n 1
w2 a"n 1 w 1
n n w
n
n
1 n
w
n
wn-1 a"n 1
wn-1 mod n
1 -1 1
wn-1 mod n
d = we oraz e = (bk, . . . , bi+1)2
w n
1
2
k
e = 2i bj · 2j
j:=i+1
 100
1 n n
n
1
n
2100
1
1 -
2100
n
n
Zn {0, . . . , n - 1}
n
n
Zn
2
p(x1, . . . , xn) q(x1, . . . , xn)
n a1, . . . , an
p(a1, . . . , an) q(a1, . . . , an)
" G = (V, E) V = {1, . . . , 2n}
(i, j) " E 1 d" i d" n n < j d" n
" n E Ä…" E
{1, . . . , n}
{n+1, . . . , 2n} E
A (n × n)
0

xi,j (i, n + j " E)
ai,j =
0
i, j = 1, . . . , n
d(< xi,j >(i,n+j)"E)
A
ri,j (i, n + j) " E) d
w = d(< ri,j >(i,n+j)"E)
w = 0

w = 0
d(< xi,j >(i,n+j)"E)
0
d(< xi,j >(i,n+j)"E
) 0
d(<
xi,j >(i,n+j)"E)
(n×n)

detA = sgn(Ã) · x1,Ã(1) · . . . · xn,Ã(n)
Ã"Sn
Sn {1, . . . , n} sgn(Ã)
à d(< xi,j >(i,n+j)"E)
à " Sn
ai,Ã(i) = xi,Ã(i) {(1, n +
Ã(1)), . . . , (n, n + Ã(n))} E
(n×n)
G = (V, E)






















A
îÅ‚ Å‚Å‚
0 x1,2 x1,3 0
ïÅ‚ śł
x2,1 0 0 0
ïÅ‚ śł
A = ïÅ‚ śł
ðÅ‚ 0 x3,2 0 x3,4 ûÅ‚
0 0 x3,4 x4,4
d(< xi,j >(i,n+j)"E) = detA = x1,2 · x2,1 · x3,4 · x4,3 + x1,3 · x2,1 · x3,2 · x4,4
{(1, 6), (2, 5), (3, 8), (4, 7)}
{(1, 7), (2, 5), (3, 6), (4, 8)}.

detA = sgn(Ã) · x1,Ã(1) · . . . · xn,Ã(n)
Ã"Sn
 (n×n)
n
O(n3)
C = A · B
O(nlg 7 H" O(n2.81)

A (n × n) b = [b1, . . . , bn]
= [x1, . . . , xn] n
x
 n
T
A · T = b .
x
detA = 0

A T = A-1 · T
x b
A-1
(n × n) L U P
L · U = P · A
L
L
U U
P
P
îÅ‚ Å‚Å‚
1 2 3
ïÅ‚ śł
A = 2 4 2
ðÅ‚ ûÅ‚
1 1 2
(3 × 3)
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
1 0 0 1 0 0 1 2 3
ïÅ‚ śł ïÅ‚ śł ïÅ‚ śł
P = 0 0 1 L = 1 1 0 U = 0 -1 -1
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
0 1 0 2 0 1 0 0 -4
L · U = P · A.
A
P (n×n) Q (n×k)
P · Q Q
Ä„ {1, . . . , n} pi,Ä„(i) = 1
1, . . . , n i P · Q Ä„(i) Q
P
Ä„(1) = 1
Ä„(2) = 3 Ä„(3) = 2
(n × n) P
-1 T T
Rn P = P P
P

(n×n) A b

A· T = bT
x
T
A · T = b
x
P · A · T = P · T
x b

x
-1 -1
T
A · T = P · P · A · T = P · P · T = b
x x b
P · A = L · U
x
L · U · T = P · T .
x b
L · T = P · T U · T = T
y b x y
P · A · T = L · U · T = L · T = P · T .
x x y b

x
îÅ‚ Å‚Å‚
1 2 3
ïÅ‚ śł
A = 2 4 2
ðÅ‚ ûÅ‚
1 1 2
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
1 0 0 1 0 0 1 2 3
ïÅ‚ śł ïÅ‚ śł ïÅ‚ śł
P = 0 0 1 L = 1 1 0 U = 0 -1 -1
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
0 1 0 2 0 1 0 0 -4

b = [2, 1, 3]
L · T = P · T
y b
Å„Å‚
ôÅ‚
y1 = 2
òÅ‚
y1 + y2 = 3
ôÅ‚
ół
2y1 + y3 = 1
y1 = 2
y2 = 3 - 2y1 = 1
y3 = 1 - 3y1 + y2 = -3
U · T =
x y
Å„Å‚
ôÅ‚
x1 + 2x2 + 3x3 = 2
òÅ‚
-x2 - x3 = 1
ôÅ‚
ół
-4x3 = -3
x3 = -3/ - 4 = 0.75
x2 = (1 + x3)/ - 1 = -1.75
x1 = (2 - 2x2 - 3x3)/1 = 3.25
{1, . . . , n} P
 (n × n) A
A
îÅ‚ Å‚Å‚

a1,1 . . . a1,n
a1,1 w

ïÅ‚ śł
A = . . . . . . . . . =
ðÅ‚ ûÅ‚
T A
v
an,1 . . . an,n
w (n - 1)
v
A a1,1 = 0




a1,1 w 1 0
a1,1 w
A = = ·
T A T /a1,1 In-1 T A - T · w/a1,1
v v 0 v

0 (n - 1) T · w/a1,1
v
(n - 1, n - 1) T w
v
a1,1 A
A - T · w/a1,1
v
(n - 1, n - 1) L
U
A - T · w/a1,1 = L · U
v
 A


a1,1 w

1 0
A = ·
T /a1,1 In-1 T A - T · w/a1,1
v 0 v


a1,1 w

1 0
= · =
T /a1,1 In-1 T L · U
v 0


a1,1 w

1 0
= · =
T /a1,1 L T U
v 0
= L · U
0
A
0 0
A
a1,1
A
E(i)+c(k) (n × n)
In 0 k i
c
 A
a1,1
a2,2
ai,i ak,i A
E(i)-ak,i/ai,i(k)
A G
E(i)+c(k) A
U
U = G · A L · U = A L = G-1 L
A
0
P
0
0
A
k A
|ak,1| = max{|al,1| : i = 1, . . . , k}
A |ak,1| > 0 Q
k Q · A

ak,1 w

Q · A =
T A
v
A



ak,1 w 1 0
ak,1 w
A = = ·
T A T /ak,1 In-1 T A - T · w/ak,1
v v 0 v
A - T · w/ak,1
v

P · (A - T · w/ak,1) = L · U
v


1 0
P =
T P · Q
0
 A


ak,1 w

1 0
P · A = · = L · U

P · T /ak,1 L T U
v 0
L U P
A


1 0
P · A =
T P · Q · A =
0


ak,1 w

1 0 1 0
= · =
T P ·
v 0 v
0 T /ak,1 In-1 T A - T · w/ak,1


ak,1 w

1 0
= ·

T A T w/ak,1 =
P · T /ak,1 P 0 - v ·
v


ak,1 w

1 0
= · =

P · T /ak,1 In-1 T P · (A - T · w/ak,1)
v 0 v


ak,1 w

1 0
= · =

P · T /ak,1 In-1 T L · U
v 0


ak,1 w

1 0
= · =

P · T /ak,1 L T U
v 0
= L · U
A
 (n×n) A
A n
i = 1, . . . , n i
ei ei
Rn Xi
Rn
A · Xi =
ei
i = 1, . . . , n
A-1 = [X1, . . . , Xn].
A
A
L · U = P · A
 A L
detL = 1 detP 1 -1
à P U
n
detU = L[i, i]
i=1
n

detA = sgn(Ã) · L[i, i].
i=1
Ã
0 A
detA = 0
O(f(n))
&!(f(n))
Åš(f(n))