Lecture 04

background image

Jagiellonian University

Theoretical

Computer Science

Matematyka Dyskretna

Wykład 04

WSZIB

Edward Szczypka

szczypka@tcs.uj.edu.pl

zima 2013

Edward Szczypka

Matematyka Dyskretna

1 / 1

background image

Jagiellonian University

Theoretical

Computer Science

Co dzisiaj

Dzisiejszy wykład

Edward Szczypka

Matematyka Dyskretna

2 / 1

background image

Jagiellonian University

Theoretical

Computer Science

Algorytmy

spis

Edward Szczypka

Matematyka Dyskretna

3 / 1

background image

Jagiellonian University

Theoretical

Computer Science

Algorytmy

Poj ˛ecie Algorytmu

Algorytm

to sformalizowany sposób post ˛epowania przy rozwi ˛

azywaniu jakiego´s problemu.

Klasyczny przykład – przepisy kulinarne, instrukcje obsługi rozmaitych urz ˛

adze ´n

Algorytm:

pobiera dane wej´sciowe
wykonuje pewne (z góry przewidziane) operacje
daje dane wyj´sciowe

Pojecie danych mo˙zna rozumie´c bardzo szeroko

Algorytm powinien działa´c

poprawnie – tzn. zwraca´c zawsze poprawna odpowiedz
sko ´nczenie długo – nie powinien si ˛e p ˛etli´c

odpowiedz powinien zwraca´c w mo˙zliwie krótkim
anga˙zuj ˛

ac mo˙zliwie mało zasobów – np. pami ˛eci

Edward Szczypka

Matematyka Dyskretna

4 / 1

background image

Jagiellonian University

Theoretical

Computer Science

Algorytmy

Algorytm vs Program

Program

to algorytm zapisany w jakims jezyku (programowania).

program ma zwykle postac ciagu polecen, które nalezy wykonywac po kolei (chyba, ze w
samym programie przewidziana jest zmiana kolejnosci)

ten sam algorytm mozna zapisac w róznych jezykach, zwykle na wiele sposobów

Przykład 1 Algorytm ustawiania zadanej stacji w radiu:

1) Dowiedz sie, na jakiej czestotliwosci nadaje Twoja ulubiona stacja. (To sa dane wejsciowe.)

2) Nacisnij piaty guzik w siódmym rzedzie.

3) Wpisz czestotliwosc na klawiaturze.

4) Nacisnij zielony guzik pod fioletowa gałka.

5) Teraz powinno grac. (To jest rezultat - dane wyjsciowe.)

Edward Szczypka

Matematyka Dyskretna

5 / 1

background image

Jagiellonian University

Theoretical

Computer Science

Algorytmy

Algorytm vs Program

Rozwiazywanie równania kwadratowego:

Oznacz współczynniki równania symbolami a, b, c. (Dane wejsciowe.)

Policz ∆ = b

2

4ac.

Je´sli ∆ < 0, to koniec – nie ma pierwiastków rzeczywistych.

Je´sli ∆ = 0, to policz x

1

=

x

2

=

b/2a.

Je´sli ∆ > 0, to policz x

1

=

b+

2a

i x

2

=

b

2a

.

Program realizuj ˛

acy ten algorytm zapisany w pseudo-Pascalu:

read(a, b, c)

delta:=b*b-4*a*c
if delta<0 then

write(’Nie ma pierwiastków rzeczywistych’)

halt

if delta=0 then

x1:=-b/(2*a)
x2:=-b/(2*a)

if delta > 0 then

x1:=(-b+sqrt(delta))/(2*a)
x2:=(-b-sqrt(delta))/(2*a)

write(x1, x2)

Edward Szczypka

Matematyka Dyskretna

6 / 1

background image

Jagiellonian University

Theoretical

Computer Science

Algorytmy

P˛etle

Prawie kazdy wiekszy algorytm musi powtarzac pewne obliczenia, az do uzyskania jakiegos
rezultatu.

Taka sytuacja nazywana jest petla.

Typowa (i jedyna potrzebna tutaj) petla to:

WHILE

warunek DO polecenie

Taka petla:

sprawdza podany warunek
i jesli jest spełniony, to wykonuje podane polecenie
nastepnie ponownie sprawdza warunek
(wartosci dla których warunek jest sprawdzany mogły ulec zmianie przez wykonanie
polecenia)
i jesli jest spełniony, to wykonuje podane polecenie
nastepnie ponownie sprawdza warunek
i jesli jest spełniony, to wykonuje podane polecenie
. . .
. . .

Wyjscie z petli nastepuje wiec wtedy, gdy warunek nie jest spełniony

bo albo w ogóle nie był spełniony,
albo przestał byc spełniony na skutek wykonywania polecenia

Edward Szczypka

Matematyka Dyskretna

7 / 1

background image

Jagiellonian University

Theoretical

Computer Science

Algorytmy

P˛etle - graficznie

Edward Szczypka

Matematyka Dyskretna

8 / 1

background image

Jagiellonian University

Theoretical

Computer Science

Algorytmy

P˛etle – przykłady

Przykład 2 Wypisanie liczb od 1 do 100:

write(’Zaczynamy’)

x := 1

while x <= 100 do

write(x)

x := x + 1

write(’I to by było na tyle’)

W tym programie nie ma danych wej´sciowych.

Dane wyj´sciowe to wypisane liczby 1, 2, . . . , 100 (oraz ew. komentarze tekstowe).

Bardzo typowe jest podstawienie x := x + 1. Jego sens jest taki: zwi ˛eksz x o jeden.

Przykład 3 A co robi program?

read(a)

write(’Zaczynamy’)

x := 1

while x <= a do

x := x + 1

write(x)

write(’I to by było na tyle’)

Edward Szczypka

Matematyka Dyskretna

9 / 1

background image

Jagiellonian University

Theoretical

Computer Science

Algorytmy

P˛etle - problemy

P˛etle s ˛

a bardzo silnym narz ˛edziem programistycznym, ale mog ˛

a by´c powodem wielu komplikacji.

Istotne pytania to:

1

Czy algorytm/procedura zako ´nczy si ˛e?

2

Czy po zako ´nczeniu daje poprawne wyniki?

3

Jak długo trwa wykonanie procedury?

4

Ile pami ˛eci zu˙zywa procedura?

Do analizowania dwu pierwszych problemów słu˙z ˛

a tzw.

NIEZMIENNIKI P ˛

ETLI

.

Edward Szczypka

Matematyka Dyskretna

10 / 1

background image

Jagiellonian University

Theoretical

Computer Science

Algorytmy

P˛etle - Niezmienniki

W p ˛etli WHILE W DO S

W

jest warunkiem – formuła logiczna, od spełnienia której zale˙zy wykonywanie p ˛etli

S

jest lista czynno´sci wykonywanych w p ˛etli

NIEZMIENNIKIEM

p ˛etli WHILE W DO S jest

warunek (formuła logiczna) P taki, ze:

je´sli W P zachodzi przed wykonaniem czynno´sci S
to P zachodzi po wykonaniu czynno´sci S.

U ˙

ZYTECZNA OBSERWACJA:

Je´sli:

P jest niezmiennikiem p ˛etli WHILE W DO S

P jest spełniony przy wej´sciu w te p ˛etle

to:

w ka˙zdym takcie p ˛etli warunek P jest spełniony

przy wyj´sciu z p ˛etli warunek P jest spełniony, a W juz nie.

Edward Szczypka

Matematyka Dyskretna

11 / 1

background image

Jagiellonian University

Theoretical

Computer Science

Algorytmy

P˛etle – Niezmienniki – Graficznie

Edward Szczypka

Matematyka Dyskretna

12 / 1

background image

Jagiellonian University

Theoretical

Computer Science

Algorytmy

P˛etle – Liczenie Silni

INPUT: a<= 0

OUTPUT: s = a!

INITIAL:

s:=1

x:=1

WHILE x<a DO x:=x+1

s:=s*x

END

Edward Szczypka

Matematyka Dyskretna

13 / 1

background image

Jagiellonian University

Theoretical

Computer Science

Algorytmy

P˛etle - Liczenie Silni

Edward Szczypka

Matematyka Dyskretna

14 / 1

background image

Jagiellonian University

Theoretical

Computer Science

Algorytmy

P˛etle – Liczenie Silni – Analiza

Potrzebujemy wykaza´c, ˙ze po wyj´sciu z p ˛etli rzeczywi´scie s = a!. Najpierw pokazujemy, ze
niezmiennikiem petli jest warunek (s = x ! i x ¬ a): Skoro jest on spełniony przed wej´sciem w
p ˛etle, to mamy:

x

stare

<

a

s

stare

=

x

stare

!

i x

stare

¬ a

Czynno´sci p ˛etli zmieniaj ˛

a warto´sci x i s na:

x

nowe

=

x

stare

+

1

s

nowe

=

s

stare

x

nowe

=

s

stare

(

x

stare

+

1)

sk ˛

ad s

nowe

=

s

stare

(

x

stare

+

1) = x

stare

!(

x

stare

+

1) = (x

stare

+

1)! = x

nowe

!

Nadto, skoro x

stare

<

a

to

x

nowe

=

x

stare

+

1 ¬ a.

Z kolei przy wyj´sciu z p ˛etli mamy:

x > a

s = x ! i x ¬ a

co daje x = a oraz s = x ! = a!.

Edward Szczypka

Matematyka Dyskretna

15 / 1

background image

Jagiellonian University

Theoretical

Computer Science

Algorytmy

P˛etle – Liczenie Silni – inne liczenie Silni

INPUT: a <= 0

OUTPUT: s = a!

INITIAL:

s:=1

x:=a

WHILE x>0 DO s:=s*x

x:=x-1

END

Edward Szczypka

Matematyka Dyskretna

16 / 1

background image

Jagiellonian University

Theoretical

Computer Science

Algorytmy

P˛etle – Liczenie Silni – inne liczenie Silni

Uzasadnij, ze:

wyra˙zenie podane w nawiasie jest rzeczywi´scie niezmiennikiem p ˛etli,

oraz gwarantuje poprawno´s´c wyniku tzn., ze przy wyj´sciu z p ˛etli s = a!.

Edward Szczypka

Matematyka Dyskretna

17 / 1

background image

Jagiellonian University

Theoretical

Computer Science

Algorytmy

P˛etle i niezmienniki – Problem Stopu

INPUT: a <= 0

OUTPUT: ?

INITIAL: x:=a

WHILE x<>8 DO PRINT x^2

x:=x+2

END

Co robi powy˙zsza procedura i kiedy si ˛e zatrzymuje (dla jakich warto´sci a)?

Zauwa˙z, ze kolejno´s´c instrukcji w prostok ˛

acie jest istotna!

Edward Szczypka

Matematyka Dyskretna

18 / 1

background image

Jagiellonian University

Theoretical

Computer Science

Algorytmy

P˛etle i niezmienniki – Nierozwi ˛

azany Problem Stopu

INPUT: a >= 0

OUTPUT: ?

INITIAL: x:=a

WHILE x<>1 DO

IF x jest parzyste THEN

x:=x/2

ELSE

x:=3*x+1

END

Narysuj schemat blokowy tej procedury. Spróbuj znale´z´c niezmienniki p ˛etli. Spróbuj uzasadni´c,

˙ze zawsze si ˛e zatrzyma – na jakie kłopoty natrafiasz?

Ta procedura wygl ˛

ada na do´s´c prosta,

ale . . .

do dzi´s nie wiadomo, czy zawsze si ˛e zatrzymuje . . .

Edward Szczypka

Matematyka Dyskretna

19 / 1

background image

Jagiellonian University

Theoretical

Computer Science

Algorytmy

P˛etle i niezmienniki – dzielenie z reszt ˛

