Ćwiczenie II

 

1. Pojęcia

1) Rozwiązanie problemu algorytmicznego

2) Sposoby prezentacji algorytmów

3) Metody sortowania

 

2. Wiadomości

2.1 Składowe rozwiązania problemu

 

Całościowe rozwiązanie problemu:

 

Czynności służące do rozwiązania zadania:

 

Składowe algorytmu:

 

Przykłady algorytmów:

·        Algorytm Euklidesa

·        Algorytmy sortowania

·        Algorytmy kompresji

·        Algorytmy sztucznej inteligencji

·        Algorytmy przeszukiwania drzew: min-max i alpha-beta

 

2.2 Sposoby prezentacji algorytmów

 

 

Algorytmy powinny być tak przedstawiane, aby było możliwe ich jednoznaczne odczytanie i zastosowanie. Można prezentować je poprzez:

 

            Zapis w postaci opisu słownego

Zapis w postaci ciągu kroków ( języka potocznego)

Zapis w postaci graficznej - schematy blokowe

Zapis w języku symbolicznym

Zapis w języku programowania

Algorytm wyrażony w jakimś języku programowania nazywa się programem.

 

Metody prezentowania algorytmów:

 

Metody graficzne (wykreślne) - oparte na symbolach graficznych:

-          tablice decyzyjne;

-          schematy blokowe;

-          schematy czynnościowe (w tym obiegu dokumentów);

-          schematy przetwarzania (systemów przebiegu);

-          technika grafów;

-          tablice krzyżowe;

-          matryce sprzężeń.

 

 

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,

 

Języki formalne

 

            Najczęściej używany w praktyce sposób zapisu algorytmu. Językiem formalnym może być dowolny z języków programowania lub specjalnie stworzona w tym celu notacja. Zapewnia ścisłość zapisu. Język taki zwykle nazywamy pseudokodem.

 

Funkcje rekurencyjne

            Sposób używany wszędzie tam, gdzie łatwo można przedstawić rozwiązanie problemu za pomocą rekurencji.

 

Tablice decyzyjne

            Tablice decyzyjne służą przede wszystkim do graficznej, bardzo przejrzystej prezentacji decyzji, jaką należy podjąć w zaistniałych warunkach. Abstrahują one od pozostałych elementów procesu decyzyjnego (nie określają sposobu ani adresata decyzji, procesów wprowadzania i wyprowadzania danych). Podstawą ich budowy są związki przyczynowo-skutkowe (jeżeli A to B).

 

2.3 Rodzaje algorytmów

 

Kompresja - ogólnie działanie mające na celu zmniejszenie wielkości czegoś (czyli zwiększenia gęstości). Np. wody (fizyka). Działaniem przeciwnym do kompresji jest dekompresja. W informatyce chodzi o działania mające na celu zmniejszenie objętości informacyjnej danych, czyli wyrażenie zestawu danych za pomocą mniejszej ilości bitów.

 

Sztuczna Inteligencja (ang. Artificial Intelligence) (AI) to technologia i kierunek badań informatycznych, którego zadaniem jest "Konstruowanie maszyn, o których działaniu dałoby się powiedzieć, że są podobne do ludzkich przejawów inteligencji", Istnieją dwa różne podejścia do pracy nad AI. Pierwsze, to tworzenie całościowych modeli matematycznych analizowanych problemów i implementowanie ich w formie programów komputerowych mających realizować konkretne cele. Drugie to próby tworzenia struktur i programów "samouczących się", takich jak modele [sieci neuronowych]? oraz opracowywania procedur rozwiązywania problemów poprzez "uczenie" takich programów a następnie uzyskiwanie od nich odpowiedzi na "pytania".

 

Algorytm min-max to najprostszy algorytm przeszukiwania drzew mający zastosowanie w komputerowych nielosowych algorytmach gry w dwie osoby, np. szachów.  Wybieramy ten ruch który po ruchu przeciwnika ma "największą najmniejszą" wartość (stąd nazwa). Czyli dla każdego ruchu symulujemy wszystkie możliwe ruchy przeciwnika i za wartość danego naszego ruchu uznajemy wartość najlepszego z punktu przeciwnika ruchu który może on wykonać jeśli my wykonamy dany ruch (część min). Potem wybieramy ruch o najwyższej wartości (część max).

 

Wartość sytuacji można szacować rekurencyjnie algorytmem min-max, jednak po kilku poziomach konieczne jest użycie jakiejś innej funkcji, np. przyjmującej 1 dla wygranej, 0 dla przegranej i inną wartość dla pozostałych sytuacji.

 

Algorytm alpha-beta to zoptymalizowana postać algorytmu min-max. Podczas przeszukiwania zachowane są dwie wartości: α - najlepszy jak na razie nasz ruch i β - najlepszy jak na razie dla przeciwnika ruch w przypadku danego naszego ruchu. Przeszukiwanie ruchów przeciwnika możemy zakończyć kiedy β spadnie poniżej α, czyli w przypadku wykonania przez nas danego ruchu przeciwnik potrafi wykonać taki ruch, że nasz wynik będzie niższy niż dla jakiegoś innego naszego ruchu.

 

2.4 Algorytmy sortowania

 

Algorytmy sortowania

W życiu codziennym często spotykamy się z faktem porządkowania np., aby łatwiej było znaleźć hasło w słowniku są one uporządkowane wg określonych zasad.

 

            Sortowanie - proces ustawienia zbioru obiektów w określonym porządku

 

Metody sortowania:

  1. przez zamianę (sortowanie bąbelkowe)
  2. przez wybieranie
  3. przez wstawianie

 

 

Ad.1 Jedną z popularnych metod sortowania jest sortowanie przez prostą zamianę (sortowanie bąbelkowe). W metodzie tej porównujemy sąsiednie elementy. W celu uporządkowania elementów od najmniejszego do największego, jeśli drugi element jest mniejszy od poprzedniego, to zamieniamy go miejscami. Następnie element, który stał się drugim, porównujemy z trzecim i przestawiamy, jeśli jest mniejszy itd.

Przykład:

    7 6 1 9 5    - porównujemy 7 i 6  ( przestawiamy, bo 6 < 7) 

    6 7 1 9 5    - porównujemy 7 i 1  ( przestawiamy, bo 1 < 7)  

    6 1 7 9 5    - porównujemy 7 i 9 ( nie przestawiamy, bo 10 > 7) 

    6 1 7 9 5    - porównujemy 9 i 5 ( przestawiamy, bo 5 < 10)  

    6 1 7 5 9         - 9 na właściwym miejscu

     ….

Aż do uzyskania odpowiedniego porządku

 

Ad.2 Polega na wyszukaniu najmniejszej liczby, przestawieniu jej na początek ciągu elementów (czyli zamienieniu jej z pierwszą liczbą ciągu) i takim samym postępowaniu dalszym z pominięciem pierwszego elementu.

Przykład:

    7 6 1 9 5    - 1 na pierwszą pozycję, 7 w miejsce 1

    1 6 7 9 5    - 5 na drugą pozycję, 6 w miejsce 5

    1 5 7 9 6    - 6 na trzecią pozycję, 7 w miejsce 6

    1 5 6 9 7    - 7 na czwartą pozycję, 9 w miejsce 7

    1 5 6 7 9    - 9 na właściwym miejscu (piątym)  

 

Ad.3 Sortowanie przez wstawianie

Metoda porządkowania przez wybór polega na wstawianiu elementu we właściwe miejsce, jest ona powszechnie stosowana przez osoby grające w karty.

 

    7| 6  1  9  5 

    6  7| 1  9  5 

    1  6  7| 9  5 

    1  6  7  9| 5 

    1  6  7  5  9|

 

Na schemacie kreska oddziela posortowaną lewą część liczb od nieposortowanej prawej części. Jeśli pragniemy ustawić liczby w kolejności od najmniejszego do największego, to bierzemy element drugi i jeśli jest on mniejszy od pierwszego to wstawiamy przed nim. Następnie bierzemy element trzeci i wstawiamy również w odpowiednie miejsce, a więc jeśli jest mniejszy od pierwszego to przed pierwszy, jeśli mniejszy od drugiego to przed drugi.

 

