Efektywność i koszt algorytmu
Podstawowe pojęcia algebry Boole’a
Tablice jedno i dwywymiarowe
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).
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).
Na tych dwóch dostępnych liczbach definiuje się kilka podstawowych działań.
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).
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.
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.
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 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
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
Wymienione powyżej działania spełniają następujące zależności
a Ú b = b Ú a
Dodawanie też jest przemienne – jak w matematyce.
a Ù b = b Ù a
Mnożenie też jest przemienne.
(a Ú b) Ú c = a Ú (b Ú c)
Dodawanie jest łączne – jak w matematyce.
(a Ù b) Ù c = a Ù (b Ù c)
Mnożenie też jest łączne.
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
a Ú 0 = a
a Ú 1 = 1
a Ù 0 = 0
a Ù 1 = a
To wynika bezpośrednio z tabelek.
a Ú ~a = 1
a Ù ~a = 0
Bo jeden z argumentów zawsze będzie przeciwny do drugiego.
~(a Ú b) = ~a Ù ~b
~(a Ù b) = ~a Ú ~b
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.
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.
Ć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