a

INPUT: liczby naturalne a >= 0, b > 0

OUTPUT: liczby naturalne q i r takie, ze a = qb + r oraz 0 <= r < b

INITIAL:

q:=0

r:=a

WHILE r>=b DO

r:=r-b

q:=q+1

END

Edward Szczypka

Matematyka Dyskretna

20 / 1

background image

Jagiellonian University

Theoretical

Computer Science

Algorytmy

P˛etle i niezmienniki – dzielenie z reszt ˛

a – analiza

Poka˙zemy, ze niezmiennikiem jest warunek:

0 ¬ r

i a = qb + r

Wtedy, przy wyj´sciu z p ˛etli mamy:

r < b

0 ¬ r i a = qb + r

czyli dokładnie nało˙zone przez nas warunki: a = qb + r oraz 0 ¬ r < b.
Spełnienie niezmiennika przy wej´sciu w p ˛etle oznacza, ˙ze:

0 ¬ r

stare

oraz a = q

stare

· b + r

stare

Z kolei przebieg p ˛etli zmienia warto´sci r i q na:

r

nowe

=

r

stare

b

q

nowe

=

q

stare

+

1

sk ˛

ad mamy:

q

nowe

· b + r

nowe

= (

q

stare

+

1) · b + r

stare

b = q

stare

· b + b + r

stare

b = q

stare

· b + r

stare

=

a

Nadto, skoro czynno´sci p ˛etli wykonuj ˛

a si ˛e, to r

stare

>

b sk ˛

ad r

nowe

=

r

stare

b > b b = 0.

Edward Szczypka

Matematyka Dyskretna

21 / 1

background image

Jagiellonian University

Theoretical

Computer Science

Algorytmy

P˛etle i niezmienniki – szybkie pot ˛egowanie

INPUT: liczby naturalne a,n >= 0

OUTPUT: liczby naturalna b=a^n

INITIAL:

b:=1

x:=a

i:=n

WHILE i>0 DO

IF i jest nieparzyste THEN

b:=b*x
i:=(i-1)/2

ELSE

i:=i/2

x:=x*x

END

Narysuj schemat blokowy tego algorytmu.
Wykaz, ze niezmiennikiem p ˛etli jest x

i

· b = a

n

.

U˙zyj tego faktu do pokazania, ze ta procedura działa poprawnie.

Jaki inny warunek nale˙zy w tym celu umie´sci´c w niezmienniku?

Edward Szczypka

Matematyka Dyskretna

22 / 1

background image

Jagiellonian University

Theoretical

Computer Science

Indukcja

spis

Edward Szczypka

Matematyka Dyskretna

23 / 1

background image

Jagiellonian University

Theoretical

Computer Science

Indukcja

Liczby Naturalne – zasada indukcji

Liczby naturalne s ˛

a bardzo wa˙zne w praktyce programistycznej ˝

O s ˛

a u˙zywane do

kodowania (implementowania) danych,

adresowania pami ˛eci,

taktowania programów,

Jedna z podstawowych ich własno´sci jest to, ˙ze do ka˙zdej z nich mo˙zna ¯

ddoj´s´c ˝u zaczynaj ˛

ac od

zera i dodaj ˛

ac 1 odpowiednio wiele razy. Oznacza to, ze

jesli: A N jest jakim´s zbiorem liczb naturalnych,

– w którym jest zero

tzn. 0 Z

– wraz z pocz ˛

atkiem ka˙zdego "kroku"

tzn. k A k + 1 A

jest w nim i jego koniec

to: A zawiera juz w sobie WSZYSTKIE liczby naturalne, tzn. A = N.

Edward Szczypka

Matematyka Dyskretna

24 / 1

background image

Jagiellonian University

Theoretical

Computer Science

Indukcja

Zasada indukcji – Przykłady

Przykład 1 Niech zbiór Z składa si ˛e z tych liczb naturalnych n, dla których suma liczb

naturalnych nie przekraczaj ˛

acych n wynosi

n+a

2

, tzn. spełniaj ˛

acych

0 + 1 + 2 + . . . + n =

n(n + 1)

2

Czy Z = N? tzn. czy wszystkie liczby naturalne maja powy˙zsza własno´s´c? Oczywi´scie 0 Z , bo
suma liczb naturalnych nie przekraczaj ˛

acych zera to 0 =

0(0+1)

2

Nadto, gdy k Z , tzn.

0 + 1 + 2 + . . . + k =

k (k + 1)

2

to, badaj ˛

ac, czy k + 1 Z rozwa˙zamy sum ˛e

0 + 1 + 2 + . . . + k + (k + 1)

=

(

1 + 2 + 3 + . . . + k ) + (k + 1)

=

k (k + 1)

2

+ (

k + 1) =

k (k + 1) + 2(k + 1)

2

=

(

k + 1)(k + 2)

2

=

(

k + 1)((k + 1) + 1)

2

co ´swiadczy o tym, ˙ze k + 1 Z .

Edward Szczypka

Matematyka Dyskretna

25 / 1

background image

Jagiellonian University

Theoretical

Computer Science

Indukcja

Zasada indukcji – Przykłady

Przykład 2

Z =

n

n N : 0

2

+

1

2

+

3

2

+ . . . +

n

2

=

n(n + 1)(2n + 1)

6

o

Je´sli poka˙zemy, ze Z = N to dostaniemy ładny wzór na sum ˛e kolejnych kwadratów

Oczywi´scie 0 Z ,
Nadto, gdy k Z , to aby stwierdzi´c czy k + 1 jest w Z rozwa˙zamy sum ˛e

0

2

+

1

2

+

2

2

+ . . . +

k

2

+ (

k + 1)

2

=

(

0

2

+

1

2

+

2

2

+ . . . +

k

2

) + (

k + 1)

2

=

k (k + 1)(2k + 1)

6

+ (

k + 1)

2

=

k (k + 1)(2k + 1)

6

+ (

k + 1)

2

=

k (k + 1)(2k + 1) + 6(k + 1)

2

6

=

(

k + 1)(k (2k + 1) + 6(k + 1))

6

=

(

k + 1)(2k

2

+

7k + 6)

6

=

(

k + 1)((k + 2)(2k + 3))

6

=

(

k + 1)((k + 1) + 1)(2(k + 1) + 1)))

6

co ´swiadczy o tym, ˙ze k + 1 Z .

Edward Szczypka

Matematyka Dyskretna

26 / 1

background image

Jagiellonian University

Theoretical

Computer Science

Indukcja

Zasada indukcji – Przykłady

Przykład 2 Liczenie sumy pot ˛eg kolejnych liczb naturalnych ma bezpo´sredni zwi ˛

azek z praktyka

programistyczna.
Je´sli dla danych wielko´sci k wykonanych musi by´c k

s

operacji, a w programie jest p ˛etla

wykonuj ˛

aca te operacje dla k = 0, 1, 2, 3, . . . az do n, to ł ˛

acznie wykonanych jest Σ

n
k =0

k

s

operacji

Widzieli´smy ju˙z, ˙ze:

Σ

n
k =0

k

=

n(n + 1)

2

Σ

n
k =0

k

2

=

n(n + 1)(2n + 1)

6

Edward Szczypka

Matematyka Dyskretna

27 / 1

background image

Jagiellonian University

Theoretical

Computer Science

Indukcja

Zasada indukcji – Sumowanie pot ˛eg liczb naturalnych

Zadanie 3 Poka˙z, ˙ze:

Σ

n
k =0

k

3

=

n

2

(

n + 1)

2

2

Σ

n
k =0

k

4

=

n(n + 1)(2n + 1)(3n

2

+

3n 1)

30

Σ

n
k =0

k

5

=

n

2

(

n + 1)

2

(

2n

2

+

2n 1)

12

Σ

n
k =0

k

4

=

n(n + 1)(2n + 1)(3n

4

+

6n

3

3n + 1)

42

Σ

n
k =0

k

7

=

n

2

(

n + 1)

2

(

3n

4

+

6n

3

n

2

4n + 2)

24

Σ

n
k =0

k

8

=

n(n + 1)(2n + 1)(5n

6

+

15n

5

+

5n

4

15n

3

n

2

+

9n 3)

90

Edward Szczypka

Matematyka Dyskretna

28 / 1

background image

Jagiellonian University

Theoretical

Computer Science

Indukcja

Zasada indukcji – Sumowanie pot ˛eg liczb parzystych

Czasem sumujemy tylko co druga liczb ˛e.
Oczywi´scie sumowanie dla liczb parzystych jest łatwiejsze, bo na przykład:

Σ

n
k =0

2k = 2Σ

n
k =0

k = k (k + 1)

Σ

n
k =0

(

2k )

2

=

n
k =0

k =

2n(n + 1)(2n + 1)

3

Σ

n
k =0

(

2k )

3

=

n
k =0

k = 2n

2

(

n + 1)

2

Zadanie 4 Policz;

Σ

n
k =0

(

2k )

4

=

?

Σ

n
k =0

(

2k )

5

=

?

Σ

n
k =0

(

2k )

6

=

?

Σ

n
k =0

(

2k )

7

=

?

Σ

n
k =0

(

2k )

8

=

?

Edward Szczypka

Matematyka Dyskretna

29 / 1

background image

Jagiellonian University

Theoretical

Computer Science

Indukcja

Zasada indukcji – Sumowanie pot ˛eg liczb nieparzystych

Przykład 5 A ile wynosi suma kolejnych liczb nieparzystych;

Σ

n
k =1

(

2k 1) =?

Oczywi´scie

Σ

n
k =1

(

2k 1) = 2

X

k = 1nk

X

k = 1n1 = 2

n(n + 1)

2

n = n(n + 1) n = n

2

Przykład 6 Łatwo sprawdzi´c, ze wzór

Σ

n
k =1

(

2k 1)

2

=

n(4n

2

1)

3

zachodzi dla n = 0.
Nadto

Σ

n+1
k =1

(

2k 1)

2

=

X

k = 1n(2k 1)

2

+ (

2(n + 1) + 1)

2

=

n(4n

2

1)

3

+

3(2n + 1)

2

3

=

4n

3

+

12n

2

+

11n + 3

3

=

(

n + 1)(4(n + 1)

2

1))

3

Edward Szczypka

Matematyka Dyskretna

30 / 1

background image

Jagiellonian University

Theoretical

Computer Science

Indukcja

Zasada indukcji – Sumowanie pot ˛eg liczb nieparzystych

Poza wzorami

Σ

n
k =1

(

2k 1)

=

n

2

Σ

n
k =1

(

2k 1)

2

=

n(4n

2

1)

3

mamy
Zadanie 7 Poka˙z, ˙ze:

Σ

n
k =1

(

2k 1)

3

=

n

2

(

2n

2

1)

Σ

n
k =1

(

2k 1)

4

=

n(4n

2

1)(12n

2

7)

15

Σ

n
k =1

(

2k 1)

5

=

n

2

(

16n

4

20n

2

+

7)

3

Σ

n
k =1

(

2k 1)

6

=

n(4n

2

1)(48n

4

72n

2

+

31)

21

Edward Szczypka

Matematyka Dyskretna

31 / 1

background image

Jagiellonian University

Theoretical

Computer Science

Indukcja

Zasada indukcji – Modyfikacje

Jesli nasz "marsz"

zamiast od zera zaczniemy od innej liczby a,

ale upewnimy si ˛e, ze zbiór Z N, tak jak uprzednio wraz z ka˙zd ˛

a liczb ˛

a k , b ˛edzie zawierał

jej nast ˛epnik k + 1

to mo˙zemy wnioskowa´c, ˙ze w Z s ˛

a wszystkie liczby naturalne pocz ˛

awszy od a, tzn. je´sli

a Z N i k Z