--------------------------------------------------------------------------------

Ćwiczenie 1

--------------------------------------------------------------------------------

 

Opracuj algorytm telefonicznego zawiadomiania. Numer telefonu : 616-22-22.

 

Oto jak wygląda algorytm:

-          Podnieś słuchawkę.

-          Wybierz cyfrę 6.

-          Wybierz cyfrę 1.

-          Wybierz cyfrę 6.

-          Wybierz cyfrę 2.

-          Wybierz cyfrę 2.

-          Wybierz cyfrę 2.

-          Wybierz cyfrę 2.

-          Przekaż informacje.

-          Odłóż słuchawkę.

 

Algorytmy liniowe mają opisy składające się z kroków, które nie zależą od żadnych warunków i są wykonywane w zapisanej kolejności. Istnieją jednak sytuacje, w których dalsze postępowanie w algorytmie zależy od spełnienia, bądź nie, określonych warunków. Czasami musimy powtórzyć pewne kroki algorytmu kilka razy.

 

--------------------------------------------------------------------------------

Ćwiczenie 2

--------------------------------------------------------------------------------

 

Algorytm Euklidesa to algorytm znajdowania największego wspólnego dzielnika (NWD) dwóch różnych liczb naturalnych dodatnich. Nie wymaga rozkładania liczb na czynniki pierwsze. Algorytm ten znajduje się w Elementach Euklidesa.

 

Algorytm

            dane są dwie liczby naturalne dodatnie a i b

            oblicz c jako resztę z dzielenia a przez b

            zastąp a przez b, zaś b przez c

            jeżeli c = 0, to szukane NWD = a, w przeciwnym wypadku przejdź do 2

 

 

 

 

 

Przykład 1

NWD liczb 1001 i 42 wynosi 7, a obliczenia przebiegają następująco:

 

a          b          c

--------------------------------------------------------------------------------

 

1001    42        35

42        35         7

35          7         0

7            0         0

 

 

Zapis oryginalny algorytmu Euklidesa:

 

def gcd(a,b):
    while a != b:
        if a > b:
            a -= b
        else:
            b -= a
    return a

 

3 Zadania i ćwiczenia

 

Ćwiczenie 1

Zapisać w postaci poszczególnych kroków program pobierający od użytkownika liczbę całkowitą i wypisujący jako wynik wartość silni tej liczby.

 

 

Ćwiczenie 2

Dany jest ciąg liczb o nieznanej długości. Ostatnia liczba w ciągu równa się zero. Oblicz sumę elementów tego ciągu.

 

 

Ćwiczenie 3

Oblicz sumę n - kolejnych liczb naturalnych. Pierwsza z liczb wprowadzona z klawiatury i równa się b.

 

 

Ćwiczenie 4

Dany jest ciąg n-elementowy. Elementy tego ciągu są różne. Wskaż największy element ciągu.

 

Ćwiczenie 5

Dany jest ciąg n-elementowy. Elementy tego ciągu są różne. Wskaż największy i najmniejszy element ciągu.

 

 

Ćwiczenie 6

Dany jest ciąg n-elementowy. Elementy tego ciągu są różne. Wskaż różnicę między największym i najmniejszym elementem ciągu.

 

 

Ćwiczenie 7

Dany jest ciąg liczb o nieznanej długości. Ostatnia liczba w ciągu równa się zero. Oblicz średnią arytmetyczną elementów ciągu.

 

 

Ćwiczenie 8

Dany jest ciąg liczb o nieznanej długości. Ostatnia liczba w ciągu równa się zero. Oblicz średnią geometryczna elementów ciągu.

 

 

Ćwiczenie 9

Dany jest ciąg liczb o nieznanej długości. Ostatnia liczba w ciągu równa się zero. Oblicz sumę elementów ciągu, które są większe od 10.