Matematyka dyskretna 1/Wykład 2: Rekurencja

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Definicje rekurencyjne

Definicja rekurencyjna (indukcyjna):

  • nieformalnie - taka definicja, która odwołuje się do samej siebie - ale trzeba tu uważać, by odwołanie było do instancji o mniejszej komplikacji,
  • zwykle chodzi o ciąg , - dla którego przepis na element wykorzystuje jakieś poprzednie elementy: itp.,
  • początkowy element (lub kilka początkowych) muszą być zadane konkretnie - żeby było od czego zacząć,
  • zwykle definicja rekurencyjna odwołuje się do jednego lub kilku poprzednich elementów, ale może też odwoływać się do wszystkich poprzednich.

Przykład

Silnia liczby (zapisywana jako ) to iloczyn kolejnych liczb naturalnych od do , czyli



Przyjmuje się że . Oto wartości silni dla kilku początkowych liczb naturalnych



Ciąg aby mógł być precyzyjnie rozumiany np. przez komputer, powinien być zadany rekurencyjnie jako:



Ponieważ pierwszy wyraz jest zadany, to możemy kolejno obliczać:



Przykład

Jaki ciąg jest zdefiniowany poprzez małą modyfikację w definicji silni?



A co definiują następujące określenia:



oraz



W ostatnim przypadku widać, że ponieważ odwołanie jest dwa wyrazy wstecz, to już wyliczenie pierwszego wyrazu staje się niemożliwe.

Ciąg arytmetyczny

Przykład

W ciągu zadanym poprzez równania:



łatwo rozpoznać kolejne liczby parzyste:



Ogólnie ciąg zadany poprzez ustalenie oraz



to tzw. ciąg arytmetyczny.
Jego -ty wyraz dany jest wzorem:



Aby to uzasadnić, pokazujemy indukcyjnie, że:



oraz


Ciąg geometryczny

Przykład

W ciągu zadanym poprzez równania:



łatwo rozpoznać kolejne potęgi liczby :



Ogólnie ciąg zadany poprzez ustalenie oraz zadanie



to tzw. ciąg geometryczny.
Jego -ty wyraz dany jest wzorem:



Aby to uzasadnić, pokazujemy indukcyjnie, że:



oraz


Wieże Hanoi

Przykład (E.Lucas, 1883)

U zarania czasu Bóg umieścił 64 złote krążki na jednej z trzech diamentowych iglic tak, że krążki wyżej umieszczone miały mniejsze promienie.

Następnie Bóg polecił grupie mnichów przełożenie tych krążków na trzecią iglicę , ale tak by:

  • w jednym ruchu przenosić tylko jeden krążek,
  • krążek większy nigdy nie może leżeć na krążku mniejszym,
  • można posługiwać się iglicą .

Mnisi pracują od zarania dziejów dzień i noc ... .Ile czasu im to zajmie?

Wieże Hanoi - analiza

By obliczyć ilość potrzebnych do wykonania ruchów, przeanalizujmy najpierw małe przypadki:
Łatwo zauważyć, że dla 1 krążka potrzebny jest jeden ruch:
Podobnie dla dwu krążków możemy postąpić:
Przy 3 krążkach postępujemy tak:

  • najpierw przenosimy dwa górne krążki na iglicę posługując się iglicą :
  • przenosimy największy krążek z na :
  • przenosimy krążki z na posługując się iglicą :

co pokazuje, że potrzeba tu 7 ruchów.
Czy już wiesz jak rozwiązać to zadanie w ogólności (dla krążków)?
Oznaczmy przez liczbę ruchów potrzebnych do przeniesienia krążków z jednej iglicy na drugą. Wiemy już, że:



Aby przenieść krążków z na możemy postąpić podobnie jak w przypadku 3 krążków, redukując zadanie do:

  • przenosimy górnych krążków na iglicę posługując się iglicą - potrzeba na to ruchów
  • przenosimy największy krążek z na - to tylko jeden ruch
  • przenosimy krążków z na posługując się iglicą - znów potrzeba na to ruchów

A zatem



Ile wobec tego wynosi ?

Mamy więc równanie rekurencyjne



bardzo podobne do ciągu geometrycznego.
Możemy policzyć kilka jego wyrazów:



i rozpoznać w nim ciąg potęg dwójki zmniejszonych o 1.

Ale czy rzeczywiście ?

I znów, aby się upewnić, że nasze odgadnięcie było poprawne, sprawdzamy indukcyjnie, że



co oznacza, że rzeczywiście ciąg spełnia równanie rekurencyjne, którym zadany jest ciąg .
A wiec , co przy przenoszeniu jednego krążka na sekundę zajmie ponad lat, a przenosząc te krążki "komputerem" 3GHz potrzeba będzie... i tak ponad tysiąc lat!

Przykład

{{{3}}}

Przykład

Jaka jest największa możliwa liczba obszarów wyznaczonych przez prostych na płaszczyźnie?

Sprawdźmy najpierw kilka pierwszych wartości.

  • Gdy nie ma żadnej prostej obszar jest jeden.
  • Jedna prosta tworzy zawsze dwa różne obszary.
  • Kładąc drugą prostą (byle nie równoległą do pierwszej) otrzymujemy obszary.

W tym momencie możemy pokusić się o zgadywanie i przypuścić, że . Jednakże

  • Dla trzech prostych jest to .

Zauważmy, że nowa prosta zwiększa ilość obszarów o jeśli przecina dokładnie z poprzednich prostych i to w nowych punktach przecięć. Z drugiej strony dwie proste mogą się przeciąć w co najwyżej jednym punkcie i przecinają się o ile nie są równolegle. Widzimy zatem, że najwięcej obszarów dostaniemy kładąc kolejne proste w ten sposób aby żadne dwie nie były równoległe i żadne trzy nie przecinały się w jednym punkcie. Otrzymujemy następujące równanie rekurencyjne:

Ponownie rozwiążemy równanie rozwijając je:

gdzie ostatnia równość wynika z - już udowodnionego - wzoru na sumę kolejnych liczb naturalnych.

Liczby Fibonacciego

Leonardo Fibonacci (1175-1250)
Zobacz biografię

Spośród ciągów zdefiniowanych rekurencyjnie, jednym z najsłynniejszych jest ciąg Fibonacciego zadany przez



Wszystkie wyrazy ciągu, oprócz pierwszych dwu, są sumą dwu poprzednich elementów. Oto kilka pierwszych wartości ciągu Fibonacciego:



  • Jak odgadnąć wzór na ogólny wyraz ciągu?
  • Jeśli nie można odgadnąć, to jak oszacować szybkość wzrostu tego ciągu?
  • Czy rośnie on wielomianowo czy raczej wykładniczo?

Pierwsze pytanie - póki co - wydaje się dość beznadziejne.

Plik:Domino-1.6-1.8.mp4
Domino-1.6-1.8.swf

Przykład

Na ile sposobów można ułożyć domina na prostokącie o rozmiarze ?

Oznaczmy, tę liczbę przez w zależności od .

  • Dla jest to możliwe na dokładnie jeden sposób, tzn.
  • Dla są już dwa takie sposoby:

- ustawiamy obie kostki poziomo, lub obie pionowo,
a zatem .

  • Dla są trzy sposoby,
  • Pokrywając większy prostokąt musimy jakoś pokryć dwa skrajne pola przylegające do krótszej krawędzi o długości . Można to zrobić na dwa sposoby:
    • ułożyć jedno domino pionowo - pozostanie prostokąt , który można pokryć na sposobów,
    • ułożyć dwa domina poziomo - pozostanie prostokąt , który można pokryć na sposobów.

Czyli łącznie jest sposobów pokrycia tablicy .

Rozpoznajemy w tym łatwo ciąg Fibonacci'ego (bo oczywiście pusty prostokąt można pokryć na dokładnie jeden sposób, ).

Obserwacja 2.1

1.10

Dowód

Polecamy jako ćwiczenie bardzo łatwy dowód powyższej równości przez indukcję. Przedstawimy alternatywny dowód posługujący się intuicją z poprzedniego przykładu. Wiemy zatem, że prostokąt wielkości można pokryć kostkami domina na sposobów.

Dla dowodu obserwacji, policzmy na ile sposobów można ułożyć prostokąt wielkości w taki sposób aby było tam chociaż jedno domino ustawione poziomo. Policzymy to dwiema różnymi metodami:

  • Jest tylko jedna metoda ułożenia prostokąta bez poziomych klocków. A zatem jest sposobów ułożenia prostokąta z chociaż jednym dominem poziomym.
  • Rozważmy kolejne możliwe miejsca pierwszego poziomego domina (tak naprawdę pary domin) w prostokącie od lewej:
    • jeśli na samym początku jest para poziomych domin, to pozostaje prostokąt , który możemy wypełnić dowolnie na sposobów;
    • jeśli na początku jest (gdzie ) pionowych domin, a potem następuje para poziomych, to pozostaje prostokąt , który można wypełnić na sposobów;
    • para poziomych domin może się pojawić najdalej po pionowych dominach

To dowodzi, iż jest dokładnie sposobów ułożenia prostokąta z chociaż jednym dominem poziomym.

Policzyliśmy na dwa różne sposoby to samo, otrzymując obie strony postulowanej równości. To kończy dowód.

End of proof.gif

Obserwacja 2.2

Dowód

Dowód przez indukcję po :

  • dla mamy ,
  • do założonej indukcyjnie równości dodajmy obustronnie otrzymując

co kończy dowód kroku indukcyjnego.

End of proof.gif

Twierdzenie 2.3 [wzór Eulera-Bineta]



Dowód

Rozważmy równanie:



Mnożąc je obustronnie przez otrzymujemy:



Oznacza to, że jeśli jest pierwiastkiem równania , to ciąg spełnia zależność rekurencyjną Fibonacci'ego:



Tyle, że równanie ma dwa rzeczywiste rozwiązania:



Który więc z ciągów jest ciągiem Fibonacci'ego? Okazuje się, że żaden, bo na przykład ilorazy kolejnych wyrazów ciągu Fibonacci'ego nie są stałe, a takie musiałyby być dla ciągów geometrycznych . Co więcej:

  • jeśli ciąg spełnia zależność , to dla dowolnej liczby rzeczywistej ciąg też spełnia tę zależność,
  • jeśli ciągi i spełniają zależność , to ich suma też spełnia tę zależność.

Oznacza to w szczególności, że zbiór ciągów spełniających zależność jest podprzestrzenią wektorową przestrzeni .

Ćwiczenie: Przestrzen jest dwuwymiarowa o bazie

Przypuśćmy na chwilę, że jakaś kombinacja liniowa ciągów , tzn.



jest poszukiwanym ciągiem Fibonacci'ego. Aby wyznaczyć stałe zauważmy, że muszą one spełniać układ równań:



co po rozwiązaniu daje:



i ostatecznie dostajemy ciąg:



jako potencjalnego kandydata na ciąg Fibonacci'ego. W istocie potrzebujemy indukcyjnego dowodu, że . Dla wygody oznaczmy .

  • Ponieważ liczby Fibonacci'ego są zadane wzorem odwołującym się do dwóch poprzednich elementów sprawdzamy dwie pierwsze wartości:
    • ,
    • ,
  • Aby pokazać, że użyjemy pod koniec naszych obliczeń założenia indukcyjnego, że i , a także tego, że zarówno jak i spełniają zależność :



End of proof.gif
Jan Kepler (1571-1630)
Zobacz biografię

Liczba jest powszechnie znana jako złota liczba. Opisuje ona tak zwane złote proporcje w sztuce. Pojawia się ona również bardzo często przy okazji różnych obiektów kombinatorycznych. Występuje również w kolejnym wniosku, który po raz pierwszy zaobserwował Johannes Kepler.


Wniosek 2.4



Dowód



gdzie ostatnia równość wynika z faktu, iż



jako że .

End of proof.gif

Macierze liczb Fibonacci'ego

Rozważając specjalne kwadratowe macierze liczb Fibonacci'ego postaci



łatwo zauważamy, że



Ponieważ równocześnie:



to łatwo indukcyjnie łatwo udowodnić, że



Giovanni Domenico Cassini (1625-1712)
Zobacz biografię