k + 1 Z

to Z = {n N : n ­ a}.

Inna modyfikacja jest zakładanie, ze zbiór Z N spełnia:

0 Z

Z zawiera jak ˛

a´s liczb ˛e, je ˛eli tylko zawiera wszystkie mniejsze od niej

o którym to zbiorze tez mo˙zemy wnioskowa´c, ˙ze Z = N.

Na ogół łatwiej jest wywnioskowa´c, ze k + 1 Z wiedz ˛

ac, ze 0, 1, 2, . . . , k Z , ni˙z wiedz ˛

ac

tylko, ˙ze k Z .

Edward Szczypka

Matematyka Dyskretna

32 / 1

background image

Jagiellonian University

Theoretical

Computer Science

Indukcja

Zasada indukcji – Nierówno ´sci

Mamy przeczucie, ze funkcja n

2

ro´snie wolniej ni˙z 2

n

. Co prawda dla pocz ˛

atkowych warto´sci

mamy

n

0

1

2

3

4

5

6

7

8

. . .

n

2

0

1

4

9

16

25

36

49

64

. . .

2

n

1

2

4

8

16

32

64

128

256

. . .

i zachowanie tych dwu funkcji nie jest "zdecydowane", ale juz od wi ˛ekszych warto´sci 2

n

znacznie

dominuje n

2

. Aby si ˛e przekona´c, ˙ze;

n

2

<

2

n

dla n ­ 5

przeprowad´zmy dowód indukcyjny:

Poka˙zemy najpierw, ˙ze 2n + 1 < 2

n

(dla zupełnie dowolnego n ­ 3)

oczywi´scie 2 · 3 + 1 = 7 < 8 = 2

3

oraz 2(n + 1) + 1 = 2n + 3 < 2

n

+

4 = 2

n

+

2

2

2

n

+

2

n

=

2 · 2

n

=

2

n+1

a nast ˛epnie

zauwa˙zmy, ˙ze 5

2

=

25 < 32 = 2

5

,

oraz, ˙ze (n + 1)

2

=

n

2

+ (

2n + 1), 2

n

+

2

n

=

2 · 2

n

=

2

n+1

Edward Szczypka

Matematyka Dyskretna

33 / 1

background image

Jagiellonian University

Theoretical

Computer Science

Indukcja

Zasada indukcji – Nierówno ´sci

Podobnie, aby pokaza´c, ˙ze:

n

3

<

2n

dla n ­ 10

pokazujemy kolejno, ˙ze:

6n + 6 < 2

n

ju˙z dla n > 6

to mo˙zna pokaza´c podobnie jak uprzednio 2n + 1 < 2

n

,

3n

2

+

3n + 1 < 2

n

dla n ­ 10

jako, ˙ze 3 · 10

2

+

3 · 10 + 1 = 331 < 1024 = 210

oraz
3(n + 1)

2

+

3(n + 1) + 1 = (3n

2

+

3n + 1) + (6n + 6) < 2

n

+

2

n

=

2 · 2

n

=

2

n+1

a nast ˛epnie:

nierówno´s´c 10

3

=

1000 < 1024 = 2

10

wraz z (n + 1)

3

=

n

3

+ (

3n

2

+

3n + 1) < 2

n

+

2

n

=

2

n+1

Zadanie 8 Pokaz, ze dla dowolnego wykładnika c mamy

n

c

<

2n

dla dostatecznie du˙zych liczb naturalnych n.

Edward Szczypka

Matematyka Dyskretna

34 / 1

background image

Jagiellonian University

Theoretical

Computer Science

Indukcja

Zasada indukcji – Arytmetyka Modularna

Przykład 9 Poka˙zemy, ze 2|n

2

n.

Istotnie 0

2

0 = 0 = 2 · 0, czyli 0

2

0 jest podzielne przez 2.

Nadto, gdy n

2

n jest podzielne przez 2 to n

2

n = 2x dla pewnej liczby x N.

A wtedy

(

n + 1)

2

(n + 1) = n

2

+

2n + 1 n 1 = (n

2

n) + 2n = 2x + 2n = 2 · (x + n),

co oznacza, ˙ze (n + 1)

2

(n + 1) te˙z jest podzielne przez 2.

Przykład 10 Poka˙zemy, ˙ze 6|n

3

n.

Istotnie 0

3

0 = 0 = 6 · 0, czyli 0

3

0 jest podzielne przez 6.

Nadto, gdy n

3

n jest podzielne przez 6 to n

3

n = 6x dla pewnej liczby x N.

A wtedy
(

n + 1)

3

(n + 1) = n

3

+

3n

2

+

3n + 1 n 1 = (n

3

n) + 3n

2

+

3n = 6x + 3n(n + 1)

Oczywi´scie 3n(n + 1) jest podzielne przez 3. Ale n(n + 1) to iloczyn kolejnych dwu liczb,
wiec która´s z nich, (a zatem i ich iloczyn) musi by´c parzysta.

Oznacza to, ze 3n(n + 1) jest podzielne przez 6, wiec i suma 6x + 3n(n + 1) jest podzielna

przez 6. Czyli, ze (n + 1)2 (n + 1) te˙z jest podzielne przez 6.

Edward Szczypka

Matematyka Dyskretna

35 / 1

background image

Jagiellonian University

Theoretical

Computer Science

Indukcja

Zasada indukcji – Małe twierdzenie Fermata

Przykład 11 Poka˙zmy, ˙ze je´sli p jest liczba pierwsza to p|n

p

n.

Oczywi´scie p|0 = 0

p

0.

Nadto

(

n + 1)

p

(n + 1) = Σ

p
k =0

p

k

n

k

(n + 1) = (n

p

n) + Σ

p1
k =1

p

k

n

k

Pierwszy składnik tej ostatniej sumy jest podzielny przez p na mocy naszego zało˙zenia
indukcyjnego.
A drugi?
Wystarczy pokaza´c, ˙ze dla k = 1, 2, . . . , p 1 ka˙zda liczba postaci

p
k

jest podzielna przez p.

Ale

p

k

=

p!

k !(p k )!

=

(

p k + 1)(p k + 2) . . . (p 1)p

k !

Poniewa˙z p jest liczba pierwsz ˛

a, wi ˛ec ˙zeby ten ułamek był skracalny przez p, to który´s czynnik w

mianowniku musiałby by´c podzielny przez p.

A tak jest, gdy˙z wyst ˛epuj ˛

a tam tylko liczby silnie mniejsze ni˙z p, a mianowicie 1, 2, 3, . . . , k < p.

Edward Szczypka

Matematyka Dyskretna

36 / 1

background image

Jagiellonian University

Theoretical

Computer Science

Indukcja

Zasada indukcji – Małe twierdzenie Fermata

Przykład 12 Poka˙zmy, ˙ze 12|10

n

4 dla n ­ 2

Rzeczywi´scie 10

2

4 = 96 = 12 · 8 wi ˛ec 10

2

4 dzieli si ˛e przez 12.

Dodatkowo, skoro 12|10

n

4 to 10

n

4 = 12x, zatem mo˙zemy przedstawi´c

10

n+1

=

10 · 10

n

=

10 · 12x czyli te˙z jest podzielny przez 12.

Edward Szczypka

Matematyka Dyskretna

37 / 1


Document Outline


Wyszukiwarka

Podobne podstrony:
Lecture 04 05 06 C Primer New
Lecture 04 05 06 C Primer New
Feynman Lectures on Physics Volume 1 Chapter 04
lecture slides 04
Econometrics, Lecture 3, 2014 03 04
Wykład 04
IR Lecture1
04 22 PAROTITE EPIDEMICA
uml LECTURE
lecture3 complexity introduction
04 Zabezpieczenia silnikówid 5252 ppt
Wyklad 04
Wyklad 04 2014 2015
04 WdK
04) Kod genetyczny i białka (wykład 4)

więcej podobnych podstron