DZIELENIE


Dzielenie binarne jest najbardziej skomplikowaną operacją arytmetyczną z dotychczas opisywanych. Wymyślono wiele algorytmów efektywnego dzielenia, ale dla potrzeb tego opracowania wystarczy znany wam algorytm szkolny, który polega na cyklicznym odejmowaniu odpowiednio przesuniętego dzielnika od dzielnej. W systemie dwójkowym jest to szczególnie proste, ponieważ dzielnika nie musimy mnożyć.

PRZYKŁAD

Podzielimy liczbę 1101₍₂₎ przez 10₍₂₎ (13₍₁₀₎ : 2₍₁₀₎).

1. Przesuwamy w lewo dzielnik, aż zrówna się jego najstarszy, niezerowy bit z najstarszym, niezerowym bitem dzielnej. Nad dzielną rysujemy kreseczkę:

1101	- dzielna
10	- przesunięty dzielnik

1. Porównujemy dzielną z dzielnikiem. Jeśli dzielna jest większa lub równa dzielnikowi, to odejmujemy od niej dzielnik. Ponad kreską na pozycji ostatniej cyfry dzielnika piszemy 1. Jeśli dzielna jest mniejsza od dzielnika, to nie wykonujemy odejmowania, lecz przesuwamy dzielnik o 1 pozycję w prawo i powtarzamy opisane operacje. Jeśli w ogóle dzielnika nie da się odjąć od dzielnej (np. przy dzieleniu 7 przez 9), to wynik dzielenia wynosi 0, a dzielna ma w takim przypadku wartość reszty z dzielenia. W naszym przykładzie odejmowanie to jest możliwe, zatem:

		1			- pierwsza cyfra wyniku dzielenia
	1	1	0	1	- dzielna
-	1	0			- przesunięty dzielnik
	0	1	0	1	- wynik odejmowania dzielnika od dzielnej

1. Dzielnik przesuwamy o jeden bit w prawo i próbujemy tego samego z otrzymaną różnicą. Jeśli odejmowanie jest możliwe, to nad kreską w następnej kolumnie dopisujemy 1, odejmujemy dzielnik od różnicy, przesuwamy go o 1 bit w prawo i kontynuujemy. Jeśli odejmowanie nie jest możliwe, to dopisujemy nad kreską 0, przesuwamy dzielnik o 1 bit w prawo i kontynuujemy.

		1	1	0	- wynik dzielenia
	1	1	0	1	- dzielna
-	1	0			- przesunięty dzielnik
	0	1	0	1	- dzielna po pierwszym odejmowaniu przesuniętego dzielnika
-		1	0		- przesunięty dzielnik
	0	0	0	1	- dzielna po drugim odejmowaniu przesuniętego dzielnika
-			1	0	- dzielnik na swoim miejscu, odejmowanie niemożliwe
	0	0	0	1	- reszta z dzielenia

1. Operacje te wykonujemy dotąd, aż dzielnik osiągnie swoją pierwotną wartość. Pozostała dzielna jest resztą z dzielenia. Oczywiście w tym momencie możemy dalej kontynuować odejmowanie wg opisanych zasad otrzymując kolejne cyfry ułamkowe - identycznie postępujemy w systemie dziesiętnym. Jednakże pozostawimy ten problem do rozwiązania bardziej ambitnym czytelnikom.

W naszym przykładzie otrzymaliśmy wynik dzielenia równy:

1101₍₂₎ : 10₍₂₎ = 110₍₂₎ i resztę 1₍₂₎ (6₍₁₀₎ i 1₍₁₀₎)

Jest to wynik poprawny, gdyż 2 mieści się w 13 sześć razy i pozostaje reszta 1.

Dla wprawki podzielmy liczbę 110101101₍₂₎ przez 111₍₂₎ (429₍₁₀₎ przez 7₍₁₀₎):
  0111101 - wynik dzielenia
110101101 : 111
111       - nie da się odjąć, nad kreską 0
110101101
 111      - da się odjąć, nad kreską 1
 11001101
  111     - da się odjąć, nad kreską 1
  1011101
   111    - da się odjąć, nad kreską 1
   100101
    111   - da się odjąć, nad kreską 1
     1001
     111  - nie da się odjąć, nad kreską 0
     1001
      111 - da się odjąć, nad kreską 1, koniec
       10 - reszta z dzielenia

110101101₍₂₎ : 111₍₂₎ = 111101₍₂₎ i reszta 10₍₂₎ (429₍₁₀₎ : 7₍₁₀₎ = 61₍₁₀₎ i reszta 2₍₁₀₎).

MNOŻENIE

Naukę mnożenia binarnego rozpoczynamy od tabliczki mnożenia. Bez paniki - jest ona równie prosta jak podane powyżej tabliczki dodawania i odejmowania.

0 x 0 =	0
0 x 1 =	0
1 x 0 =	0
1 x 1 =	1

Tabliczka mnożenia binarnego (podobnie jak w systemie dziesiętnym) posłuży do tworzenia iloczynów częściowych cyfr mnożnej przez cyfry mnożnika. Iloczyny te następnie dodajemy wg opisanych zasad i otrzymujemy wynik mnożenia.

PRZYKŁAD

Pomnożyć binarnie liczbę 1101₍₂₎ przez 1011₍₂₎.

1. Obie liczby umieszczamy jedna pod drugą tak, aby ich cyfry znalazły się w kolumnach o tych samych wagach:

	1101
x	1011

1. Każdą cyfrę mnożnej mnożymy przez poszczególne cyfry mnożnika zapisując wyniki mnożeń w odpowiednich kolumnach - tak samo postępujemy w systemie dziesiętnym, a tutaj jest nawet prościej, gdyż wynik mnożenia cyfry przez cyfrę jest zawsze jednocyfrowy:

				1	1	0	1
x				1	0	1	1
				1	1	0	1
			1	1	0	1
		0	0	0	0
	1	1	0	1

Zwróć uwagę, iż wynikiem mnożenia mnożnej przez cyfrę mnożnika jest powtórzenie mnożnej z przesunięciem o pozycję cyfry (cyfra mnożnika 1) lub same zera (cyfra mnożnika 0). Spostrzeżenie to bardzo ułatwia konstrukcję układów mnożących.

1. Puste kolumny uzupełniamy zerami i dodajemy do siebie wszystkie cyfry w kolumnach. Uważaj na przeniesienia.

				1	1	0	1
x				1	0	1	1
	0	0	0	1	1	0	1
	0	0	1	1	0	1	0
+	1	1	0	1	0	0	0
1	0	0	0	1	1	1	1

Sprawdź, czy otrzymany wynik jest poprawny. 

ODEJMOWANIE

Przy odejmowaniu korzystamy z tabliczki odejmowania, która w systemie binarnym jest bardzo prosta:

0 - 0 =	0
0 - 1 =	1 i pożyczka do następnej pozycji
1 - 0 =	1
1 - 1 =	0

Odejmując 0 - 1 otrzymujemy wynik 1 i pożyczkę (ang. borrow) do następnej pozycji. Pożyczka oznacza konieczność odjęcia 1 od wyniku odejmowania cyfr w następnej kolumnie. Identycznie postępujemy w systemie dziesiętnym, tyle że tam jest to o wiele bardziej skomplikowane.

Na razie załóżmy, iż od liczb większych odejmujemy mniejsze (w przeciwnym razie musielibyśmy wprowadzić liczby ujemne, a nie chcemy tego robić w tym miejscu).

PRZYKŁAD

Wykonać odejmowanie w systemie binarnym 1101110₍₂₎ - 1111₍₂₎.

1. Obie liczby umieszczamy jedna pod drugą tak, aby ich cyfry znalazły się w kolumnach o tych samych wagach:

	1101110
-	1111

1. Odejmowanie rozpoczynamy od cyfr ostatniej kolumny. Wyniki zapisujemy pod kreską. W tym przykładzie odjęcie ostatnich cyfr 0 - 1 daje wynik 1 oraz pożyczkę do następnej kolumny. Pożyczki zaznaczamy kolorem czerwonym.

						1
	1	1	0	1	1	1	0
-				1	1	1	1
							1

1. Odjęcie cyfr w drugiej od końca kolumnie daje wynik 1 - 1 = 0. Od tego wyniku musimy odjąć pożyczkę 0 - 1 = 1 i pożyczka do następnej kolumny.

					1	1
	1	1	0	1	1	1	0
-				1	1	1	1
						1	1

1. Według tych zasad kontynuujemy odejmowanie cyfr w pozostałych kolumnach. Pamiętaj o pożyczkach! Jeśli w krótszej liczbie zabraknie cyfr, to możemy kolumny wypełnić zerami:

		1	1	1	1	1
	1	1	0	1	1	1	0
-	0	0	0	1	1	1	1
	1	0	1	1	1	1	1

1101110₍₂₎ - 1111₍₂₎ = 1011111₍₂₎  (110₍₁₀₎ - 15₍₁₀₎ = 95₍₁₀₎).

Reprezentacja danych - podstawowe operacje w systemie binarnym 

Zasady arytmetyki w systemie binarnym są identyczne (prawie) jak w dobrze nam znanym systemie dziesiętnym. Zaletą arytmetyki binarnej jest jej prostota, dzięki czemu można ją tanio realizować za pomocą układów elektronicznych.

Poniżej opisujemy zasady wykonywania podstawowych działań arytmetycznych wraz z odpowiednimi przykładami.

DODAWANIE

Do wykonywania dodawania niezbędna jest znajomość tabliczki dodawania, czyli wyników sumowania każdej cyfry z każdą inną. W systemie binarnym mamy tylko dwie cyfry 0 i 1, zatem tabliczka dodawania jest niezwykle prosta i składa się tylko z 4 pozycji:

0 + 0 =	0
0 + 1 =	1
1 + 0 =	1
1 + 1 =	10

PRZYKŁAD

Zsumować liczby binarne 1111001₍₂₎ oraz 10010₍₂₎.

1. Sumowane liczby zapisujemy jedna pod drugą tak, aby w kolejnych kolumnach znalazły się cyfry stojące na pozycjach o tych samych wagach (identycznie postępujemy w systemie dziesiętnym zapisując liczby w słupkach przed sumowaniem):

	1111001
+	10010

1. Sumowanie rozpoczynamy od ostatniej kolumny. Sumujemy cyfry w kolumnie zgodnie z podaną tabelką zapisując wynik pod kreską:

	1111001
+	10010
	1011

1. Jeśli wynik sumowania jest dwucyfrowy (1 + 1 = 10), to pod kreską zapisujemy tylko ostatnią cyfrę 0, a 1 przechodzi do następnej kolumny - dodamy ją do wyniku sumowania cyfr w następnej kolumnie. Jest to tzw. przeniesienie (ang. carry). Przeniesienie zaznaczyliśmy na czerwono:

		1
	1	1	1	1	0	0	1
+			1	0	0	1	0
			0	1	0	1	1

1. Jeśli w krótszej liczbie zabrakło cyfr, to dopisujemy zera. Pamiętajmy o przeniesieniach.

1	1	1
	1	1	1	1	0	0	1
+	0	0	1	0	0	1	0
	0	0	0	1	0	1	1

1. Dodaliśmy wszystkie cyfry, ale przeniesienie wciąż wynosi 1. Zatem dopisujemy je do otrzymanego wyniku (możemy potraktować pustą kolumnę tak, jakby zawierała cyfry 0 i do wyniku sumowania dodać przeniesienie).

	1	1	1
	0	1	1	1	1	0	0	1
+	0	0	0	1	0	0	1	0
	1	0	0	0	1	0	1	1

1111001₍₂₎ + 10010₍₂₎ = 10001011₍₂₎ (121 + 18 = 139)

Złożoność obliczeniowa

Teoria złożoności obliczeniowej - dział teorii obliczeń, którego głównym celem jest określanie ilości zasobów potrzebnych do rozwiązania problemów obliczeniowych. Rozważanymi zasobami są takie wielkości jak czas, pamięć lub liczba procesorów.

Za twórców tej teorii uważani są Juris Hartmanis i Richard Stearns. Jako przykłady problemów t.z.o. można podać problem spełnialności, problem najkrótszej ścieżki, problemfaktoryzacji oraz wiele innych, o których wiadomo, że są obliczalne. Kwestią obliczalności zajmuje się teoria obliczalności będąca drugą ważną gałęzią teorii obliczeń.

Wyniki, jakie podaje t.z.o., można podzielić na dwie kategorie: pozytywne i negatywne, czyli na takie, które podają, co i jak da się obliczyć, oraz takie, w których dowodzi się, czego nie da się obliczyć, wykorzystując określoną ilość zasobów. Wyniki pozytywne są łatwiejsze do uzyskania i zwykle mają postać algorytmu rozwiązującego dany problem wraz z dowodem poprawności oraz opisem potrzebnych zasobów.

Złożoność algorytmów

Ilość zasobów niezbędnych do wykonania algorytmu można rozumieć jako jego złożoność. W zależności od rozważanego zasobu mówimy o złożoności czasowej czy też pamięciowej. Oczywiście w większości wypadków ilość potrzebnych zasobów będzie się różnić w zależności od danych wejściowych z zakresu danego zagadnienia.

Przykładowo rozpatrzmy rozkład liczb na czynniki pierwsze. Domyślamy się, że (niezależnie od zastosowanego algorytmu) im większa liczba, tym więcej zasobów będzie potrzebnych do jej rozłożenia. Tę cechę podziela większość zagadnień obliczeniowych: im większe rozmiary danych wejściowych, tym więcej zasobów (czasu, procesorów, pamięci) jest koniecznych do wykonania danych obliczeń. Złożoność algorytmu jest więc funkcją rozmiaru danych wejściowych.

Kolejnym problemem jest fakt, iż złożoność zwykle nie zależy wyłącznie od rozmiaru danych, ale może się znacznie różnić dla danych wejściowych o identycznym rozmiarze. Dwoma często stosowanymi sposobami podejścia są: rozpatrywanie przypadków najgorszych (złożoność pesymistyczna) oraz zastosowanie określonego sposobu uśrednienia wszystkich możliwych przypadków (złożoność oczekiwana).

Łatwo można zauważyć, że poprzednie programy wykonują wielokrotnie te same czynności. INSTRUKCJE ITERACYJNE służą do ograniczenia cykli programowych, tj. wielokrotnego wykonywania pewnych sekwencji instrukcji.

W języku Turbo Pascal występują trzy instrukcje iteracyjne.

• instrukcja "dla" FOR,
• instrukcja "dopóki" WHILE,
• instrukcja "powtarzaj" REPEAT.

Instrukcję iteracyjną "dla" FOR stosuje się w programie w przypadku, gdy liczba powtórzeń jest znana w danym miejscu programu. Instrukcja for może mieć jedną z dwóch postaci:

gdy wartość początkowa się zwiększa

FOR wartość := wartość_pocz TOwartość_końcowa DO instrukcja
gdy wartość początkowa się zmniejszaFOR wartość := wartość_pocz DOWNTO wartość_końcowa DO instrukcja

Iteracja

Iteracja (łac. iteratio – powtarzanie) – czynność powtarzania (najczęściej wielokrotnego) tej samej instrukcji (albo wielu instrukcji) w pętli. Mianem iteracji określa się także operacje wykonywane wewnątrz takiej pętli.

Czynność iteracji przedstawia pętla, zapisana w poniższym pseudokodzie:

 i=0
 dopóki i<10 wykonuj
    i=i+1
 przeskocz do góry

W pierwszej iteracji otrzymamy wartość i=1, w następnej i=2, potem i=3 i tak dalej, a iteracją jest powtarzana tu czynność, czyli zwiększanie zmiennej i o jeden (inkrementacja).

Kod w C++:

int i=0;
while (i<10) {
  i++;
}

Kod w Pythonie:

i = 0
while i < 10:
    i += 1