Ćwiczenia V

1. Pojęcia

Algorytmy rekurencyjne

Podstawowe pojęcia algebry Boole’a

Tablice dwu i wielowymiarowe

2. Wiadomości

2.1 Algorytmy rekurencyjne

ITERACJA (działanie w pętli) to technika algorytmiczna polegająca na wykonaniu tej samej instrukcji dla n zmiennych (np. liczb, wartości logicznych etc.) Iteracja oszczędza czas programisty, który ten musiałby spędzić wpisując instrukcję n razy, zależnie od liczby zmiennych. Liczba powtórzeń w iteracji jest z góry określona lub zależy od spełnienia określonego warunku.

- for, while

O rekurencji mówimy wówczas, gdy definicja jakiegoś pojęcia odwołuje się do niego samego. Z logicznego punktu widzenia, poprawna definicja pojęcia nie może odwoływać się do niego samego, a tylko do pojęć, uznanych za nie wymagające definicji (tzw. pojęć pierwotnych), lub pojęć zdefiniowanych wcześniej. W pewnych sytuacjach jednak, po nałożeniu odpowiednich ograniczeń, możliwa jest definicja pojęcia na bazie jego samego. Jak mogą wyglądać takie ograniczenia, przykładami mogą być poniższe zagadnienia.

Liczba, zwana silnią (z argumentu, będącego liczbą naturalną) wyznaczona może być w następujący sposób:

n!=1 *2 *3 *...*n , gdzie n większe równe 1

Ponieważ silnia z liczby n jest równa ilości permutacji zbioru n-elementowego (liczbie sposobów, w jaki można ustawią elementy zbioru „w szereg“, w różnej kolejności), wygodnie jest rozszerzyć tę definicję przyjmując, że silnia z zera wynosi 1 (zbiór pusty daje tylko jedną możliwość ustawienia jego „elementów“). Po takim rozszerzeniu możemy funkcję silnia wyrazić również następująco:

n!= 1 , dla n=0, 1

n! = n * (n−1)! , dla n<>0

Rekurencja:

- pośrednia

- bezpośrednia

Wady algorytmów rekurencyjnych:

1) Zajętość pamięci

2) Obliczenia wykonywane są wielokrotnie

Zalety algorytmów rekurencyjnych:

1) Przejrzysty sposób zapisu

2) Lepsza czytelność kodu dla danych rekurencyjnych

2.2 Pojęcie algebry Boole’a

2.2.1 Pojęcie algebry

Strukturą algebraiczną nazywamy dowolny niepusty zbiór wraz z pewną liczbą działań na tym zbiorze. Strukturę taką zapisujemy w formie układu $(A; f_1,f_2,\dots)$ , gdzie $f_1,f_2,\dots$ są działaniami na zbiorze , zwanym dziedziną (uniwersum) danej struktury. Gdy wiadomo, jakie działania są określone w danej strukturze $(A; f_1,f_2,\dots)$ , dla jej oznaczenia używamy po prostu symbolu .

Przykłady struktur algebraicznych to zbiór liczb rzeczywistych ${\mathbb{R}}$ z dodawaniem i mnożeniem. Strukturę $({\mathbb{R}},+,\cdot)$ nazywamy ciałem liczb rzeczywistych. Podobnie strukturę $({\mathbb{C}},+,\cdot)$ nazywamy ciałem liczb zespolonych. Różne struktury algebraiczne są podstawowym obiektem badań algebry. Algebra liniowa zajmuje się badaniem struktur zwanych przestrzeniami liniowymi.

2.2.2 Pojecie zbioru częściowo uporządkowanego

Relacja wyznacza częściowy porządek, jeśli dla dowolnych elementów a, b, i c zachodzi:

(i) a R a (zwrotność)

(ii) a R b and b R a implikuje a = b (antysymetryczność)

(iii) a R b and b R c implikuje a _ c (przechodniość).

2.2.3 Pojecie kraty

1) Pierwsza definicja

Niepusty zbiór L wraz z dwoma binarnymi operacjami Ú i Ù na zbiorze L jest nazywany kratą jeżeli spełnia następujące warunki::

L1: x Ú y ≈ y Ú x

x Ù y ≈ y Ù x

L2: x Ú (y Ú z) ≈ (x Ú y) Ú z

x Ù (y Ù z) ≈ (x Ù y) Ù z

L3:

x Ù x ≈ x

x Ú x ≈ x

L4:

x ≈ x Ú (x Ù y)

x ≈ x Ù (x Ú y)

2) Druga definicja

Zbiór częściowo uporządkowany L nazywamy kratą jeśli dla dowolnych elementów a i b istnieją elementy inf{a, b} oraz sup{a, b}.

Kratę L nazywamy rozdzielną jeżeli:

x Ù (y Ú z) = (x Ù y) Ú (x Ù z)

x Ú (y Ù z) = (xÚ y) Ù (x Ú z):

2.2.4 Algebra Boole’a

Algebrą Boole’a nazywamy rozdzielną kratę <A, Ú, Ù, ~, 0, 1) takim, że działanie jednoargumentowe spełnia warunki:

a Ú ~a = 1 oraz a Ù ~a = 0

W algebrze Boole'a obowiązują następujące podstawowe prawa:

1. Prawo przemienności dodawania i mnożenia
a×b = b×a
a+b = b+a

2. Prawo łączności:

1. mnożenia
a×b×c = a(b×c) = (a×b)c

2. dodawania
a+b+c = (a+b)+c = a+(b+c)

3. Prawo rozdzielności

1. mnożenia względem dodawania
a(b+c) = a×b+a×c

2. dodawania względem mnożenia
a+b×c = (a+b)×(a+c)

4. 0 jest elementem neutralnym dla +: a + 0 = a

5. 1 jest elementem neutralnym dla ×: a × 1 = a

a + (~a) = 1

a × (~a) = 0

7. dwa działania ~ się znoszą: ~~x = x

Zależności logiczne zostały ujęte w algebrze Boole'a. W oparciu o zasadę tej algebry możemy tworzyć układy, które będą działać w sensie logicznym identycznie jak układy o większej liczbie elementów. Za pomocą zasad tej algebry dokonujemy minimalizacji układów logicznych. Jedną z reguł algebry Boole'a są prawa Demorgana:

I prawo Demorgana

Zaprzeczenie koniunkcji (iloczynu logicznego) równej jest sumie zaprzeczeń.

II prawo Demorgana

Zaprzeczenie sumy logicznej jest równe iloczynowi logicznemu.

Funkcje dwu zmiennych dla algebry dwuargumentowej

(x,y)	(0,0)	(0,1)	(1,0)	(1,1)	Nazwa funkcji
	0	0	0	0	Stała 0
	0	0	0	1	Iloczyn ( i - AND )
	0	0	1	0	Iloczyn z zakazem dla y
	0	0	1	1	Zmienna x
	0	1	0	0	Iloczyn z zakazem dla x
	0	1	0	1	Zmienna y
	0	1	1	0	Suma modulo 2 (EXOR)
	0	1	1	1	Suma (lub - OR )
	1	0	0	0	Operacja Pierce'a ( NOR )
	1	0	0	1	równoważność
	1	0	1	0	Negacja y (NOT)
	1	0	1	1	Implikacja x przez y
	1	1	0	0	Negacja x (NOT)
	1	1	0	1	Implikacja y przez x
	1	1	1	0	Operacja Sheffera (NAND)
	1	1	1	1	Stała 1

Tab: funkcje binarne dwóch zmiennych

2.3 Tablice dwuwymiarowe – algorytmy obsługi

Przykład tablicy dwuwymiarowej:

Do poszczególnych elementów tablicy uzyskujemy dostęp poprzez podanie nazwy tablicy oraz w nawiasach kwadratowych wartość indeksu ( numer żądanego elementu).
I tak w naszej tablicy o nazwie t zapis t[3,4] oznacza element w trzecim wierszu i czwartej kolumnie, czyli element o wartości =3.
   t [1,1] = 2
   t [1,2] =6
   t [1,3] =11
   t [1,4] =0
   t [2,1] =7

Element t [i, j] dla i równego 2 i j równego 2 wynosi 5.

Ćwiczenie 1
Opracuj algorytm wypełniający tablicę kwadratową k x k.

Ćwiczenie 2
Odszukaj w tablicy m x n element maksymalny. Wypisz jego położenie i wartość.

Ćwiczenie 3
Tablica kwadratowa m x n składa się z zer i jedynek. Podaj algorytm wypisujący ile jest zer i ile jedynek.

Ćwiczenie 4
Zbuduj algorytm sumujący elementy na przekątnej tablicy k x k.

Ćwiczenie 5
Podaj algorytm obliczający sumę i ilość elementów nad przekątną tablicy kwadratowej.

3. Zadania i ćwiczenia

Ćwiczenie 1
Zbuduj algorytm wyznaczania elementu minimalnego tablicy kwadratowej.

Ćwiczenie2
Narysuj schemat blokowy algorytmu wypisującego z tablicy k x k elementy parzyste. Podaj ilość takich elementów.

Ćwiczenie3
Zbuduj algorytm podający ilość i średnią arytmetyczną elementów tablicy m x n podzielnych przez 10.

Ćwiczenie4
Opracuj algorytm wyznaczania elementu minimalnego tablicy kwadratowej.

Ćwiczenie 5

Schemat blokowy programu wypisującego wszystkie liczby pierwsze od 1….n

Ćwiczenie 6

Wypisanie liczb podzielnych przez n z przedziału <x, y>

Ćwiczenie 7

Obliczanie sumy wyrazów szeregu arytmetycznego, geometrycznego

Ćwiczenie 8

Napisać algorytm rekurencyjny obliczania:

- silni

- wyrazu an ciągu Fibonacciego

- wyrazu an ciagu arytmetycznego

- wyrazu an ciągu geometrycznego

Ćwiczenie 9

Rozważyć zbiór <N – {0}, + , *> gdzie x i y = nwd(x,y), zaś x + y = nww(x, y). Sprawdzić, czy taki system jest kratą. Czy jest to krata rozdzielna? Czy jest to algebra Boole’a?

Projekt

Napisać program definiujący trzy tablice 256 bajtów, pobierający wartości do dwu pierwszych tablic, wykonujący operacje dodawania na odpowiednich pozycjach tablicy oraz zapisujący wynik do trzeciej tablicy.