Przyrównując wyznaczniki obu macierzy otrzymujemy tożsamość, którą jako pierwszy opublikował Jean-Dominique Cassini w 1680 roku.


Obserwacja 2.5

Korzystając z kolei z faktu, że dla dowolnej kwadratowej macierzy , otrzymujemy:

Obserwacja 2.6



Rozwiązywanie liniowych równań rekurencyjnych - metoda ogólna

Rozumowanie dotyczące ciągu Fibonacci'ego możemy uogólnić. Chwilowo skupimy się jedynie na przypadku, gdy dla rozwiązania równania rekurencyjnego



równanie kwadratowe



ma dokładnie dwa różne pierwiastki . Wtedy bowiem łatwo pokazać, że ciąg



ze stałymi



jest poszukiwanym rozwiązaniem.

Gdy równanie ma tylko jeden pierwiastek (podwójny, gdy ), to wkrótce pokażemy, że rozwiązaniem jest



ze stałymi wyznaczonymi, jak poprzednio, poprzez dwa pierwsze wyrazy początkowe:


Drzewa binarne

Poznaliśmy wiele przykładów ciągów liczbowych zadanych równaniami rekurencyjnymi. Teraz poznamy zupełnie inną strukturę zadaną definicją rekurencyjną.

Interpretacja graficzna kilku, małych drzew binarnych

Drzewo binarne to dowolny obiekt powstały zgodnie z regułami:

  • jest drzewem binarnym,
  • jeśli i są drzewami binarnymi to też jest drzewem binarnym.

Zbiór wszystkich drzew binarnych oznaczamy przez . Wypisując konkretne drzewo binarne używamy nawiasów aby ujednoznacznic kolejność aplikacji reguł z definicji rekurencyjnej.

Wielkość drzewa binarnego jest wyznaczona funkcją



zdefiniowana rekurencyjnie (z uwagi na budowę drzewa) jako:

  • ,
  • .

Szerokość drzewa binarnego jest wyznaczona funkcją



zdefiniowana rekurencyjnie (z uwagi na budowę drzewa) jako:

  • ,
  • .

Wysokość drzewa binarnego jest wyznaczona funkcją



zdefiniowana rekurencyjnie (z uwagi na budowę drzewa) jako:

  • ,
  • .
1-13

Przykład




1-14

Obserwacja 2.7

Dla mamy

  • ,
  • ,
  • .

Wniosek 2.8

Drzewo jest jedynym drzewem o wysokości .

Twierdzenie 2.9 [Zasada Indukcji dla drzew binarnych]

Gdy jest zbiorem drzew binarnych spełniającym warunki:

  • ,
  • jeśli to ,

to .

Dowód

Dla dowodu niewprost załóżmy, że w nie ma wszystkich drzew. Zatem zbiór jest niepusty. Tym samym niepusty jest też zbiór Na mocy założenia o wiemy, że , co wraz z Wnioskiem 2.8 implikuje, że .

Ponieważ jest niepusty, to na podstawie Zasady Minimum ma element najmniejszy, powiedzmy . Wiemy już, że . Niech poświadcza fakt, że , tzn. . Ponownie z Wniosku 2.8 dostajemy , czyli dla pewnych . Z Obserwacji 2.7 mamy oraz . Zatem minimalność w daje , czyli i w konsekwencji .

Ale wtedy, z założenia o zbiorze , dostajemy . Sprzeczność.

End of proof.gif

Zasada Indukcji dla drzew binarnych to przykład na to, że w strukturach zdefiniowanych rekurencyjnie można dowodzić przy pomocy zasady analogicznej do Zasady Indukcji. Poniżej przedstawiamy przykład używający tego narzędzia.

Obserwacja 2.10

Dla dowolnego drzewa binarnego mamy:

  • ,
  • .

Dowód

Niech będzie zbiorem drzew binarnych spełniających powyższe własności.

  • , oraz , czyli .
  • W kroku indukcyjnym zakładamy, że oraz że drzewa mają już opisane w Obserwacji własności. Wtedy



Podobnie



gdzie ostatnia nierówność wynika bezpośrednio z faktu, że szerokość każdego drzewa wynosi co najmniej .

End of proof.gif