Cyfroteka.pl

klikaj i czytaj online

Cyfro
Czytomierz
00301 007777 11009312 na godz. na dobę w sumie
Wykłady z informatyki z przykładami w języku C - książka
Wykłady z informatyki z przykładami w języku C - książka
Autor: , Liczba stron: 848
Wydawca: Helion Język publikacji: polski
ISBN: 83-7361-138-X Data wydania:
Lektor:
Kategoria: ebooki >> komputery i informatyka >> programowanie >> c - programowanie
Porównaj ceny (książka, ebook, audiobook).

Książka Alfreda Aho i Jeffreya Ullmana 'Wykłady z informatyki z przykładami w języku C' stanowi znaczący postęp w dziedzinie metodyki nauczania podstaw informatyki. Ten nowatorski podręcznik w przystępny sposób prezentuje zagadnienia dotyczące modeli, pojęć i technik z zakresu matematyki dyskretnej i informatyki. Książka stanowi zarówno wprowadzenie do dziedziny informatyki, jak i autorytatywne źródło jej teoretycznych podstaw. Pokazuje, w jaki sposób 'matematyczne abstrakcje' przekształca się w działające programy.

Podręcznik dostarcza przyszłym informatykom solidnych podstaw niezbędnych w dalszych studiach oraz w przyszłej pracy zawodowej. Zawiera liczne ćwiczenia, ułatwiające przyswojenie przedstawianej w nim wiedzy i sprawdzenie swoich umiejętności. Autorzy wymagają od czytelnika znajomości języka C.

Zakres tematyczny obejmuje między innymi:

Znajdź podobne książki Ostatnio czytane w tej kategorii

Darmowy fragment publikacji:

IDZ DO IDZ DO PRZYK£ADOWY ROZDZIA£ PRZYK£ADOWY ROZDZIA£ SPIS TREĎCI SPIS TREĎCI KATALOG KSI¥¯EK KATALOG KSI¥¯EK KATALOG ONLINE KATALOG ONLINE ZAMÓW DRUKOWANY KATALOG ZAMÓW DRUKOWANY KATALOG TWÓJ KOSZYK TWÓJ KOSZYK DODAJ DO KOSZYKA DODAJ DO KOSZYKA CENNIK I INFORMACJE CENNIK I INFORMACJE ZAMÓW INFORMACJE ZAMÓW INFORMACJE O NOWOĎCIACH O NOWOĎCIACH ZAMÓW CENNIK ZAMÓW CENNIK CZYTELNIA CZYTELNIA FRAGMENTY KSI¥¯EK ONLINE FRAGMENTY KSI¥¯EK ONLINE Wydawnictwo Helion ul. Chopina 6 44-100 Gliwice tel. (32)230-98-63 e-mail: helion@helion.pl Wyk³ady z informatyki z przyk³adami w jêzyku C Autorzy: Alfred V. Aho, Jeffrey D. Ullman T³umaczenie: Miko³aj Szczepaniak, Bart³omiej Garbacz ISBN: 83-7361-138-X Tytu³ orygina³u: Foundation of Computer Science in C Format: B5, stron: 846 Ksi¹¿ka Alfreda Aho i Jeffreya Ullmana „Jêzyk C” stanowi znacz¹cy postêp w dziedzinie metodyki nauczania podstaw informatyki. Ten nowatorski podrêcznik w przystêpny sposób prezentuje zagadnienia dotycz¹ce modeli, pojêæ i technik z zakresu matematyki dyskretnej i informatyki. Ksi¹¿ka stanowi zarówno wprowadzenie do dziedziny informatyki, jak i autorytatywne ĥród³o jej teoretycznych podstaw. Pokazuje, w jaki sposób „matematyczne abstrakcje” przekszta³ca siê w dzia³aj¹ce programy. Podrêcznik dostarcza przysz³ym informatykom solidnych podstaw niezbêdnych w dalszych studiach oraz w przysz³ej pracy zawodowej. Zawiera liczne æwiczenia, u³atwiaj¹ce przyswojenie przedstawianej w nim wiedzy i sprawdzenie swoich umiejêtnoġci. Autorzy wymagaj¹ od czytelnika znajomoġci jêzyka C. Zakres tematyczny obejmuje miêdzy innymi: • Iteracjê, indukcjê i rekursjê • Zagadnienia zwi¹zane z czasem wykonywania programów • Kombinatorykê i prawdopodobieñstwo • Modele danych oparte na drzewach, listach i zbiorach • Relacyjny i grafowy model danych • Wzorce, automaty i wyra¿enia regularne, rekurencyjny model wzorców • Logikê zdañ • Logikê predykatów Alfred V. Aho jest zastêpc¹ dyrektora ds. informatyki i badañ technologicznych w firmie Bellcore. Od 1967 do 1991 roku pracowa³ w Computing Science Research Center w AT T Bell Laboratories. Wyk³ada³ równie¿ informatykê na Columbia University, Stanford University oraz Stevens Institute of Technology. Spis treści Przedmowa.................................................................................................................9 1. Informatyka: mechanizacja abstrakcji ....................................................................15 1.1. Zagadnienia omawiane w książce ...................................................e........................................................... 17 1.2. Zagadnienia omawiane w tym rozdziale...................................................e................................................. 20 1.3. Modele danych ...................................................e...................................................e..................................... 20 1.4. Model danych języka C...................................................e........................................................................... 27 1.5. Algorytmy i projektowanie programów...................................................e.................................................. 35 1.6. Niektóre z wykorzystywanych w tej książce konwencji języka C...................................................e.......... 37 1.7. Podsumowanie rozdziału 1........................e...................................................e.............................................. 38 1.8. Bibliografia rozdziału 1....................................................e.......................................................................... 39 2. Iteracja, indukcja i rekurencja.................................................................................41 2.1. Zagadnienia poruszane w rozdziale 2. ...................................................e.................................................... 43 2.2. Iteracje...................................................e...................................................e.................................................. 43 2.3. Dowody indukcyjne ...................................................e...................................................e............................. 51 2.4. Indukcja zupełna ...................................................e...................................................e.................................. 61 2.5. Dowodzenie własności programów ...................................................e........................................................ 69 2.6. Definicje rekurencyjne ...................................................e............................................................................ 77 2.7. Funkcje rekurencyjne ...................................................e...................................................e........................... 87 2.8. Sortowanie przez scalanie: rekurencyjny algorytm sortujący...................................................e................. 93 2.9. Dowodzenie własności programów rekurencyjnych......e...................................................e....................... 102 2.10. Podsumowanie rozdziału 2.......................e...................................................e........................................... 105 2.11. Bibliografia rozdziału 2....................................................e...................................................................... 106 4 3. SPIS TREŚCI Czas działania programów....................................................................................107 3.1. Zagadnienia poruszane w tym rozdziale ...................................................e............................................... 107 3.2. Wybór algorytmu ...................................................e...................................................e............................... 108 3.3. Pomiar czasu działania programu ...................................................e......................................................... 109 3.4. Notacja „dużego O” i przybliżony czas działania...................................................e................................. 114 3.5. Upraszczanie wyrażeń „dużego O”...................................................e....................................................... 120 3.6. Analiza czasu działania programu..................e...................................................e....................................... 128 3.7. Reguła rekurencyjna dla szacowania ograniczeń czasów działania...................................................e...... 136 3.8. Analizowanie programów zawierających wywołania funkcji ...................................................e.............. 146 3.9. Analizowanie funkcji rekurencyjnych ...................................................e.................................................. 151 3.10. Analiza sortowania przez scalanie ...................................................e...................................................... 155 3.11. Rozwiązywanie relacji rekurencyjnych ...................................................e.............................................. 164 3.12. Podsumowanie rozdziału 3.......................e...................................................e........................................... 174 3.13. Bibliografia rozdziału 3....................................................e...................................................................... 175 4. Kombinatoryka i prawdopodobieństwo................................................................177 4.1. Zagadnienia poruszane w tym rozdziale ...................................................e............................................... 177 4.2. Wariacje z powtórzeniami...................................................e..................................................................... 178 4.3. Permutacje...................................................e...................................................e.......................................... 182 4.4. Wariacje bez powtórzeń ...................................................e........................................................................ 188 4.5. Kombinacje ...................................................e...................................................e........................................ 191 4.6. Permutacje z powtórzeniami ...................................................e................................................................. 199 4.7. Rozdzielanie obiektów do koszyków...................................................e.................................................... 202 4.8. Łączenie reguł kombinatorycznych ...................................................e...................................................... 205 4.9. Wprowadzenie do teorii prawdopodobieństwa ...................................................e..................................... 209 4.10. Prawdopodobieństwo warunkowe ...................................................e...................................................... 215 4.11. Rozumowanie probabilistyczne ...................................................e.......................................................... 225 4.12. Oczekiwane wartości obliczeń ...................................................e............................................................ 235 4.13. Niektóre zastosowania prawdopodobieństwa w programowaniu ...................................................e....... 238 4.14. Podsumowanie rozdziału 4.......................e...................................................e........................................... 244 4.15. Bibliografia rozdziału 4....................................................e...................................................................... 245 5. Model danych oparty na drzewach .......................................................................247 5.1. Zagadnienia poruszane w tym rozdziale ...................................................e............................................... 247 5.2. Podstawowa terminologia ...................................................e..................................................................... 248 5.3. Struktury danych dla drzew......................e...................................................e............................................. 256 5.4. Rekurencja w drzewach ...................................................e........................................................................ 263 5.5. Indukcja strukturalna...................................................e............................................................................. 272 5.6. Drzewa binarne ...................................................e...................................................e.................................. 277 5.7. Drzewa przeszukiwania binarnego..................e...................................................e...................................... 284 5.8. Efektywność operacji na drzewach przeszukiwania binarnego ...................................................e............ 293 5.9. Kolejki priorytetowe i drzewa częściowo uporządkowane...................................................e................... 297 5.10. Sortowanie stogowe — sortowanie za pomocą zrównoeważonych drzew częściowo uporządkowanych ...................................................e...................................................e.......... 306 5.11. Podsumowanie rozdziału 5........................e...................................................e.......................................... 311 5.12. Bibliografia rozdziału 5....................................................e...................................................................... 312 SPIS TREŚCI 6. 5 Model danych oparty na listach ............................................................................313 6.1. Zagadnienia poruszane w tym rozdziale ...................................................e............................................... 313 6.2. Podstawowa terminologia ...................................................e..................................................................... 314 6.3. Operacje na listach ...................................................e...................................................e............................. 318 6.4. Struktura danych — lista jednokierunkowa ...................................................e.......................................... 320 6.5. Implementacja list oparta na tablicy..............e...................................................e........................................ 329 6.6. Stosy ...................................................e...................................................e................................................... 335 6.7. Wykorzystanie stosu w implementacji wywołań funkcji...................................................e...................... 341 6.8. Kolejki...................................................e...................................................e................................................ 347 6.9. Najdłuższy wspólny podciąg...................................................e................................................................. 350 6.10. Reprezentowanie ciągów znakowych ...................................................e................................................. 357 6.11. Podsumowanie rozdziału 6........................e...................................................e.......................................... 364 6.12. Bibliografia rozdziału 6....................................................e...................................................................... 365 7. Model danych oparty na zbiorach.........................................................................367 7.1. Zagadnienia poruszane w tym rozdziale ...................................................e............................................... 367 7.2. Podstawowe definicje...................................................e...................................................e......................... 367 7.3. Operacje na zbiorach...................................................e...................................................e.......................... 372 7.4. Implementacja zbiorów oparta na liście...................................................e................................................ 383 7.5. Implementacja zbiorów oparta na wektorze własnym ...................................................e.......................... 389 7.6. Mieszanie ...................................................e...................................................e........................................... 392 7.7. Relacje i funkcje...................................................e...................................................e................................. 398 7.8. Implementowanie funkcji w formie danych...........e...................................................e............................... 406 7.9. Implementowanie relacji binarnych ...................................................e...................................................... 413 7.10. Specyficzne własności relacji binarnych..........e...................................................e................................... 421 7.11. Zbiory nieskończone ...................................................e...................................................e........................ 431 7.12. Podsumowanie rozdziału 7.......................e...................................................e........................................... 437 7.13. Bibliografia rozdziału 7....................................................e...................................................................... 437 8. Relacyjny model danych.......................................................................................439 8.1. Zagadnienia poruszane w tym rozdziale ...................................................e............................................... 439 8.2. Relacje...................................................e...................................................e................................................ 440 8.3. Klucze ...................................................e...................................................e................................................ 447 8.4. Główne struktury przechowywania danych w relacjach...................................................e....................... 451 8.5. Struktury indeksu drugorzędnego ...................................................e......................................................... 456 8.6. Poruszanie się wśród wielu relacji ...................................................e........................................................ 460 8.7. Algebra relacyjna ...................................................e...................................................e............................... 466 8.8. Implementowanie operacji algebry relacyjnej ...................................................e...................................... 473 8.9. Prawa algebraiczne dla relacji...................................................e............................................................... 479 8.10. Podsumowanie rozdziału 8........................e...................................................e.......................................... 488 8.11. Bibliografia rozdziału 8....................................................e...................................................................... 489 6 9. SPIS TREŚCI Grafowy model danych.........................................................................................491 9.1. Zagadnienia poruszane w tym rozdziale ...................................................e............................................... 491 9.2. Podstawowe pojęcia ...................................................e...................................................e........................... 492 9.3. Sposoby implementacji grafów...................................................e............................................................. 499 9.4. Składowe spójności grafu nieskierowanego ...................................................e......................................... 506 9.5. Minimalne drzewa rozpinające ...................................................e............................................................. 518 9.6. Przeszukiwanie w głąb ...................................................e.......................................................................... 524 9.7. Zastosowania algorytmu przeszukiwania w głąb...................................................e.................................. 536 9.8. Algorytm Dijkstry znajdowania najkrótszych dróg ...................................................e.............................. 544 9.9. Algorytm Floyda znajdowania najkrótszych dróg ...................................................e................................ 556 9.10. Wprowadzenie do teorii grafów...................................................e.......................................................... 564 9.11. Podsumowanie rozdziału 9........................e...................................................e.......................................... 569 9.12. Bibliografia rozdziału 9....................................................e...................................................................... 570 10. Wzorce, automaty i wyrażenia regularne..............................................................571 10.1. Zagadnienia poruszane w tym rozdziale ...................................................e............................................. 572 10.2. Maszyny stanów i automaty...................................................e................................................................ 572 10.3. Automaty deterministyczne i niedeterministyczne ...................................................e............................. 578 10.4. Przechodzenie od niedeterminizmu do determinizmu ...................................................e........................ 588 10.5. Wyrażenia regularne ...................................................e...................................................e........................ 597 10.6. Rozszerzenia wyrażeń regularnych stosowane w systemie Unix ...................................................e....... 606 10.7. Prawa algebraiczne wyrażeń regularnych ...................................................e........................................... 610 10.8. Od wyrażeń regularnych do automatów..............e...................................................e................................ 614 10.9. Od automatów do wyrażeń regularnych..............e...................................................e................................ 624 10.10. Podsumowanie rozdziału 10.....................e...................................................e......................................... 631 10.11. Bibliografia rozdziału 10....................................................e.................................................................. 631 11. Rekurencyjny opis wzorców.................................................................................633 11.1. Zagadnienia poruszane w tym rozdziale ...................................................e............................................. 633 11.2. Gramatyki bezkontekstowe ...................................................e................................................................. 634 11.3. Języki gramatyk...............................e...................................................e.................................................... 641 11.4. Drzewa rozbioru...................................................e...................................................e............................... 644 11.5. Niejednoznaczność i projektowanie gramatyk...................................................e.................................... 652 11.6. Konstruowanie drzew rozbioru ...................................................e........................................................... 659 11.7. Algorytm analizy składniowej oparty na tabeli...e...................................................e................................ 667 11.8. Gramatyki a wyrażenia regularne ...................................................e....................................................... 676 11.9. Podsumowanie rozdziału 11.......................e...................................................e......................................... 684 11.10. Bibliografia rozdziału 11....................................................e.................................................................. 684 12. Logika zdań............................................................................................................685 12.1. Zagadnienia poruszane w tym rozdziale ...................................................e............................................. 685 12.2. Podstawy logiki zdań ...................................................e.......................................................................... 686 12.3. Wyrażenia logiczne ...................................................e...................................................e.......................... 688 SPIS TREŚCI 7 12.4. Tabele prawdy ...................................................e...................................................e.................................. 692 12.5. Od funkcji boolowskich do wyrażeń logicznych ...................................................e................................ 699 12.6. Określanie wyrażeń logicznych za pomocą tablic Karnaugha...................................................e............ 704 12.7. Tautologie ...................................................e...................................................e........................................ 712 12.8. Niektóre prawa algebraiczne dla wyrażeń logicznych ...................................................e.......................... 717 12.9. Tautologie i metody dowodzenia ...................................................e........................................................ 726 12.10. Dedukcja ...................................................e...................................................e........................................ 731 12.11. Dowodzenie przez rezolucję ...................................................e............................................................. 737 12.12. Podsumowanie rozdziału 12.....................e...................................................e......................................... 742 12.13. Bibliografia rozdziału 12....................................................e.................................................................. 743 13. Wykorzystanie logiki do projektowania komponentów komputerów .................745 13.1. Zagadnienia poruszane w tym rozdziale ...................................................e............................................. 745 13.2. Bramki...................................................e...................................................e.............................................. 746 13.3. Układy ...................................................e...................................................e.............................................. 747 13.4. Wyrażenia logiczne i układy ...................................................e............................................................... 750 13.5. Ograniczenia fizyczne związane z układami ...................................................e...................................... 756 13.6. Projekt układu dodawania z zastosowaniem zasady dziel i zwyciężaj .................................................. 761 13.7. Projekt multipleksera ...................................................e.......................................................................... 769 13.8. Elementy pamięciowe ...................................................e...................................................e...................... 776 13.9. Podsumowanie rozdziału 13.......................e...................................................e......................................... 778 13.10. Bibliografia rozdziału 13....................................................e.................................................................. 778 14. Logika predykatów ...............................................................................................779 14.1. Zagadnienia poruszane w tym rozdziale ...................................................e............................................. 779 14.2. Predykaty...................................................e...................................................e.......................................... 780 14.3. Wyrażenia logiczne ...................................................e...................................................e.......................... 782 14.4. Kwantyfikatory ...................................................e...................................................e................................ 785 14.5. Interpretacje...................................................e...................................................e...................................... 791 14.6. Tautologie ...................................................e...................................................e........................................ 797 14.7. Tautologie zawierające kwantyfikatory ...................................................e.............................................. 799 14.8. Dowody w logice predykatów ...................................................e............................................................ 806 14.9. Dowody na podstawie reguł i faktów...................................................e.................................................. 810 14.10. Prawdziwość i możność dowodzenia...................................................e................................................ 816 14.11. Podsumowanie rozdziału 14.....................e...................................................e......................................... 822 14.12. Bibliografia rozdziału 14....................................................e.................................................................. 823 Skorowidz ............................................................................................................. 825 2 Iteracja, indukcja i rekurencja Źródłem potęgi komputerów jest ich zdolność do wielokrotnego wykonywania tego samego zadania lub jego różnych wersji. W informatyce z pojęciem iteracji (ang. iteration) można się spotkać przy wielu okazjach. Wiele zagadnień związanych z modelami danych, np. listami, opiera się na powtó- rzeniach typu „lista jest albo pusta, albo składa się z jednego elementu poprzedzającego inny, i kolej- ny, itd.”. Programy i algorytmy wykorzystują iteracje do wielokrotnego wykonywania określonych zadań bez konieczności definiowania ogromnej liczby pojedynczych kroków, np. w przypadku zadania „wykonaj kolejny krok 1000 razy”. Języki programowania wykorzystują do implementowania algo- rytmów iteracyjnych pętle, np. YJKNG czy HQT w języku C. Zagadnieniem blisko związanym z powtórzeniem jest rekurencja (ang. recursion) — technika, w której definiuje się pewne pojęcie bezpośrednio lub pośrednio na podstawie tego samego pojęcia. Przykładowo, można by zdefiniować listę stwierdzeniem: „lista albo jest pusta, albo jest elementem poprzedzającym listę”. Rekurencja jest obsługiwana przez wiele języków programowania. W języku C, funkcja ( może wywoływać samą siebie albo bezpośrednio z poziomu funkcji (, albo pośrednio, wywołując inną funkcję, która wywołuje jeszcze inną funkcję itd., aż do pewnej funkcji w tym ciągu, która wywoła funkcję (. Innym ważnym zagadnieniem jest indukcja (ang. induction), która ściśle wiąże się z rekurencją i jest wykorzystywana do dowoodzenia wielu twierdzeń matematycznych. Iteracja, indukcja i rekurencja to podstawowe zagadnienia występujące w wielu formach modelów danych, struktur danych czy algorytmów. Poniższa lista zawiera pewne przykłady wykorzystania tych pojęć, każdy z nich będzie szczegółowo omówionoy w tej książce. (1) Techniki iteracyjne. Najprostszym sposobem wielokrotnego wykonania sekwencji operacji jest wykorzystanie konstrukcji iteracyjnej, jaką jest np.o instrukcja HQT w języku C. (2) Programowanie rekurencyjne. C, podobnie jak wiele innych języków programowania, umoż- liwia tworzenie funkcji rekurencyjnych, które bezpośrednio lub pośrednio wywołują same siebie. W przypadku początkujących programistów programowanie iteracyjne jest często bezpiecz- niejsze od programowania rekurencyjnego; jednym z ważniejszych celów niniejszej książki jest jednak przyzwyczajenie Czytelnika do stosowania rekurencji we właściwych momentach. Rekurencyjne programy mogą być łatwiejsze do napisanoia, analizy i zrozumienia. (3) Dowodzenie indukcyjne. Ważną techniką dowodzenia prawdziwości twierdzeń jest „dowo- dzenie indukcyjne”. Zostało ono omówione szczegółowo w podrozdziale 2.3. Poniżej przed- stawiono najprostszą formę dowodzenia indukcyjnego. Rozpoczynamy od twierdzenia S(n) zależnego od zmiennej n; chcemy udowodnić, że S(n) jest prawdziwe. Dowód rozpoczynamy od wykazania podstawy, czyli twierdzenia S(n) dla konkretnego n. Przykładowo, możemy założyć, 42 2. ITERACJA, INDUKCJA I REKURENCJA Notacja: symbole sumy i iloczynu i = n Powiększona grecka wielka litera sigma jest często wykorzystywana do oznaczenia sumy, np. ∑ 1 . To konkretne wyrażenie reprezentuje sumę liczb całkowitych od 1 do n, co oznacza, i że zastępuje zapis sumy: 1+2+3+…+n. W ogólności, można sumować dowolne funkcje f(i) względem indeksu sumy i (oczywiście indeksem może być symbol inny niż i). Wyrażenie ∑ zastępuje: i )( f b ai = f(a)+f(a+1)+f(a+2)+…+f(b) Przykładowo, wyrażenie ∑ funkcją f jest podnoszenie do kwadratu oraz wprowadzono indeoks j zamiast i. 2 jest równoważne z sumą 4+9+16+…+m j 2 j = m 2. W tym przypadku W szczególnych przypadkach, gdy b a, nie ma żadnych składników sumy ∑ , i )( zatem — zgodnie z konwencją — jej wartość wynosi 0. Jeśli b = a, istnieje dokładnie jeden składnik sumy, dla którego i = a. Wartością sumy ∑ i )( ai = f f a b Analogiczną notację wykorzystuje się do reprezentowania iloczynów za pomocą powięk- jest równoważne z iloczynem f(a)×f(a+1)× szonej wielkiej litery pi. Wyrażenie ∏ f f(a+2)×…×f(b); jeśli b a, iloczyn wynosi 1. i )( ai = b ai = jest więc f(a). że n = 0 i udowodnić prawdziwość twierdzenia S(0). Po drugie, musimy udowodnić krok indukcji, w którym wykazujemy, że twierdzenie S dla jednej wartości jego argumentu wynika z tego same- go twierdzenia S dla poprzedniej wartości jego argumentu; S(n) implikuje więc S(n+1) dla wszystkich n ≥ 0. Przykładowo, S(n) może być prostym wzorem na sumę: n =∑ i i 1 = ( nn ,2/)1 + (2.1) który określa, że suma liczb całkowitych od 1 do n jest równa n(n+1)/2. Podstawę można określić jako S(1), co oznacza, że w równaniu (2.1) zostaje podstawione 1 w miejsce n. Otrzy- mana równość ma postać 1 = 1×2/2. Krok indukcji polega na wykazaniu, że ∑ 2/)1 implikuje ∑ + pierwsze równanie to S(n), czyli równanie (2.1); drugie to S(n+1), czyli równanie (2.1) z wyrażeniem n+1 podstawionym w miejsce wszystkich wystąpień n. W podrozdziale 2.3 zostanie zaprezentowany sposób konostruowania podobnych dowodów. 2/)2 )(1 nn 1 i n n ( ( + = = + + i 1 1 n n = i i = (4) Dowodzenie poprawności programów. W informatyce często istnieje konieczność formalnego lub nieformalnego dowiedzenia, że twierdzenie S(n) w danym programie jest prawdziwe. Takie twierdzenie może np. opisywać, co jest prawdą w n-tej iteracji pewnej pętli lub co jest prawdą w n-tym wywołaniu rekurencyjnym pewnej funkcji. Tego typu dowody przeprowadza się za- zwyczaj z wykorzystaniem indukcji. (5) Definicje indukcyjne. Najlepszą formą definiowania wielu ważnych zagadnień ow informatyce, szczególnie tych związanych z modelami danych, jest indukcja, w której podstawowa reguła defi- niuje najprostszy przykład lub przykłady zagadnienia, zaś regułę lub reguły indukcyjne buduje się w celu przedstawienia większych przypadków danego zagadnienia na bazie zdefiniowanych wcześniej mniejszych. Przykładowo, powyżej wspomnianoo o tym, że listę można zdefiniować 2.1. ZAGADNIENIA PORUSZANE W ROZDZIALE 2. 43 za pomocą podstawowej zasady (lista pusta jest listą) w połączeniu z regułą indukcji (element wraz z następującą po nim listą także tworzą listę). (6) Analiza czasu działania. Ważnym kryterium oceny jakości algorytmu jest czas potrzebny do wykonania zadania dla danych o różnych rozmiarach. Jeśli algorytm opiera się na rekurencji, wykorzystuje się wzór zwany równaniem rekurencji (ang. recurrence equation), który jest indukcyjną definicją pozwalającą przewidzieć czas potrzebny danemu algorytmowi na prze- tworzenie danych wejściowych różnych rozmiarów. Każde z powyższych zagadnień (poza ostatnim) omówiono w bieżącym rozdziale; czas działania programów jest tematem rozdziału 3. 2.1. Zagadnienia poruszane w rozdziale 2. W niniejszym rozdziale omówione zostaną następujące poodstawowe zagadnienia: programowanie iteracyjne (podrozdział 2.2); dowody indukcyjne (podrozdziały 2.3 i 2.4); definicje indukcyjne (podrozdział 2.6); programowanie rekurencyjne (podrozdziały 2.7 i 2.8); dowodzenie poprawności programów (podrozdziały 2.5 i o2.9). • • • • • Dodatkowo, posługując się przykładami wykorzystania tych pojęć, szczególna uwaga zostanie poświę- cona wielu ważnym i interesującym zagadnieniom związoanym z informatyką. Będą do nich należeć: algorytmy sortujące, w tym sortowanie przez wybieranie (podrozdział 2.2) oraz sortowanie • przez scalanie (podrozdział 2.8); kontrola parzystości oraz detekcja błędów w danych o(podrozdział 2.3); wyrażenia arytmetyczne i ich przekształcanie za pomocą praw algebraicznych (podrozdziały • • 2.4 i 2.6); zbilansowane nawiasy zwykłe (podrozdział 2.6). • 2.2. Iteracje Każdy początkujący programista uczy się, jak wykorzystywać iteracje, wprowadzając pewne kon- strukcje pętlowe, takie jak instrukcje HQT lub YJKNG w języku programowania C. W niniejszym pod- rozdziale zostanie zaprezentowany przykład algorytmu iteracyjnego zwanego „sortowaniem przez wybieranie”. W podrozdziale 2.5 zostanie udowodnione metodą indukcji, że algorytm ten rzeczy- wiście wykonuje sortowanie, a czas jego działania zostanie przeanalizowany w podrozdziale 3.6. Z ko- lei w podrozdziale 2.8 zostanie zademonstrowany sposób, w jaki rekurencja może pomóc w opra- cowaniu efektywnego algorytmu sortującego zgodnie z otechniką zwaną „dziel i zwyciężaj”. 44 2. ITERACJA, INDUKCJA I REKURENCJA Powszechnie stosowane techniki: samodefiniowanie i para podstawowy-indukcyjny Podczas studiowania bieżącego rozdziału Czytelnik powinien zwrócić uwagę na dwa zagad- nienia pojawiające się często w odniesieniu do różnych tematów. Pierwsze to samodefinio- wanie, które polega na definiowaniu lub budowaniu pewnego pojęcia odwołując się do niego samego. Przykładowo, wcześniej wspomniano o liście, którą można zdefiniować jako listę pustą lub jako element wraz z następującą po nim listoą. Drugim takim zagadnieniem jest para podstawowy-indukcyjny. Funkcje rekurencyjne zawierają często rodzaj testów dla „podstawowego” przypadku, w którym nie ma wywołania rekurencyjnego, oraz przypadku „indukcyjnego”, który wymaga jednego lub większej liczby wywołań rekurencyjnych. Dobrze znane dowodzenie indukcyjne wymaga kroku podstawo- wego i indukcyjnego, podobnie jest w przypadku definicji indukcyjnych. Ta para podstawo- wy-indukcyjny jest tak ważna, że te słowa będą specjalnie podkreślane w tekście, w momen- cie każdego wystąpienia przypadku podstawowego lub okroku indukcyjnego. Cykliczność związana z poprawnym zastosowaniem samodefinicji nie jest żadnym pa- radoksem, ponieważ samodefiniujące się podczęści są zawsze „mniejsze” od definiowanego w ten sposób obiektu. Co więcej, po skończonej liczbie kroków przechodzenia do mniej- szych części, dociera się do przypadku podstawowego, w którym kończy się proces samode- finiowania. Przykładowo, lista L jest zbudowana z elementu i listy krótszej o jeden element od L. Kiedy dochodzi się do listy posiadającej zero elementów, otrzymuje się przypadek podstawowy definicji listy: „lista pusta jest listą”. Jako inny przykład można rozważyć funkcję rekurencyjną, która działa poprawnie, jeśli argumenty jej wywołania są (w pewnym sensie) „mniejsze” od argumentów wywołującej ją innej kopii tej samej funkcji. Co więcej, po pewnej liczbie rekurencyjnych wywołań, należy dojść do argumentów tak „małych”, że funkcja nie będzie już wykonywała żadnych rekuren- cyjnych wywołań. Sortowanie Aby posortować listę n elementów, należy tak permutować jej elementy, by zostały ostatecznie ułożone w porządku niemalejącym. ● Przykład 2.1. Przypuśćmy, że mamy listę liczb całkowitych (3, 1, 4, 1, 5, 9, 2, 6, 5). Sortujemy tę listę, permutując ją do postaci sekwencji (1, 1, 2, 3, 4, 5, 5, 6, 9). Należy zauważyć, że sortowa- nie nie tylko porządkuje wartości tak, że każda jest mniejsza lub równa kolejnej liczbie z listy, ale także zachowuje liczbę wystąpień każdej wartości. Posortowana lista zawiera więc dwie jedynki, dwie piątki i po jednej z każdej z pozostałych liczob znajdujących się na oryginalnej liście. ● Listy elementów dowolnego typu można sortować wówczas, gdy istnieje możliwość zdefinio- wania między nimi relacji mniejszości, którą reprezentuje się zazwyczaj znakiem (). Przykładowo, jeśli wartościami do posortowania są liczby całkowite lub zmiennoprzecinkowe, symbol () oznacza znaną wszystkim relację mniejszości liczb całkowitych lub rzeczywistych. Jeśli natomiast tymi war- tościami są ciągi znaków, należy zastosować ich porządek leksykograficzny (patrz ramka „Porządek leksykograficzny”). Niekiedy, gdy dane do posortowania elementy są skomplikowane (np. struktury), do porównania można wykorzystać część każdego z elementów (np. jedno konkretne pole). 2.2. ITERACJE 45 Porządek leksykograficzny Podstawowym sposobem porównywania ciągów znaków jest wykorzystywanie porządku leksykograficznego (ang. lexicographic order). Niech c1c2…ck oraz d1d2…dm będą dwoma ciągami, w których kolejne elementy c i d reprezentują pojedyncze znaki. Długości ciągów wynoszą odpowiednio k oraz m i nie muszą być sobie równe. Zakładamy, że istnieje relacja ( ) porządkująca znaki; przykładowo, w języku C znaki są reprezentowane przez małe liczby całkowite, można więc stałe oraz zmienne znakowe wykorzystać jako liczby całkowite w wy- rażeniach arytmetycznych. Stąd można wykorzystać konwencjonalną relację ( ) dla liczb całko- witych do określania, który z pary rozpatrywanych znaków jest mniejszy. Takie uporządkowanie uwzględnia naturalne wyobrażenie, w którym małe litery znajdujące się wcześniej w alfabecie są „mniejsze” od małych liter znajdujących się w alfabecie później. To samo dotyczy układu wielkich liter. Można teraz zdefiniować dla ciągów znaków uporządkowanie zwane leksykograficznym, słownikowym lub alfabetycznym. Mówimy, że c1c2…ck d1d2…dm, jeśli spełniony jest jeden z dwóch poniższych warunków: (1) Pierwszy ciąg jest prefiksem właściwym (ang. proper prefix)drugiego ciągu, co oznacza, że k m oraz dla i = 1, 2, …, k zachodzi ci = di. Zgodnie z tą zasadą, MQV MQVCTC. Szczególnym przypadkiem spełniającym tę zasadę jest sytuacja, w której k = 0, czyli gdy pierwszy ciąg nie zawiera żadnych znaków. Do oznaczania ciągu pustego (ang. empty string), czyli takiego, który nie zawiera żadnych znaków, będzie wykorzystywany znak ε (grecka litera epsilon). Jeśli k = 0, pierwsza reguła mówi, że ε s dla każdego niepu- stego ciągu s. (2) Dla pewnej wartości i 0, pierwsze i–1 znaków dwóch porównywanych ciągów wza- jemnie sobie odpowiada, ale i-ty znak pierwszego ciągu jest mniejszy od i-tego znaku drugiego ciągu. Oznacza to, że cj = dj dla j = 1, 2, …, i–1, oraz ci di. Zgodnie z tą zasadą, MQU[ MQV[, ponieważ te dwa słowa różnią się na pozycji trzeciej — MQU[ zawiera literę U, która poprzedza literę V znajdującą się na trzeciej pozycji ciągu MQV[. Porównanie a ≤ b jak zwykle oznacza, że albo a b, albo a i b to te same wartości. O liście (a1, a2, …, an) mówimy, że jest posortowana (ang. sorted), jeśli a1 ≤ a2 ≤ … ≤ an, co oznacza, że wartości są ułożone w porządku niemalejącym. Sortowanie (ang. sorting) jest operacją, której na wejściu podaje się dowolną listę (a1, a2, …, an), i która zwraca na wyjściu listę (b1, b2, …, bn) taką, że: (1) Lista (b1, b2, …, bn) jest posortowana. (2) Lista (b1, b2, …, bn) jest permutacją (ang. permutation) listy oryginalnej. Oznacza to, że każ- da wartość znajduje się na liście (a1, a2, …, an) dokładnie taką samą liczbę razy, co na wyni- kowej liście (b1, b2, …, bn). Algorytm sortujący (ang. sorting algorithm) pobiera na wejściu dowolną listę i zwraca jako wynik listę posortowaną, która jest permutacją listy wejścioowej. ● Przykład 2.2. Rozważmy listę słów: MQV[MQU[NCUMQVTúMCYKECMQVCTC Mając takie dane wejściowe i wykorzystując porządek leksykograficzny, algorytm sortujący zwróci następującą listę wyjściową: MQU[, MQV, MQVCTC, MQV[, NCU, TúMCYKEC. ● 46 2. ITERACJA, INDUKCJA I REKURENCJA Konwencja związana z nazwami i wartościami Zmienną można traktować jako skrzynkę zawierającą nazwę i wartość. W przypadku odwoły- wania się do zmiennej, np. CDE, do zapisu jej nazwy będzie wykorzystywana czcionka o stałej szerokości znaków. Kiedy jednak odwołanie będzie odnosiło się do wartości zmiennej CDE, wykorzystywana będzie kursywa, np. abc. Podsumowując, CDE odnosi się do nazwy skrzynki, zaś abc do jej zawartości. Sortowanie przez wybieranie — iteracyjny algorytm s ortujący Przypuśćmy, że mamy tablicę # zawierającą n liczb całkowitych, którą chcemy posortować w po- rządku niemalejącym. Można to zrobić wielokrotnie powtarzając krok, w którym wyszukiwany jest najmniejszy1 element nieposortowanej części tablicy i wymieniany z elementem znajdującym się na pierwszej pozycji nieposortowanej części tablicy. W pierwszej iteracji znajdujemy (wybie- ramy) najmniejszy element z wszystkich wartości znajdujących się w tablicy #=PŌ? i wymie- niamy go z elementem #=?2. W drugiej iteracji wybieramy najmniejszy element w tablicy #=P? i wymieniamy go z elementem #=?, następnie wykonujemy kolejne iteracje. Na początku (i+1). iteracji, tablica #=K? zawiera i najmniejszych elementów tablicy # ułożonych w porządku nie- malejącym, pozostałe elementy tablicy nie są uporządkowane. Stan tablicy # bezpośrednio przed (i+1). iteracją przedstawiono na rysunku 2.1. RYSUNEK 2.1. Stan tablicy bezpośrednio przed (i+1). iteracją algorytmu sortowania przez selekcję W (i+1). iteracji znajdujemy najmniejszy element tablicy #=KPŌ? i wymieniamy go z ele- mentem #=K?. Po tej iteracji tablica #=K? zawiera więc i+1 najmniejszych elementów posorto- wanych w porządku niemalejącym. Po (i–1). iteracji posortowana jest cała tablica. Na listingu 2.1 przedstawiono napisaną w języku C funkcję realizującą sortowanie przez wybie- ranie. Funkcja, którą nazwano 5GNGEVKQP5QTV, pobiera dwa argumenty: tablicę # oraz jej długość n. LISTING 2.1. Iteracyjne sortowanie przez wybieranie XQKF5GNGEVKQP5QTV KPV#=?KPVP ] KPVKLUOCNNVGOR  HQT KKPŌK ]  RT[RKUWLGO[OKGPPGLUOCNNKPFGMURKGTYUGIQ  1 Nie musi to być dokładnie jeden najmniejszy element — w tablicy może istnieć wiele wystąpień naj- mniejszej wartości. W takim przypadku, wystarczy, że znajdzi2emy dowolne wystąpienie tej wartości. 2 Do opisywania przedziałów elementów w tablicach będzie stosowana konwencja z języka programowa- nia Pascal. Jeśli # jest tablicą, to zapis #=KL? oznacza elementy tej tablicy o indeksach od K do L włącznie. 2.2. ITERACJE 47  Y[UVæRKGPKCPCLOPKGLUGIQGNGOGPVWPKGRQUQTVQYCPGML   EúħEKVCDNKE[   UOCNNK  HQT LK LPL  KH #=L?#=UOCNN?  UOCNNL  YV[OOKGLUEWOKGPPCUOCNNCYKGTCKPFGMU   RKGTYUGIQPCLOPKGLUGIQGNGOGPVWVCDNKE[   #=KPŌ?Y[OKGPKCO[YKúE#=UOCNN?#=K?   VGOR#=UOCNN?  #=UOCNN?#=K?  #=K?VGOR _ _ W wierszach od (2) do (5) zostaje wybrany najmniejszy element nieposortowanej części tablicy, czyli #=KPŌ?. Pierwszą operacją jest przypisanie zmiennej indeksowej UOCNN wartości i w wier- szu (2). W pętli HQT w wierszach od (3) do (5) zostają przeanalizowane kolejno wszystkie większe indeksy L i zmiennej UOCNN zostaje przypisana wartość j, jeśli element #=L? zawiera wartość mniej- szą niż wszystkie elementy z przedziału #=KLŌ?. Efektem tych działań jest przypisanie zmiennej UOCNN wartości indeksu pierwszego wystąpienia najmniejszoego elementu tablicy #=KPŌ?. Po wybraniu odpowiedniej wartości indeksu dla zmiennej UOCNN zostaje wymieniony element na wskazywanej przez ten indeks pozycji z elementem #=K? (patrz wiersze od (6) do (8)). Jeśli small = i, wymiana jest dokonywana, tyle że nie zmienia ona układu w tablicy. Warto zauważyć, że aby wymienić wartości dwóch elementów w tablicy, trzeba wykorzystać tymczasową zmienną do prze- chowania wartości jednego z nich. Wartość elementu #=UOCNN? zostaje więc przypisana zmiennej VGOR w wierszu (6), wartość elementu #=K? zostaje przypisana elementowi #=UOCNN? w wierszu (7) i wreszcie oryginalna wartość elementu #=UOCNN? przechowywana w zmiennej VGOR zostaje przypi- sana do elementu #=K? w wierszu (8). ● Przykład 2.3. Poniżej przeanalizowano działanie funkcji 5GNGEVKQP5QTV dla różnych danych wejściowych. Pierwszym przypadkiem jest tablica wejściowa nie zawierająca żadnych elementów. Jeśli n = 0, ciało pętli HQT z wiersza (1) nie będzie wykonane ani razu, zatem, zgodnie z oczekiwa- niami, funkcja 5GNGEVKQP5QTV nie wykona żadnej operacji. Kolejnym przypadkiem jest tablica wejściowa zawierająca tylko jeden element. Ponownie, ciało pętli HQT z wiersza (1) nie zostanie wykonane ani razu. Odpowiedź funkcji będzie więc pra- widłowa, ponieważ tablica jednoelementowa jest zawsze posortowana. Przypadki, w których n jest równe 0 lub 1 są ważnymi warunkami granicznymi, dla których należy sprawdzać przebieg wszyst- kich algorytmów czy programów. Wreszcie, uruchamiamy funkcję 5GNGEVKQP5QTV dla małej tablicy złożonej z czterech elementów od #=? do #=?: Pętla zewnętrzna rozpoczyna działanie przy wartości i = 0 i w wierszu (2) zmiennej UOCNN zostaje przy- pisana wartość 0. Wiersze od (3) do (5) tworzą pętlę wewnętrzną, w której L przyjmuje kolejno war- tości 1, 2 i 3. Dla j = 1 spełniony jest warunek z wiersza (4), ponieważ element #=? o wartości 30 48 2. ITERACJA, INDUKCJA I REKURENCJA Sortowanie na podstawie kluczy Kiedy jest przeprowadzany proces sortowania, dla sortowanych wartości stosuje się operację porównania. Porównanie to jest często wykonywane tylko dla określonych części wartości. Taka cześć używana w operacjach porównywania nosi noazwę klucza (ang. key). Przykładowo, wykaz studentów biorących udział w danych zajęciach może być tablicą # zawierającą struktury języka C postaci: UVTWEV567 06] KPVUVWFGPV+  EJCT PCYKUMQ EJCTQEGPC _#=/#:? Może zaistnieć potrzeba posortowania tej tablicy na podstawie identyfikatora studenta, na- zwiska lub oceny; każdy z tych elementów po kolei stałby się więc kluczem sortowania. Przy- kładowo, jeśli należałoby posortować struktury na podstawie identyfikatora studenta, wyko- nywane porównania musiałyby mieć postać: #=L?UVWFGPV+ #=UOCNN?UVWFGPV+ w wierszu (4) funkcji 5GNGEVKQP5QTV. Typem tablicy # i tymczasowej zmiennej VGOR (wykorzy- stywanej do zamiany wartości) byłaby struktura 567 06, zamiast liczby całkowitej. Należy pamiętać, że wymieniana jest cała struktura, nie tyloko pola kluczy. Ponieważ wymiana całych struktur jest czasochłonna, bardziej wydajnym rozwiązaniem byłoby wykorzystanie drugiej tablicy ze wskaźnikami do struktur 567 06 i sortowanie tylko zawartych w niej wskaźników. Same struktury pozostałyby nienaruszone w pierwszej tablicy. Opracowanie takiej wersji sortowania przez wybieranie autorzy pozostawiają Czytelnikowi jako ćwiczenie. jest mniejszy od elementu A[small], zawierającego wartość 40. W wierszu (5) zmiennej UOCNN zo- staje więc przypisana wartość 1. W drugiej iteracji pętli zawartej w wierszach od (3) do (5), dla j = 2, ponownie spełniony jest warunek z wiersza (4), ponieważ A[2] A[1]. W wierszu (5) następuje więc przypisanie zmiennej UOCNN wartości 2. W ostatniej iteracji tej pętli, dla j = 3, także spełniony jest warunek z wiersza (4), ponieważ A[3] A[2]. W wierszu (5) zmiennej UOCNN zostaje więc przy- pisana wartość 3. W tym momencie następuje przejście z pętli wewnętrznej do wiersza (6). Zmiennej VGOR zo- staje przypisana wartość 10, czyli wartość elementu A[small], następnie wartość elementu A[0], 40, zostaje w wierszu (7) przypisana elementowi #=?, po czym elementowi #=? zostaje przypisana wartość 10 w wierszu (8). Na tym kończy się pierwsza iteracja pętli zewnętrznej; tablica # wyglą- da w tym momencie następująco: W drugiej iteracji pętli zewnętrznej, dla i = 1, w wierszu (2) zmiennej UOCNN zostaje przypisana wartość 1. Pętla wewnętrzna przypisuje początkowo zmioennej L wartość 2 i, ponieważ A[2] A[1], 2.2. ITERACJE 49 w wierszu (5) zmiennej UOCNN zostaje przypisana wartość 2. Dla L = 3, warunek z wiersza (4) nie jest spełniony, ponieważ A[3] ≥ A[2]. Zmienna small ma więc wartość 2 w momencie, gdy stero- wanie dochodzi do wiersza (6). W wierszach od (6) do (8) zostają zamienione elementy #=? i #=?, w efekcie czego otrzymuje się tablicę: Mimo że tablica # jest już posortowana, musi zostać wykonana ostatnia iteracja pętli zewnętrznej, dla i = 2. Zmiennej UOCNN zostaje więc w wierszu (2) przypisana wartość 2 i uruchomiona pętla wewnętrzna tylko dla przypadku, w którym j = 3. Ponieważ warunek w wierszu (4) nie jest spełniony, zmienna small nadal przechowuje wartość 2, zatem w wierszach od (6) do (8) następuje „zamiana” elementu #=? z samym sobą. Czytelnik sam powinien sprawdzić, czy taka wymiana dla small = i rzeczywiście nie zmienia układu w tablicy. ● Listing 2.2 przedstawia przykładowy sposób wykorzystania funkcji 5GNGEVKQP5QTV w kom- pletnym programie sortującym ciąg n liczb całkowitych przy założeniu, że n ≤ 100. W wierszu (1) następuje odczytanie n liczb całkowitych i zapisanie ich w tablicy #. Jeśli liczba danych wejścio- wych przekroczy /#:, w tablicy zapisywanych jest jedynie pierwsze /#: liczb całkowitych. W tym miejscu przydatny byłby komunikat ostrzegający użytkownika o zbyt dużej liczbie danych, jednak w prezentowanym programie pominięto ten element. W wierszu (3) następuje wywołanie funkcji 5GNGEVKQP5QTV w celu posortowania tablicy. Wier- sze (4) i (5) są odpowiedzialne za wydrukowanie liczb całkowitych w posortowanym porządku. LISTING 2.2. Program sortujący elementy tablicy za pomocą algorytmu sorto2wania przez wybieranie KPENWFGUVFKQJ FGHKPG/#: KPV#=/#:? XQKF5GNGEVKQP5QTV KPV#=?KPVP  OCKP ] KPVKP  QFE[VWLGO[FCPGYGLħEKQYGKCRKUWLGO[LGYVCDNKME[#   HQT PP/#:UECPH  F#=P?  1(P    5GNGEVKQP5QTV #P  UQTVWLG#   HQT KKPK  RTKPVH F P#=K?  Y[ħYKGVNC#  _ XQKF5GNGEVKQP5QTV KPV#=?KPVP ] KPVKLUOCNNVGOR HQT KKPŌK ] UOCNNK HQT LK LPL 50 2. ITERACJA, INDUKCJA I REKURENCJA KH #=L?#=UOCNN? UOCNNL VGOR#=UOCNN? #=UOCNN?#=K? #=K?VGOR _ _ Ćwiczenia 2.2.1. Przeprowadź symulację działania funkcji 5GNGEVKQP5QTV dla tablicy zawierającej następujące elementy: (a) 6, 8, 14, 17, 23; (b) 17, 23, 14, 6, 8; (c) 23, 17, 14, 8, 6. Ile porównań i zamian będzie wykonywanych dla każdegoo z powyższych przypadków? 2.2.2**. Jaka jest minimalna i maksymalna liczba (a) porównań i (b) zamian, które funkcja 5GNGE VKQP5QTV musi przeprowadzić do posortowania ciągu n elementów? 2.2.3. Napisz w języku C funkcję, która pobiera jako argumenty dwie listy jednokierunkowe zło- żone ze znaków i zwraca wartość 647 , jeśli pierwszy ciąg znaków leksykograficznie poprzedza drugi. Wskazówka: zaimplementuj opisany w niniejszym rozdziale algorytm porównywania cią- gów znaków. Wykorzystaj rekurencję w postaci wywołania funkcji przez nią samą dla reszt cią- gów znaków, jeśli zostanie stwierdzone, że pierwsze znaki obu ciągów są takie same. Alternatyw- nym rozwiązaniem jest opracowanie wykonującego identoyczne działania algorytmu iteracyjnego. 2.2.4*. Zmodyfikuj program z ćwiczenia 2.2.3 tak, by ignorowało wielkość porównywanych znaków. 2.2.5. Co dzieje się w algorytmie sortowania przez wybieroanie, jeśli wszystkie elementy są takie same? 2.2.6. Zmodyfikuj program z listingu 2.2 tak, by program wykonywał sortowanie przez wybieranie dla elementów tablicy nie będących liczbami całkowitymi, lecz strukturami 567 06 opisanymi w ramce „Sortowanie na podstawie kluczy”. Zakładamy, że kluczeom jest pole UVWFGPV+ . 2.2.7*. Jeszcze raz zmodyfikuj program z listing 2.2 tak, by program sortował elementy dowolnego typu 6. Możesz jednak założyć, że istnieje funkcja MG[, która jako argument pobiera element typu 6 i zwraca klucz dla tego elementu, będący wartością pewnego typu -. Załóż także, że istnieje funkcja NV, która jako argumenty pobiera dwa elementy typu - i zwraca wartość 647 , jeśli pierwszy jest „mniejszy” od drugiego; w przeciwnym razie, funkcja poowinna zwrócić wartość (#.5 . 2.2.8. Zamiast wykorzystywać całkowitoliczbowe indeksy w tablicy #, możemy do określania po- zycji elementów tablicy wykorzystać wskaźniki do liczb całkowitych. Przekształć algorytm sorto- wania przez wybieranie z listingu 2.2 tak, by wykorzyostywał wskaźniki. 2.2.9*. Jak wspomniano w ramce „Sortowanie na podstawie kluczy”, jeśli elementy do posorto- wania są dużymi strukturami, jak w przypadku struktury 567 06, sensowne jest pozostawienie tych struktur nienaruszonych w ich tablicy i posortowanie wskaźników do nich, znajdujących się w osobnej tablicy. Opracuj także taką wersję sortowaonia przez wybieranie. 2.3. DOWODY INDUKCYJNE 51 2.2.10. Napisz iteracyjny program wyświetlający odrębne elementy tablicy złożonej z liczb całko- witych. 2.2.11. Wykorzystaj opisane na początku tego rozdziału notaocje Σ oraz Π do wyrażenia: (a) sumy liczb nieparzystych od 1 do 377; (b) sumy kwadratów liczb parzystych od 2 do n (załóż, że n jest liczbą parzystą); (c) iloczynu potęg liczby 2 od 8 do 2k. 2.2.12. Wykaż, że dla small = i, wiersze od (6) do (8) na listingu 2.1 (operacja zamiany wartości) nie mają wpływu na układ w tablicy #. 2.3. Dowody indukcyjne Indukcja matematyczna (ang. mathematical induction) jest przydatną techniką dowodzenia, że twierdzenie S(n) jest prawdziwe dla wszystkich nieujemnych liczb całkowitych n lub, uogólniając, dla wszystkich liczb całkowitych większych lub równych danemu ograniczeniu dolnemu. Przykła- dowo, we wprowadzeniu do niniejszego rozdziału zasugerowano, że w przypadku twierdzenia ∑ poprzez indukcję względem n można dowieść, że jest ono prawdziwe dla wszyst- kich n ≥ 1. 2/)1 nn ( i 1 = + n i = Niech S(n) będzie dowolnym twierdzeniem dotyczącym liczby całkowitej n. W najprostszej formie dowodu indukcyjnego twierdzenia S(n) dowodzi się dwóch faktów: (1) Przypadku podstawowego (ang. basis case), za który często przyjmuje się twierdzenie S(0). Przypadkiem podstawowym może jednak być równie dobrze S(k) dla dowolnej liczby całko- witej k. Dowodzi się wówczas prawdziwości twierdzenia S(n) dla n ≥ k. (2) Kroku indukcyjnego (ang. inductive step), gdzie dowodzi się, że dla wszystkich n ≥ 0 (lub dla wszystkich n ≥ k, jeśli przypadkiem podstawowym jest S(k)), S(n) implikuje S(n+1). W tej części dowodu zakłada się, że twierdzenie S(n) jest prawdziwe. S(n) nazywa się często hipote- zą indukcyjną (ang. inductive hypothesis) — zakładając, że jest prawdziwa, należy udowodnić, że twierdzenie S(n+1) jest prawdziwe. Rysunek 2.2 ilustruje indukcję rozpoczynaną od wartości 0. Dla każdej liczby całkowitej n, należy udowodnić twierdzenie S(n). Dowód dla twierdzenia S(1) wykorzystuje twierdzenie S(0), dowód dla twierdzenia S(2) wykorzystuje twierdzenie S(1) itd. (kierunek dowodzenia oznaczono strzałkami). Sposób uzależnienia kolejnych twierdzeń od ich poprzedników jest identyczny dla wszyst- kich n. Oznacza to, że za pomocą jednego dowodu kroku indukcyjnego dowodzi się poprawności wszystkich kroków oznaczonych strzałkami na rysunkuk 2.2. RYSUNEK 2.2. W dowodzie indukcyjnym każdy przypadek twier2dzenia S(n) jest dowodzony za pomocą twierdzenia dotyczącego kolejnej, mniejszej wartości n 52 2. ITERACJA, INDUKCJA I REKURENCJA Nazewnictwo parametru indukcji Niekiedy przydatne jest wyjaśnienie indukcji za pomocą intuicyjnego opisu znaczenia zmiennej n wykorzystywanej w dowodzonym twierdzeniu S(n). Jeśli n nie ma szczególnego znaczenia (patrz przykład 2.4), mówimy po prostu, że „dowodzimy prawdziwości twierdzenia S(n) za pomocą indukcji względem n”. W przeciwnym razie, jeśli n ma jasne znaczenie (patrz przy- kład 2.6, w którym n jest liczbą bitów wykorzystywanych w słowach kodu), możemy powie- dzieć, że „wykazujemy prawdziwość twierdzenia S(n) względem liczby bitów stosowanych w słowach kodu”. Przykład 2.4. Aby przybliżyć Czytelnikowi indukcję matematyczną, poniżej zostanie udowod- nione następujące n TWIERDZENIE S(n): ∑ n 2 2 = i + 1 1 − dla dowolnego n ≥ 0. i = 0 Twierdzenie to określa, że suma potęg liczby 2, od potęgi zerowej do n-tej, jest o 1 mniejsza od (n+1). potęgi liczby 23. Przykładowo, 1+2+4+8 = 16–1. Dowód przedstawiono poniżej. PODSTAWA. Aby udowodnić podstawę, w twierdzeniu S(n) za n należy podstawić 0. Otrzymujemy: 0 =∑ 2 i 1 2 1 − (2.2) =i 0 Dla i = 0, w powyższej sumie istnieje tylko jeden składnik po lewej stronie równania (2.2); lewa strona tego równania jest więc sumą jednego wyrazu 20, czyli 1. Prawa strona równania (2.2), po- staci 21–1, czyli 2–1, również jest równa 1. Stanowi to dowód podstawy S(n), gdyż wykazano prawdziwość tego równania dla n = 0. INDUKCJA. Następnie należy udowodnić krok indukcyjny. Zakładamy, że S(n) jest prawdziwe i do- wodzimy prawdziwości tego samego równania dla n zastąpionego przez n+1. Należy więc dowieść prawdziwości równania S(n+1): n + 1 ∑ n i 2 2 = + 2 1 − (2.3) Aby wykazać, że równanie (2.3) jest prawdziwe, najpierw orozważamy sumę po jego lewej stronie: i = 0 n + 1 ∑ i = 0 i 2 3 Prawdziwość twierdzenia S(n) można wykazać bez stosowania indukcji — za pomocą wzoru na sumę wyrazów ciągu geometrycznego. Jednak ten prosty przykład posłuży do zaprezentowania techniki dowodzenia za pomocą indukcji matematycznej. Co więcej, dowody wzorów na sumy wyrazów ciągu geometrycznego i aryt- metycznego, z którymi Czytelnik spotkał się zapewne w szkole średniej, są raczej nieformalne, i mówiąc ściśle, właśnie indukcję matematyczną powinno się wykorzystać do dowied2zenia ich prawdziwości. 2.3. DOWODY INDUKCYJNE 53 Powyższa suma jest niemal taka sama, jak poniższa suoma po lewej stronie równania S(n): i 2 n ∑ i = 0 Wyjątkiem jest dodatkowy składnik sumy w równaniu (2.3o) dla i = n+1, czyli 2n+1. Ponieważ można założyć, że w dowodzie równania (2.3) hipoteza indukcyjna S(n) jest praw- dziwa, należy znaleźć sposób na wykorzystanie S(n) w dalszych rozważaniach. Można to osiągnąć, rozbijając sumę z równania (2.3) na dwie części, z których jedną jest suma znana z równania dla S(n). Oznacza to oddzielenie ostatniego składnika, dla i = n+1, i zapisanie: n 1 + n = ∑∑ 2 i i = 0 i = 0 i 2 + 2 n 1 + (2.4) n i 2 i 0 = Teraz można wykorzystać równania S(n), zastępując po prawej stronie równania (2.4) sumę ∑ wyrażeniem 2n+1–1: n + 1 =∑ 2 i n + 1 2 +− 21 n + 1 (2.5) i = 0 Po uproszczeniu prawej strony równania (2.5) otrzymujemy 2×2n+1–1, czyli 2n+2–1. Widać teraz, że suma po lewej stronie równania (2.5) jest identyczna z sumą po lewej stronie równania (2.3), zaś prawa strona rów
Pobierz darmowy fragment (pdf)

Gdzie kupić całą publikację:

Wykłady z informatyki z przykładami w języku C
Autor:
,

Opinie na temat publikacji:


Inne popularne pozycje z tej kategorii:


Czytaj również:


Prowadzisz stronę lub blog? Wstaw link do fragmentu tej książki i współpracuj z Cyfroteką: