Cyfroteka.pl

klikaj i czytaj online

Cyfro
Czytomierz
00326 007039 19024346 na godz. na dobę w sumie
Tablice informatyczne. Algorytmy - książka
Tablice informatyczne. Algorytmy - książka
Autor: Liczba stron: 8
Wydawca: Helion Język publikacji: polski
ISBN: 978-83-283-5206-3 Data wydania:
Lektor:
Kategoria: ebooki >> komputery i informatyka >> programowanie >> c++ - programowanie
Porównaj ceny (książka, ebook (-35%), audiobook).

Cała wiedza w jednym miejscu!

Nie pamiętasz jakiegoś algorytmu? Nie wiesz, jaką strukturę danych należy zastosować? Nie masz pojęcia, jak wyznaczyć złożoność obliczeniową algorytmu? Nie martw się, Twoje problemy należą już do przeszłości!

Tablice informatyczne. Algorytmy pozwolą Ci szybko odnaleźć i przypomnieć sobie podstawowe zagadnienia dotyczące algorytmów i ich zastosowania. Będą doskonałą ściągą na wykładach lub laboratoriach, a nawet w pracy. Przykłady opracowane w C++ lub pseudokodzie pomogą właściwie zrozumieć i wdrożyć odpowiednie rozwiązania.

Algorytmika nigdy nie była prostsza!

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

Darmowy fragment publikacji:

Algorytmy TABLICE INFORMATYCZNE • Piotr Wróblewski Jest to zależność liniowa, gdzie każdej z n danych wejściowych algorytm musi poświęcić pewien czas na wykonanie swoich obliczeń. O(log n) Lepsza od liniowej. Logarytm liczby x 0 o pod- stawie b ≠1, oznaczony jako u = log bx, jest to liczba u spełniająca zależność bu = x, np. 3 = log28. Jeśli klasa problemu rośnie geometrycznie (np. o rząd wielkości ze 100 na 1000), to wzrost złożoności będzie arytmetyczny (tutaj dwukrotny). Jeśli n rośnie niezbyt szybko, to algorytm zwalnia, ale nie drastycznie. Ze złożonością logarytmiczną spotkamy się na przykład w algorytmie przeszuki- wania posortowanej tablicy, gdzie w każdym kroku algorytmu będziemy pomijali część danych. Klasa ta często spotykana jest w rozważaniach kombinatorycznych, gdzie mamy do czynienia z regułą „każdy z każdym”, np. dodawanie matryc o rozmiarach n×n. Często przytaczana jest jako swego rodzaju stra- szak, choć w praktyce algorytmy tej klasy mogą być też używane, oczywiście jeśli zwracają wyniki w sensownym dla użytkownika czasie. O(n2) O(2n) Przykład wyliczania złożoności algorytmu A — czas wykonania instrukcji przypisania C — czas wykonania instrukcji porównania int tab[n][n]; void zerowanie(){ int i,j; i=0; // A while (i n){ // C j=0; // A while (j =i){ // C tab[i][j]=0; // A REKURENCJA • Algorytmy iteracyjne polegają na n-krotnym wykonywaniu instrukcji w taki sposób, aby wyniki uzyskane podczas poprzednich iteracji (przebiegów) mogły służyć jako dane wejściowe do kolejnych (sterowanie przez instrukcje pętli, np. for lub while). • Algorytmy rekurencyjne realizują zapętlenie nieco inaczej, a mianowicie poprzez wywoływanie tej samej procedury (funkcji) przez siebie samą z innymi parametrami. • Matematycy stosują często zapis rekurencyjny, np. funk- cja silnia: 0!=1, n!=n*(n-1)! Typy rekurencji • Notacja matematyczna pokazana na przykładzie funkcji silnia może być określona jako rekurencja naturalna. • Informatycy, w celu optymalizacji czasu wykonania pro- gramów, używają tzw. rekurencji z parametrem dodatko- wym, gdzie parametry dodatkowe służą do przekazywania częściowo obliczonych wyników. // Przykład rekurencji z parametrem dodatkowym unsignedlongintsilnia (unsignedlong int x, unsignedlongint tmp=1){ if (x==0) return tmp; else return silnia(x-1, x*tmp); } // Przykładowe wywołanie: silnia(5) WPROWADZENIE Tablice pomogą Ci szybko przypomnieć sobie podstawo- we zagadnienia dotyczące algorytmów i ich zastosowania. Opracowania tego możesz użyć jako przydatnej ściągi na wykładach lub laboratoriach. Tam, gdzie istniała taka możliwość, pokazałem także reprezentatywne fragmenty kodu w C++, a jeśli nie było to możliwe z uwagi na rozmiar listingu, posłużyłem się pseudokodem. Tablice napisane są w oparciu o książkę Algorytmy, struktury danych i techniki programowania. PODSTAWOWE POJĘCIA Algorytm • Skończony ciąg reguł, który stosuje się na skończonej liczbie danych, aby rozwiązywać zbliżone do siebie klasy problemów. • Zespół reguł charakterystycznych dla pewnych obliczeń lub czynności informatycznych. Pochodzenie Termin algorytm pochodzi od nazwiska perskiego matema- tyka Muhammada ibn Musy al-Chuwarizmiego, który żył w IX wieku n.e. Jego zasługą jest dostarczenie klarownych reguł wyjaśniających krok po kroku zasady operacji arytme- tycznych wykonywanych na liczbach dziesiętnych. Algorytmy deterministyczne i niedeterministyczne • Algorytm jest deterministyczny, gdy wynik działania jest jednoznacznie okr eślony przez warunki początkowe (pa- rametry) niezależnie od liczby jego wykonań. • Algorytm niedeterministyczny można uzyskać, wprowa- dzając czynnik losowości (np. generator liczb losowych), przetwarzanie równoległe lub tzw. logikę kwantową (stany pośrednie między 0 i 1). Budowa algorytmu informatycznego • Dane wejściowe (w ilości większej lub równej 0) pochodzą z dobrze zdefi niowanego zbioru, który tworzą liczby całko- wite, napisy lub ciągi znaków, złożone struktury wejściowe (np. grafy, zbiory). • Wynik produkowany przez algorytm (rezultat wykonania) nie zawsze jest numeryczny (np. napisy, zbiory, listy). • Warunki wejściowe mają n a celu m.in. wyeliminowanie danych, które nie zawierają się w domenie obsługiwanej przez algorytm (np. pewien algorytm może akceptować wyłącznie dodatnie liczby całkowite). • Struktury danych umożliwiają przechowywanie i obsłu- gę danych przetwarzanych przez algorytm (np. tablice, listy, drzewa). powinno być możliwe precyzyjne określenie czasu wy- konania T(A, D)). • Precyzyjny — każdy krok algorytmu musi być jedno- znacznie zdefi niowany. • Uniwersalny — dany algorytm można zastosować do rozwiązywania całej klasy zadań, a nie tylko jednego konkretnego zadania (np. algorytm sortowania powinien dobrze działać zarówno na tablicy liczb całkowitych, jak i na tablicy obiektów złożonych). • Efektywny — algorytm powinien wykonywać swoje zadanie w jak najkrótszym czasie i wykorzystywać do tego celu jak najmniejszą ilość pamięci (komputery mają ograniczoną pamięć i moc obliczeniową). Algorytm Euklidesa (NWD) Pojęcie algorytmu bywa ilustrowane przepisem greckiego matematyka Euklidesa (365 – 300 rok p.n.e.) na obliczanie największego wspólnego dzielnika (NWD) dwóch liczb : a i b. Algorytm NWD można opisać na wiele sposobów prowadzą- cych do tego samego wyniku końcowego. NWD (dane wejściowe: a i b; zmienna pomocnicza: r) { jeśli b równa się zero, to wynikiem jest a; wprzeciwnymwypadku podstaw za r resztę z dzielenia a przez b; rezultat: NWD(q, r); } #include iostream using namespace std; int nwd (int a, int b){ if (b==0) return a; else return nwd (b, a b); // Funkcja modulo // w C++ } Cechy algorytmu • Skończony — wynik algorytmu musi zostać kiedyś dostarczony (dla algorytmu A i danych wejściowych D Wynik działania algorytmu będzie taki sam zarówno w przy- padku zastosowania pseudonotacji, jak i języka programo- wania. Schemat algorytmu ZŁOŻONOŚĆ OBLICZENIOWA • Który z dwóch programów wykonujących to samo za- danie (ale odmiennymi metodami) jest efektywniejszy? Efektywność analizuje się zazwyczaj pod kątem czasu wykonania lub zajętość pamięci. • Informacja typu „program jest szybki, bo wykonał się w 1 minutę” nie daje żadnej miarodajnej informacji! • Miara złożoności obliczeniowej musi być reprezentatywna, aby użytkownicy na przykład małego komputera osobiste- go i potężnej stacji roboczej — obaj korzystający z tego samego algorytmu — mogli się ze sobą porozumieć co do sprawności obliczeniowej bez wyszczególniania, jakich używają komputerów, wersji kompilatora, rodzajów i architektury procesora. • Parametrem najczęściej decydującym o czasie wykonania określonego algorytmu jest rozmiar danych n, z którymi ma on do czynienia. Rozmiar danych ma wiele znaczeń: dla funkcji sortującej tablicę będzie to jej rozmiar, dla programu obliczającego wartość funkcji silnia — wiel- kość danej wejściowej. Notacja dużego O Funkcja oznaczana jako T ukazuje rezultat dokładnych obli- czeń działania algorytmu i jest nazywana złożonością prak- tyczną. Gdy szukamy funkcji O, interesuje nas typ funkcji matema- tycznej występującej w T, który odgrywa w niej najważniejszą rolę, wpływając najsilniej na czas wykonywania programu. Przykłady poniżej. T(n) 6 3n+1 n2–n+1 2n+n2+4 O(n) O(1) O(n) O(n2) O(2n) O(1) O(n) Liczba operacji wykonywanych przez algorytm jest niezależna od rozmiarów problemu (co nie oznacza, że będzie mała!). Algorytm wykonuje się w czasie proporcjonal- nym do rozmiaru problemu, np. przetwarzanie sekwencyjne ciągu znaków, obsługa kolejki itp. j=j+1; // A } i=i+1; // A } } Pętla while wykonuje n razy instrukcje zawarte w nawia- sach klamrowych, warunek natomiast jest sprawdzany n+1 razy. Korzystając z tej uwagi i informacji zawartych w liniach komentarza, możemy napisać:  ∑ 2  = + +  ) A  +( C C A T n ( ) ∑ C 2 + + A i = 1 j = 1 2 N . i Po usunięciu sumy z wewnętrznego nawiasu otrzymamy: T n ( ) = + + C A N ( ∑ 2 i = 1 A + +( C i C 2 + ) A ) . 2 (*) Przypomnijmy jeszcze użyteczny wzór na sumę szeregu liczb naturalnych od 1 do N: 1 2 3 + + + + ... N = ( + N N 2 ) 1 . Po jego zastosowaniu w równaniu (*) otrzymamy: T n ( ) = + + C A +( N A C 2 ) + ( + N N 2 ) 1 +( C ) A . 2 Ostateczne uproszczenie wyrażenia powinno nam dać: T n ( ) = A ( + 1 3 N N + 2 ) + C   C 1 2 5 + , + 2 N 2   ; co sugeruje od razu, że analizowany program jest klasy O(n2). Porady dotyczące optymalizacji • Jeśli algorytm ma za zadanie coś obliczyć kilka razy, to jego optymalizacja może mijać się z celem. Taniej bę- dzie spróbować go uruchomić lub ekstrapolować czas wykonania. • Prostota: czasem optymalne algorytmy są zupełnie nie- zrozumiałe na pierwszy rzut oka i stopień ich skompliko- wania łatwo prowadzi do błędów logicznych. • Precyzja, tak potrzebna na przykład w algorytmach nu- merycznych, może być ważniejsza niż klasa algorytmu lub jego fragmentu. • Notacja dużego O tak naprawdę odgrywa rolę dla takich danych wejściowych, dla których czas wykonania może zbliżać się do bardzo dużych liczb. W praktyce może to oznaczać, że algorytm „kwadratowy” będzie w pewnych konfi guracjach lepszy od „logarytmicznego”! fib fib fib n (0) 0, (1) 1, () = = = ( 1) fib n − + fib n − gdzie n ≥ ( 2), 2 Funkcja Fibonacciego zapisana w formie rekurencyjnej W ciągu Fibonacciego dwa wyrazy ciągu są równe 1, a każdy następny powstaje jako suma dwóch poprzednich: 1, 1, 2, 3, 5, 8, 13… Jeżeli podzielimy przez siebie dowolne kolejne dwa wyrazy ciągu Fibonacciego, to ich stosunek będzie równy zawsze tej samej złotej liczbie φ (fi ) równej w przybliżeniu 1,618. Liczby ciągu Fibonacciego i złota liczba pojawiają się często w przyrodzie (np. rozmnażanie się zwierząt, wzrost roślin), muzyce (prawa harmonii), sztuce i naukach ścisłych. unsigned long int fi b(int x){ if (x 2) return x; else return fi b(x-1)+fi b(x-2); } Pułapki rekurencji Rekurencja umożliwia proste opisanie skomplikowanych al- gorytmów, ale gdy jest realizowana przez fi zyczne komputery, ukazuje istotne wady. Niska efektywność wskutek wielokrotnego wywoływania tych samych fragmentów kodu. Zobacz drzewko wywołań funkcji fi b(4), cała gałąź fi b(2) jest zdublowana! Nieskończona liczba wywołań rekurencyjnych dla pewnych konfiguracji danych wejściowych, np. StadDoWiecznosci(2), co szybko prowadzi do zawiesze- nia się programu z powodu przekroczenia dostępnej pamięci.
Pobierz darmowy fragment (pdf)

Gdzie kupić całą publikację:

Tablice informatyczne. Algorytmy
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ą: