Читать книгу Wprowadzenie do teorii obliczeń - Michael Sipser - Страница 32

Krok podstawowy: Udowadniamy, że wzór jest poprawny dla t = 0. Jeśli t = 0, wówczas wzór przybiera kształt

Prawą stronę można uprościć, zauważając, że M⁰ = 1. Otrzymujemy zatem

P₀ = P,

co jest prawdą, gdyż zdefiniowaliśmy P₀ jako P. W ten sposób udowodniliśmy, że krok podstawowy indukcji jest spełniony.

Krok indukcyjny: Dla każdego k ≥ 0 zakładamy, że jeśli wzór jest spełniony dla t = k, to wynika stąd, że jest spełniony dla t = k + 1. Hipoteza indukcyjna stwierdza, że

Naszym celem jest udowodnienie, że

Zrealizujemy to w następujących krokach. Ponieważ P_k+1 definiowane jest na podstawie P_k, wiemy, że

P_k+1 = P_kM − Y.

Tym samym, używając hipotezy indukcyjnej do obliczenia P_k, otrzymujemy

Po pomnożeniu przez M i przekształceniu Y uzyskujemy

Tym samym wzór jest poprawny dla t = k + 1, co kończy dowód twierdzenia.

W zadaniu 0.15 należy użyć powyższego wzoru do obliczenia bieżących rat kredytu.

Ćwiczenia

0.1 Zbadaj poniższe formalne przedstawienia zbiorów, aby zrozumieć, jakie elementy zawierają. Dla każdego zbioru napisz krótki nieformalny opis w języku potocznym.

a. {1, 3, 5, 7, …}

b. {…,−4,−2, 0, 2, 4, …}

c. {n : n = 2m dla pewnego m należącego do N}

d. {n : n = 2m dla pewnego m należącego do N, oraz n = 3k dla pewnego k z N}

e. {w : w jest słowem złożonym z zer i jedynek i w jest równe odwróconemu w}

f. {n : n jest liczbą całkowitą i n = n + 1}

0.2 Napisz formalne definicje następujących zbiorów.

a. Zbiór zawierający liczby 1, 10 i 100

b. Zbiór zawierający wszystkie liczby całkowite większe od 5

c. Zbiór zawierający wszystkie liczby naturalne mniejsze od 5

d. Zbiór zawierający słowo aba

e. Zbiór zawierający puste słowo

f. Zbiór, który niczego nie zawiera

0.3 Niech A będzie zbiorem {x, y, z}, a B zbiorem {x, y}.

a. Czy A jest podzbiorem B?

b. Czy B jest podzbiorem A?

c. Czym jest A ∪ B?

d. Czym jest A ∩ B?

e. Czym jest A × B?

f. Czym jest zbiór potęgowy zbioru B?

0.4 Jeśli A zawiera a elementów, zaś B ma b elementów, ile elementów będzie zawierać A × B? Odpowiedź uzasadnij.

0.5 Jeśli C jest zbiorem o c elementach, ile elementów zawiera zbiór potęgowy zbioru C? Odpowiedź uzasadnij.

0.6 Niech X będzie zbiorem {1, 2, 3, 4, 5}, a Y zbiorem {6, 7, 8, 9, 10}. Jednoargumentowa funkcja f : X → Y i dwuargumentowa funkcja g : X × Y → Y opisane są następującymi tablicami.

n	f(n)		g	6	7	8	9	10
1	6		1	10	10	10	10	10
2	7		2	7	8	9	10	6
3	6		3	7	7	8	8	9
4	7		4	9	8	7	6	10
5	6		5	6	6	6	6	6

a. Jaka jest wartość f(2)?

b. Jaka jest dziedzina i przeciwdziedzina f?

c. Jaka jest wartość g(2, 10)?

d. Jaka jest dziedzina i przeciwdziedzina g?

e. Jaka jest wartość g(4, f(4))?

0.7 Dla każdego punktu podaj przykład relacji, która spełnia podany warunek.

a. Zwrotna i symetryczna, ale nie przechodnia

b. Zwrotna i przechodnia, ale nie symetryczna

c. Symetryczna i przechodnia, ale nie zwrotna

0.8 Rozważ nieskierowany graf G = (V, E), gdzie V, czyli zbiór wierzchołków, to {1, 2, 3, 4}, a E, czyli zbiór krawędzi, to {{1, 2}, {2, 3}, {1, 3}, {2, 4}, {1, 4}}. Narysuj graf G. Jaki jest stopień każdego wierzchołka? Na rysunku grafu G zaznacz ścieżkę od wierzchołka 3 do wierzchołka 4.

0.9 Napisz formalny opis poniższego grafu.

Zadania

0.10 Znajdź błąd w poniższym dowodzie, że 2 = 1.

Rozważmy równanie a = b. Mnożymy obie strony równania przez a, uzyskując a² = ab. Od obu stron równania odejmujemy b², otrzymując a² − b² = ab − b². Przekształcamy obie strony do postaci (a+b)(a−b) = b(a−b), po czym dzielimy obie strony przez (a−b), otrzymując a+b = b. Na koniec podstawiamy 1 za a i b, co daje 2 = 1.

0.11 Niech S(n) = 1 + 2 + … + n będzie sumą pierwszych n liczb naturalnych, zaś C(n) = 1³ + 2³ + … + n³ niech będzie sumą pierwszych n sześcianów liczb naturalnych. Udowodnij następujące równości, używając indukcji po n, aby dojść do zadziwiającego wniosku, że C(n) = S²(n) dla każdego n.

a. S(n) = ¹/₃ n(n + 1).

b. C(n) = ¹/₃ (n⁴ + 2n³ + n²) = ¹/₃ n²(n + 1)².

0.12 Znajdź błąd w poniższym dowodzie, że wszystkie konie są tego samego koloru.

Twierdzenie: W dowolnym zbiorze h koni wszystkie konie są tego samego koloru.

Dowód: Przez indukcję po h.

Krok podstawowy: Dla h = 1. W dowolnym zbiorze zawierającym tylko jednego konia wszystkie konie oczywiście mają ten sam kolor.

Krok indukcyjny: Dla k ≥ 1, zakładamy, że teza jest prawdziwa dla h = k i wykażemy, że jest też prawdziwa dla h = k+1. Weźmy dowolny zbiór H zawierający k+1 koni. Wykażemy, że wszystkie konie w tym zbiorze są tego samego koloru. Usuwamy jednego konia z tego zbioru, aby uzyskać zbiór H₁ zawierający tyko k koni. Na mocy założenia indukcyjnego wszystkie konie ze zbioru H₁ są tego samego koloru. Teraz zwracamy usuniętego konia i usuwamy innego, aby uzyskać zbiór H₂. Na mocy tego samego rozumowania wszystkie konie w H₂ są tego samego koloru. Tym samym wszystkie konie w zbiorze muszą mieć ten sam kolor, co kończy dowód.

0.13 Wykaż, że każdy graf bez pętli zwrotnych z dwoma lub więcej wierzchołkami zawiera dwa wierzchołki o równych stopniach.

^A*0.14 Twierdzenie Ramseya. Niech G będzie grafem. Kliką w G nazywamy podgraf, w którym każde dwa wierzchołki są ze sobą połączone krawędzią. Antyklika, nazywana też zbiorem niezależnym, to podgraf, w którym dowolne dwa wierzchołki nie są ze sobą połączone krawędzią. Udowodnij, że każdy graf o n wierzchołkach zawiera albo kilkę, albo antyklikę z co najmniej ¹/₃ log₂n wierzchołkami.

^A0.15 Użyj twierdzenia 0.25, aby wyprowadzić wzór na obliczanie wielkości miesięcznej raty spłaty kredytu na podstawie wartości kredytu P, stopy oprocentowania I oraz liczby spłat t. Przyjmij założenie, że po wykonaniu t spłat wielkość długu jest zredukowana do 0. Użyj tego wzoru do obliczenia wartości miesięcznej raty dla 30-letniego kredytu z 360 miesięcznymi ratami dla początkowej wartości kredytu wynoszącej 100 000 dolarów przy rocznej stopie oprocentowania 5%.

Wybrane rozwiązania

0.14 Przygotuj miejsce na dwie kupki wierzchołków: A i B. Następnie rozważaj po kolei wszystkie wierzchołki i jeśli dany wierzchołek x ma stopień większy niż połowa nierozważonych jeszcze wierzchołków, to umieść go na kupce A a w przeciwnym razie na kupce B; jeśli x został umieszczony na kupce A (na kupce B), usuń z grafu wszystkie wierzchołki z którymi x nie jest (jest) połączony. Wykonuj te operacje, aż wszystkie wierzchołki zostaną rozważone lub usunięte. W każdym kroku usuwamy nie więcej niż połowę wierzchołków, więc wykonamy co najmniej log₂n kroków. W każdym kroku wierzchołek dodawany jest na jedną z kupek, zatem jedna z nich ma wielkość co najmniej ¹/₃ log₂n wierzchołków. Kupka A zawiera wierzchołki tworzące klikę, zaś kupka B wierzchołki tworzące antyklikę.

0.15 Przyjmujemy P_t = 0 i rozwiązujemy wzór ze względu na Y, aby uzyskać wzór: Y = PM^t(M − 1)//(M^t − 1). Dla P = $100,000, I = 0.05 i t = 360 otrzymujemy M = 1 + (0.05)/12. Następnie można użyć kalkulatora, aby ustalić, że rata miesięczna Y » $536.82.