Ćwiczenie IV

 

1. Pojęcia

            Efektywność i koszt algorytmu

            Podstawowe pojęcia algebry Boole’a

            Tablice jedno i dwywymiarowe

 

2. Wiadomości

2.1 Efektywność i koszt algorytmu

 

            Pożądaną cechą dodatkową jest efektywność: algorytm powinien osiągać efekt możliwie niskim kosztem. Koszty eksploatacji są związane z czasem pracy wykonawcy: im bardziej efektywny algorytm, tym mniej czasu zajmie jego wykonanie temu samemu wykonawcy. Na ogół tym więcej czasu musi mu poświęcić projektant i programista.

 

            Przy rozwiązywaniu zadań praktycznych znaczenie ma również koszt opracowania i koszt przyszłej konserwacji algorytmu, mierzony wysiłkiem twórcy wkładanym w jego ulepszanie i rozbudowę. Algorytmy bardziej efektywne są często bardziej skomplikowane (więc trudniejsze w opracowaniu, analizie i implementacji).

 

 

2.2 Algebra Boole’a

 

            Algebra Boole’a posługuje się jedynie dwiema możliwymi cyframi. Przyjęło się zapisywać je jako 0 i 1. Można też wyobrazić je sobie jako dwa przeciwne stany – prawda (ang. true) i fałsz (ang. false), stan wysoki (ang. high – w skrócie H) i niski (ang. low – w skrócie L).

Działania

Na tych dwóch dostępnych liczbach definiuje się kilka podstawowych działań.

Negacja

Jest to działanie jednoargumentowe oznaczane symbolem ~ (tzw. tylda – czyli taki wężyk pisany nieco u góry :) Bywa też oznaczane przez takie coś: Ø lub przez pisany za negowanym wyrażeniem apostrof: ‘. Można by je porównać znanej do zamiany liczby na przeciwną za pomocą poprzedzającego znaku minus -. Tak jak liczba –5 jest przeciwna, do liczby 5, tak ~x oznacza stan przeciwny do stanu oznaczonego przez x. Ponieważ w logice dwuwartościowej wartości są tylko… dwie, nietrudno jest wypisać tabelkę dla tego działania:

  

x

~x

0

1

1

0

 

Tabela 1. Wartości logiczne negacji

 

Jak widać, zanegowanie wartości powoduje jej zamianę na wartość przeciwną, czyli drugą spośród dwóch możliwych.

 

Można jeszcze dodać, że negacja nazywana bywa też przeczeniem, a jej słownym odpowiednikiem jest słowo „nie” (ang. not).

 

Koniunkcja

Jest to działanie dwuargumentowe, które można porównać znanego nam mnożenia. Symbolizuje go taki oto dziwny znaczek przypominający daszek: Ù.

 

Mnożąc jakąkolwiek liczbę przez 0, otrzymujemy 0. Z kolei 1*1 daje w wyniku 1. Identycznie wynika iloczyn wartości Boole’owskich.

  

x

y

x Ù y

0

0

0

0

1

0

1

0

0

1

1

1

 

Tabela 2. Wartości logiczne koniunkcji

 

Koniunkcja bywa też nazywana iloczynem, a odpowiadającym jej słowem jest „i”. Faktycznie możemy zauważyć, że aby działanie dało w wyniku jedynkę, jedynką muszą być obydwa argumenty działania: pierwszy i drugi.

Alternatywa

Skoro jest mnożenie, powinno być też dodawanie. Jego symbol jest przeciwny do symbolu koniunkcji (odwrócony daszek) i wygląda tak: Ú.

 

            Tylko dodawanie dwóch zer daje w wyniku zero. Jeśli choć jednym ze składników jest jedynka, wynikiem dodawania jest liczba większa od zera – 1 albo 2. Ponieważ dwójka w algebrze Boole’a nie występuje zostaje jakby „obcięta” do jedynki. Tabelka będzie więc wyglądała tak:

 

 

x

y

x Ú y

0

0

0

0

1

1

1

0

1

1

1

1

 

Tabela 3. Wartości logiczne alternatywy

 

Słówkiem odpowiadającym alternatywie jest „lub”. Widzimy, że wynikiem działania jest 1, jeśli wartość 1 ma przynajmniej jeden spośród argumentów działania – pierwszy lub drugi. A więc wszystko się zgadza.

 

Różnica symetryczna

Aby sporządzić tabelkę, przyda się angielska nazwa tej operacji. Brzmi ona exclusive or (w skrócie xor) – co oznacza „wyłącznie lub”. Aby w wyniku otrzymać 1, jedynką musi być koniecznie tylko pierwszy lub tylko drugi argument tego działania, nie żaden ani nie obydwa.

 

x

y

x Å  y

0

0

0

0

1

1

1

0

1

1

1

0

 

Tabela 4. Wartości logiczne różnicy symetrycznej

 

Dodatkowe działania – teoretycznie może ich być 2*2*2*2  czyli 16

Ekwiwalencja

Ekwiwalencja to inaczej równoważność i odpowiada jej nieco przydługie stwierdzenie o treści: „wtedy i tylko wtedy, gdy”. Daje ono w wyniku jedynkę wtedy i tylko wtedy, gdy obydwa argumenty są takie same. Symbolizuje go taka zwrócona w obydwie strony strzałka: Û. Można więc utożsamiać to działanie z równością.

 

x

y

x Û y

0

0

1

0

1

0

1

0

0

1

1

1

 

Tabela 5. Wartości logiczne ekwiwalencji

 

Implikacja

 

Inna nazwa implikacji to wynikanie, a odpowiadające mu stwierdzenie brzmi: „jeżeli …, to …”. Oznaczane jest strzałką skierowaną w prawo: Þ. Oto jego tabelka:

 

x

y

x Þ y

0

0

1

0

1

1

1

0

0

1

1

1

 

Tabela 6. Wartości logiczne implikacji

 

Aksjomaty

Wymienione powyżej działania spełniają następujące zależności

Przemienność

a Ú b = b Ú a

 Dodawanie też jest przemienne – jak w matematyce.

a Ù b = b Ù a

Mnożenie też jest przemienne.

Łączność

(a Ú b) Ú c = a Ú (b Ú c)

Dodawanie jest łączne – jak w matematyce.

(a Ù b) Ù c = a Ù (b Ù c)

Mnożenie też jest łączne.

Rozdzielność

a Ù (b Ú c) = (a Ù b) Ú (a Ù c)

Mnożenie jest rozdzielne względem dodawania.

a Ú (b Ù c) = (a Ú b) Ù (a Ú c)

Dodawanie też jest rozdzielne względem mnożenia

Identyczność

a Ú 0 = a

a Ú 1 = 1

a Ù 0 = 0

a Ù 1 = a

To wynika bezpośrednio z tabelek.

Dopełnienie

a Ú ~a = 1

a Ù ~a = 0

Bo jeden z argumentów zawsze będzie przeciwny do drugiego.

Prawa De Morgana

~(a Ú b) = ~a Ù ~b

~(a Ù b) = ~a Ú ~b

 

 

2.3 Pojęcie tablicy – zastosowania w programowaniu

 

            Tablicą nazywamy złożoną strukturę danych, która zawiera zbiór elementów tego samego typu. Wyróżniamy tablice jednowymiarowe oraz tablice wielowymiarowe.

 

 

 

 

 

            Do poszczególnych elementów tablicy uzyskujemy dostęp poprzez podanie nazwy tablicy oraz w nawiasach kwadratowych wartość indeksu ( numer żądanego elementu). W tablicy o nazwie t:

 

   t [1] = 5

   t [2] =11

   t [3] =8

   t [4] =3

   t [5] =2

 

 

 

 

 

Element t [i] dla i równego 4 wynosi 3, dla i równego 2 wynosi 11.

 

2.4 Schematy blokowe – ćwiczenia

 

Schemat blokowy – określanie liczby pierwiastków równania kwadratowego

 

 

 

Ćwiczenie 2
Opracuj algorytm wypisujący elementy tablicy k- elementowej.

Ćwiczenie 3
Zbuduj algorytm sumujący elementy tablicy n- elementowej.

Ćwiczenie 4
Zbuduj algorytm liczący średnią arytmetyczną elementów tablicy.

Ćwiczenie 5
Do tablicy wczytano k-elementów. Wydrukuj położenie i wartość elementu najmniejszego (zakładamy, że elementy są różne).

Ćwiczenie 6
Wczytaj elementy do tablicy k- elementowej, a następnie wydrukuj je w odwrotnej kolejności.

Ćwiczenie 7
Z tablicy zawierającej k-elementów wybierz elementy podzielne przez 3. Oblicz ich ilość, sumę i średnią.

Ćwiczenie 8
Wczytaj elementy do tablicy k- elementowej. Wydrukuj tę tablicę. Zamień pierwszy z ostatnim i wydrukuj tablicę po modyfikacji.

 

 

3. Zadania i ćwiczenia

 

Ćwiczenie 1

Napisać schemat blokowy programu pobierającego od użytkownika ciąg elementów an, oraz następnie zapisujący elementy tego ciągu w tablicy bn w odwrotnej kolejności

 

                  Ćwiczenie 2

Napisać schemat blokowy programu pobierającego od użytkownika ciąg elementów an, oraz następnie zapisujący elementy tego ciągu w tablicy an w odwrotnej kolejności

 

                  Ćwiczenie 3

                  Napisać schemat blokowy programu sprawdzającego, czy dana liczba (wprowadzona przez użytkownika) jest liczbą pierwszą

                 

                  Ćwiczenie 4

Schemat blokowy programu wypisującego wszystkie liczby pierwsze w ciągu od 1 do n

 

                  Ćwiczenie 5 

                  Napisać program wypisujący współczynniki trójkąta Pascala dla zadanej liczby n.

 

                  Ćwiczenie 6

                  Zdefiniować wszystkie możliwe działania w dwuelementowej algebrze Boole’a.

 

 

Projekt

Zaprojektować i zaimplementować program sortujący elementy określonego ciągu poznanymi metodami sortowania.

 

-     sortowanie przez porównanie

-     sortowanie przez selekcję / wybór

-     sortowanie przez wstawianie