Wprowadzenie do Algorytmów i Struktur Danych PDF

Wprowadzenie do przedmiotu Algorytmy i struktury danych Algorytmy i struktury danych – Jan G. Bazan 1 Witryna internetowa wykładu http://fenix.univ.rzeszow.pl/bazan/archiwum/ Dostęp wymaga autoryzacji:  Konto: asd  Hasło: algosys  Witryna będzie zawierać: prezentacje wykładow...

Wprowadzenie do przedmiotu Algorytmy i struktury danych Algorytmy i struktury danych – Jan G. Bazan 1 Witryna internetowa wykładu http://fenix.univ.rzeszow.pl/bazan/archiwum/ Dostęp wymaga autoryzacji:  Konto: asd  Hasło: algosys  Witryna będzie zawierać: prezentacje wykładowe, materiały pomocnicze do ćwiczeń, przykłady programów, pytania do egzaminu itd. Algorytmy i struktury danych – Jan G. Bazan 2  Literatura  Banachowski, L., Kreczmar, A.: Elementy analizy algorytmów, WNT (1989).  Dańko, A, Truong Lan Le, Mirkowska, G., Rembelski, P., Smyk, A., Sydow, M.: Algorytmy i struktury danych – zadania, Wydawnictwo PJWSTK (2006).  Cichy M., Nomańczuk J., Szpakowicz S.: Zbiór zadań z propedeutyki informatyki, PWN 1996. oraz:  Wykłady z ASD Pawła Rembelskiego z PJWSTK  Aho, A., V., Hopcroft, J.,E., Ullman, J., D.: Algorytmy i struktury danych, Helion (2003).  Banachowski, L., Diks, K., Rytter, W.: Algorytmy i struktury danych, WNT (1996).  Cormen, T., H., Leiserson, C. E, Rivest, R., L., Stein, C.: Wprowadzenie do algorytmów, WNT (2012). Algorytmy i struktury danych – Jan G. Bazan 3  Algorytm i algorytmika  Algorytm to opis metody rozwiązania danego problemu w skończonej liczbie kroków zwanych operacjami elementarnymi. » Przez operacje elementarną rozumiemy taką operacje, która z naszego punktu widzenia stanowi całość i jest wykonana w skończonym i akceptowalnym dla nas czasie – Np. przypisanie wartości do zmiennej, porównanie dwóch wartości, wczytanie danych z wejścia lub wypisanie danych na wyjściu.  Własnościami algorytmów, ich projektowaniem i analizą zajmuje się dział informatyki zwany algorytmiką.  Określenie algorytm wywodzi się od nazwiska matematyka perskiego Muhammed'a ibn Musa Alchwarizmi (przełom VIII i IX wieku n.e.). Algorytmy i struktury danych – Jan G. Bazan 4 Przykład algorytmu Algorytmy i struktury danych – Jan G. Bazan 5  Patenty na algorytmy  W niektórych krajach, jak USA, algorytmy mogą zostać opatentowane, jeżeli zostaną zaimplementowane w jakimś praktycznym celu. » Niektórzy twierdzą, że patentowanie algorytmów spowalnia rozwój informatyki, bo jeden producent może uzyskać monopol, np. na pisanie oprogramowania tworzącego pewne typy plików (np. GIF).  Wiele koncernów komputerowych prowadzi między sobą spory prawne dotyczące praw własności do niektórych patentów.  Argumentem za patentowaniem algorytmów jest tzw. prawo własności intelektualnej (jaką objęty jest np. utwór muzyczny, będący wytworem intelektu i pracy muzyka) zakładające, że program jest intelektualną własnością twórcy. Algorytmy i struktury danych – Jan G. Bazan 6  Oczekiwane cechy algorytmów  Poprawność (algorytm daje dobre wyniki, odzwierciedlające rzeczywistość)  Jednoznaczność (brak rozbieżności wyników przy takich samych danych, jednoznaczne opisanie każdego kroku)  Skończoność (wykonuje się w skończonej ilości kroków)  Sprawność (czasowa - szybkość działania i pamięciowa – mała "zasobożerność")  Prostota wykonania (operacje powinny być jak najprostsze) Algorytmy i struktury danych – Jan G. Bazan 7  Cel przedmiotu w pierwszym semestrze jego trwania  Nauka projektowania prostych algorytmów  Nauka analizy algorytmów w zakresie ich złożoności (efektywności) i poprawności.  Analiza algorytmów zarówno bez rekurencji, jak i rekurencyjnych. Algorytmy i struktury danych – Jan G. Bazan 8 Algorytm i zagadnienia towarzyszące Algorytmy i struktury danych – Jan G. Bazan 9  Problemy nierozsztrzygalne  Powiemy, że problem decyzyjny jest rozstrzygalny, jeśli istnieje algorytm, który dla dowolnych danych po skończonej liczbie kroków daje rozwiązanie problemu. W przeciwnym razie, tzn. jeśli taki algorytm nie istnieje, mówimy, że problem jest nierozstrzygalny. Algorytmy i struktury danych – Jan G. Bazan 10  Problem domina - nie jest rozsztrzygalny Małpia układanka  Udowodniono, że nie ma i nigdy nie będzie w przyszłości, algorytmu, który po skończonej liczbie kroków odpowiadałby, że pokrycie danej powierzchni jest lub, że pokrycie nie jest możliwe.  Z tego bierze się trudność tzw. "małpiej układanki" (por. D. Harel, Rzecz o istocie informatyki, WNT 1992) Algorytmy i struktury danych – Jan G. Bazan 11  Sposoby zapisu algorytmów  Opis słowny - polega na logicznym i zrozumiałym dla odbiorcy przedstawieniu kolejnych czynności (akcji), jakie należy wykonać aby osiągnąć zamierzony efekt. Przykładami takiego opisu algorytmu mogą być: przepis kulinarny, recepta wykonania leku, metoda rozwiązania zadania.  Schemat blokowy - jest jedną z najpopularniejszych form przedstawiania algorytmu. Wykorzystuje się w nim symbole zwane bloczkami.  Pseudokod - umowny język programowania, który raczej nie ma translatora (tylko do analiz teoretycznych).  Język programowania to sformalizowany język służący do zapisu algorytmów, który został sztucznie stworzony drogą przyjęcia pewnych aksjomatów i definicji (ustalony alfabet, słownik, ścisłe reguły składniowe i znaczeniowe). Przykłady: C, C++, Pascal, Java, C# Algorytmy i struktury danych – Jan G. Bazan 12  Aspekty różnych metodologii tworzenia algorytmów  Proceduralność – algorytm dzielimy na szereg podstawowych procedur, wiele algorytmów współdzieli wspólne biblioteki standardowych procedur, z których są one wywoływane w razie potrzeby  Praca sekwencyjna – wykonywanie kolejnych procedur algorytmu, według kolejności ich wywołań, na raz pracuje tylko jedna procedura  Praca wielowątkowa – procedury wykonywane są sekwencyjnie, lecz kolejność ich wykonania jest trudna do przewidzenia dla programisty  Praca równoległa i współbieżna – wiele procedur wykonywanych jest w tym samym czasie, które mogą wymieniać się danymi i pośrednimi wynikami  Rekurencja – procedura lub funkcja wywołuje sama siebie, aż do uzyskania wyniku lub błędu  Obiektowość – procedury i dane łączymy w pewne klasy reprezentujące najważniejsze elementy algorytmu oraz stan wewnętrzny wykonującego je urządzenia  Algorytm probabilistyczny – algorytm działa poprawnie z bardzo wysokim prawdopodobieństwem, ale wynik nie jest pewny Algorytmy i struktury danych – Jan G. Bazan 13  Podstawy pseudokodu  Jest to pseudokod z książki:  Dańko, A, Truong Lan Le, Mirkowska, G., Rembelski, P., Smyk, A., Sydow, M.: Algorytmy i struktury danych – zadania, Wydawnictwo PJWSTK (2006). Algorytmy i struktury danych – Jan G. Bazan 14 Elementy składni pseudokodu Algorytmy i struktury danych – Jan G. Bazan 15  Operatory i relacje  Operatory arytmetyczne: + (dodawanie), - (odejmowanie), * (mnożenie), / (dzielenie), div (dzielenie całkowite, bez reszty), mod (dzielenie modulo, reszta z dzielenia)  Operatory logiczne: NOT (negacja), AND (koniunkcja), OR (alternatywa), XOR (alternatywa wykluczająca),  (implikacja)  (równoważność)  Relacje: = (równe), < (mniejsze), > (większe), = (większe bądź równe)  Dla stringów – porządek leksykograficzny Algorytmy i struktury danych – Jan G. Bazan 16  Typy podstawowe  int – typ liczb całkowitych  real - typ liczb rzeczywistych  char – typ znakowy  bool – typ logiczny, zmienne tego typu przyjmują wartości ze zbioru {TRUE, FALSE} lub {true, false}  string – typ łańcuchowy Algorytmy i struktury danych – Jan G. Bazan 17  Deklaracja zmiennych  ; lub  :=  Przykłady: int i; int i,j; real pi:=3.14; int i:=0; bool p,q:=true; string t1,t2:=‘Ala’; Dostęp do elementów typu string: t1:=‘A’; Algorytmy i struktury danych – Jan G. Bazan 18  Deklaracja zmiennych tablicowych  [, ,..., ]  Poszczególne indeksy przebiegają wartości od 1 do rozmiaru na danym indeksie  Wartość początkowa elementów w tablicy jest NIEOKREŚLONA  Przykład: int X; real N; real K[10,10] Dostęp za pomocą operatora []: X – dostęp do elementu numer 3, K[3,5] – dostęp do elementu w wierszu numer 3 i w kolumnie numer 5, Algorytmy i struktury danych – Jan G. Bazan 19  Blok instrukcji  Blok instrukcji to ciąg instrukcji rozdzielonych średnikiem. ; ; ;  Blok może być pusty  Przykład: p:=NOT(q); M[i]:=3; q:=false; Algorytmy i struktury danych – Jan G. Bazan 20  Instrukcja przypisania  Instrukcja przypisania :=;  Do zmiennej po lewej stronie przypisywana jest wartość obliczona po prawej stronie znaku :=  Przykład: eps:=15.125+0.3*45; p:=(eps>0); Algorytmy i struktury danych – Jan G. Bazan 21  Instrukcja warunkowa  Instrukcja warunkowa  Warunek jest if () then wyrażeniem algebraicznym mającym wartość TRUE fi (warunek spełniony) lub FALSE (warunek lub niespełniony) if () then  Wykonanie po słowie then jest else realizowane gdy warunek jest spełniony fi  po słowie else jest realizowany, gdy warunek nie jest spełniony Algorytmy i struktury danych – Jan G. Bazan 22 Przykłady instrukcji warunkowych if (x=0) then if (x=0) then y:=y+1; y:=y+1; x:=x+2; x:=x+2; else fi y:=y-1; x:=x-2 fi Algorytmy i struktury danych – Jan G. Bazan 23  Instrukcja pętli while  Instrukcja while: while () do od Przykład: int i:=1; int s:=0; while (i