DYNAMICZNE STRUKTURY DANYCH

struktury implementowane za pomocą wskaźników, dzięki czemu pamięć pod

nie przydzielana jest dynamicznie.

Zalety: Wady

- skalowalność, - utrudniony dostęp do danych (dostęp sekwencyjny),

- lepsze wykorzystanie pamięci; - dodatkowe pole na wskaźnik;

LISTA

struktura dynamiczna składająca się z dowolnej, nieznanej na początku i zmiennej

ilości elementów powiązanych ze sobą za pomocą wskaźników w taki sposób,

że poprzedni element wskazuje na następny (lista jednokierunkowa). Dodatkowo

do listy dołącza się wskaźnik do jej pierwszego elementu (korzeń). Elementem listy

jest rekord, który zawiera pola ze swoimi danymi oraz dodatkowe pole zawierające

wskaźnik do następnego elementu. W ostatnim elemencie listy wartość wskaźnika

ustawia się na wskazanie puste.

Rodzaje list:

● lista jednokierunkowa● lista dwukierunkowa● lista uporządkowana

● lista cykliczna

Zastosowanie:

stos – kolejka typu LIFO (last in first out), czyli struktura, w której dostępny jest

jedynie pierwszy (ostatni) element; operacje:

push()

pop()

kolejka FIFO (first in first out) – struktura, w której dane dopisywane na koniec,

a obsługiwane i usuwane z początku

kolejka priorytetowa – struktura, której elementy wyposażone w dodatkowe pole

określające priorytet danego elementu

DRZEWO

struktura dynamiczna składająca się z dowolnej, nieznanej na początku i zmiennej

ilości elementów (węzłów) powiązanych ze sobą za pomocą wskaźników w taki

sposób, że dany element (przodek) wskazuje na elementy następne (potomków);

struktura drzewiasta o typie podstawowym T jest węzłem typu T ze skończoną

liczbą dowiązanych rozłącznych struktur drzewiastych o typie podstawowym T

(nazywanych poddrzewami), lub strukturą pustą. Elementem drzewa jest rekord,

który zawiera pola ze swoimi danymi oraz wskaźniki na swoje poddrzewa.

Korzeń – najwyższy węzeł drzewa to (jest to jedyny deklarowany element).

Liść (element końcowy) – element nie mający potomków, w którym wartości wskaźników

ustawia się na wskazania puste.

Węzeł wewnętrzny – element nie będący liściem.

Gałąź (krawędź) – powiązanie pomiędzy dwoma węzłami.

Stopień węzła – liczba bezpośrednich potomków węzła wewnętrznego. Stopień drzewa –

maksymalny stopień wszystkich węzłów (liczba wskaźników zawartych w deklaracji typu

elementu).

Poziom węzła – liczba gałęzi prowadzących do węzła. Poziom korzenia = 1.

Głębokość (wysokość) drzewa – maksymalny poziom wszystkich elementów.

Długość ścieżki (drogi) x – liczba gałęzi (krawędzi), które należy przejść aby od korzenia

dojść do węzła x (długość ścieżki węzła na poziomie i = i, długość ścieżki korzenia = 1).

Długość ścieżki wewnętrznej – suma długości ścieżek wszystkich elementów drzewa.

Długość ścieżki zewnętrznej (w drzewie uzupełnionym w ten sposób, że w miejsce

każdego wskazania pustego jest wstawiony specjalny węzeł) – suma długości ścieżek

wszystkich węzłów specjalnych.

Waga węzła – prawdopodobieństwo konieczności dostępu do węzła (jeśli jest ono znane).

Ważona długość ścieżki poszukiwania – suma wszystkich ścieżek z korzenia do

każdego węzła pomnożonych przez wagi węzłów.

Koszt – średnia ważona długość ścieżki.

Drzewo binarne – drzewo o stopniu drugim – skończony zbiór węzłów, który zawiera

węzeł z dwoma rozłącznymi binarnymi drzewami (lewym i prawym poddrzewem), albo jest

pusty (każdy element ma co najwyżej dwoje potomków).

Rodzaje drzew binarnych:

drzewo doskonale zrównoważone – drzewo, w którym dla każdego węzła liczba węzłów

w jego prawym i lewym poddrzewie różni się co najwyżej o 1;

drzewo zrównoważone AVL – drzewo, w którym dla każdego węzła wysokości dwóch

jego poddrzew różnią się co najwyżej o 1;

drzewo poszukiwań (leksykograficzne) – drzewo, w którym dla każdego węzła

wszystkie klucze z lewego poddrzewa są mniejsze od klucza, a wszystkie klucze

z prawego poddrzewa są od niego większe;

optymalne drzewo – drzewo poszukiwań, którego struktura daje najmniejszy koszt

spośród drzew o danym zbiorze elementów i danych prawdopodobieństwach;

stóg – drzewo, w którym wartość klucza w węźle jest mniejsza od wartości kluczy w jego

potomkach;

Współczynnik wyważenia – dodatkowe pole w węźle, równe różnicy wysokości prawego

i lewego poddrzewa, mogące przyjmować wartości -1, 0, 1;

● dla liścia współczynnik wyważenia jest równy 0

● jeśli liść jest lewym potomkiem od pola wyważenia przodka odejmuje się 1

● jeśli liść jest prawym potomkiem do pola wyważenia przodka dodaje się 1

● jeśli równowaga w przodku zostaje zachwiana (wartość różna od 0) współczynnik

propaguje dalej

Drzewa wyższych rzędów:

● drzewo wielokierunkowe – drzewo bez ustalonej ilości potomków – węzeł może

mieć wielu potomków:

Drzewa wyższych rzędów:

● b-drzewo – drzewo złożone ze stron, czyli z poddrzew, do których węzłów

uzyskiwany jest jednoczesny dostęp.

Własności b-drzewa rzędu n:

- każda strona zawiera co najwyżej 2n obiektów;

- każda strona, z wyjątkiem strony zawierającej korzeń, zawiera co najmniej n

obiektów;

- każda strona jest liściem albo ma m+1 potomków, gdzie m jest liczbą jej

kluczy;

- wszystkie strony liście występują na tym samym poziomie.

● B*-drzewa – wszystkie węzły z wyjątkiem korzenia muszą być wypełnione

przynajmniej w 2/3, czyli liczba kluczy k w niebędącym korzeniem węźle wynosi

(2m-1)/3 <= k <= m-1

● B+-drzewa – połączenie B-drzewa przechowującego indeksy i listy danych; węzeł

wewnętrzny przechowuje klucze, wskaźniki i licznik kluczy, liść przechowuje klucze,

dane, licznik kluczy i wskaźnik na następny liść

● uniwersalna struktura słownikowa – służy do przechowywania słowników oraz

zarządzania danymi przy kluczach będących słowami (ciągami znaków); węzeł

zawiera tablicę wskaźników odpowiadających poszczególnym znakom alfabetu

rozszerzoną o wskaźnik końca słowa

● drzewa trie – służy do przechowywania słowników oraz zarządzania danymi przy

kluczach będących słowami (ciągami znaków); węzły wewnętrzne zawierają tablice

wskaźników odpowiadających poszczególnym znakom alfabetu rozszerzonego

o znak końca słowa; liście zawierają rekordy z danymi; w drzewie mogą być

przechowywane zarówno całe słowa, jak i ich początki

przeglądanie drzewa

preorder: inorder: postorder:

procedure D(t:wsk); procedure D(t:wsk); procedure D(t:wsk);

begin begin begin

if t<>nil then if t<>nil then if t<>nil then

begin begin begin

P(t); D(t^.lewe); D(t^.lewe);

D(t^.lewe); P(t); D(t^.prawe);

D(t^.prawe); D(t^.prawe); P(t);

end end end end end end

szukanie elementu x w drzewie poszukiwań:

znaleziony:=false; while (t<>nil) and (znaleziony = false) do begin

if t^.klucz = x then znaleziony := true else if t^.klucz>x then t:= t^.lewe else t:= t^.prawe end;

GRAF

struktura dynamiczna zbudowana z węzłów i krawędzi, jednak nie wprowadzająca

ograniczenia na jednoznaczność ścieżek.

Węzły sąsiednie – węzły, pomiędzy którymi istnieje krawędź.

Ścieżka – ciąg krawędzi prowadzących od jednego węzła do drugiego.

Spójna składowa – węzeł oraz wszystkie węzły z niego osiągalne; maksymalny

zbiór takich węzłów, że między każdą parą węzłów istnieje ścieżka.

Rodzaje grafów:

● graf niezorientowany (nieskierowany) składa się ze skończonego zbioru węzłów N

oraz skończonego zbioru krawędzi E, przy czym każda gałąź jest nieuporządkowaną

parą węzłów

● graf skierowany – graf, którego krawędzie są skierowane, czyli każda krawędź jest

uporządkowaną parą węzłów; w tym wypadku krawędź z A do B nie jest równa

krawędzi z B do A

Porządek topologiczny – odwiedzanie węzłów w takiej kolejności, aby

każdy węzeł był odwiedzany dopiero po odwiedzeniu wszystkich węzłów,

z których krawędzie prowadzą do niego.

Sortowanie topologiczne – proc:es znajdowania porządku topologicznego.

● graf z wagami – graf, w którym z każdą ścieżką połączona liczbę określającą jej wagę

Waga ścieżki – suma wag wszystkich krawędzi na tej ścieżce.

graf dwuspójny – zbiór węzłów, dla których istnieją zawsze dwie różne ścieżki;

w przypadku grafu o dwóch węzłach graf będzie dwuspójny, jeśli węzły będą połączone

Punkt artykulacji – węzeł, którego usunięcie wraz z krawędziami

spowodowałoby rozbicie grafu na dwie lub więcej spójne składowe.

● graf rzadki – graf o liczbie krawędzi rzędu mniejszego od kwadratu liczby węzłów

● graf gęsty – graf o liczbie krawędzi rzędu kwadratu liczby węzłów

Podstawowe algorytmy:

algorytmem Fleury'ego – odszukuje cykl Eulera; graf Eulera – graf, w którym da się skonstruować cykl Eulera, czyli drogę, która przechodzi przez każdą jego krawędź dokładnie raz i wraca do punktu wyjściowego;

problem komiwojażera – wyznacza ścieżkę Hamiltona; graf hamiltonowski - graf

zawierający ścieżkę przechodzącą przez każdy wierzchołek dokładnie jeden raz (scieżkę Hamiltona)

algorytm Roy-Warshalla – wyznacza domknięcie przechodnie grafu (wyszukuje dostępne połączenia między węzłami);

algorytm Floyda – wyznacza optymalną drogę między wierzchołkami grafu z wagami;

problem plecakowy - Nazwa zagadnienia pochodzi od maksymalizacyjnego problemu wyboru przedmiotów, tak by ich sumaryczna wartość była jak największa i jednocześnie mieściły się w plecaku. Przy podanym zbiorze elementów o podanej wadze i wartości, należy wybrać taki podzbiór by suma wartości była możliwie jak największa, a suma wag była nie większa od danej pojemności plecaka.

Problem kasjera - należy wydać żądaną kwotę przy pomocy minimalnej liczby monet, korzystając z podanych nominałów. Każdy nominał jest dostępny w nieograniczonej ilości.

Algorytm – ściśle określony sposób postępowania, który w skończonej liczbie kroków

daje oczekiwany wynik; przepis wykonania czynności.

Cechy algorytmu:

● jeśli posiada dane wejściowe, to pochodzą one z dobrze zdefiniowanego zbioru;

● ciąg reguł jest skończony;

● jest precyzyjnie zdefiniowany, każdy krok jest jednoznacznie określony.

Projektowanie zstępujące (top-down design)

Ogólna zasada:

● zdefiniuj problem do rozwiązania;

● podziel problem na główne kroki (podproblemy) - stopniowe uszczegóławiani;

● podproblemy dziel ponownie na mniejsze kroki, aż do uzyskania podproblemów

łatwych do rozwiązania.

Zalety:

● otrzymane rozwiązanie jest modularne;

● teoretycznie rozwiązanie jest łatwiejsze do zrozumienia i analizy;

● rozwiązania poszczególnych kroków mogą być wykorzystane wielokrotnie, także przy

innych zadaniach.

Projektowanie wstępujące (bottom-up design)

Ogólna zasada:

● zdefiniuj problem do rozwiązania;

● na podstawie istniejących funkcji języka definiuj własne do momentu, gdy problem

będzie możliwy do rozwiązania w rozszerzonym języku.

Zalety:

● rozszerzenie możliwości języka;

● stworzone funkcje mogą być wykorzystywane wielokrotnie.

Obiekt rekurencyjny – obiekt, który częściowo składa się z siebie samego lub jego

definicja odwołuje się do jego samego.

Rekurencja umożliwia definiowanie nieskończonego zbioru obiektów za pomocą

skończonego wyrażenia.

Rekurencja bezpośrednia:

procedura (lub funkcja) P jest bezpośrednio rekurencyjna, jeśli zawiera odwołanie

do samej siebie .

Rekurencja pośrednia: procedura (lub funkcja) P jest pośrednio rekurencyjna, jeśli

zawiera odwołanie do procedury (lub funkcji) Q, natomiast Q zawiera odwołanie

do P (bezpośrednie lub pośrednie).

Rekurencja końcowa – w procedurze lub funkcji rekurencyjnej występuje tylko

jedno wywołanie rekurencyjne i jest ono ostatnią instrukcją (znajduje się ono na

samym końcu procedury). W przeciwnym wypadku mamy do czynienia z

rekurencją niekońcową.

Cechy algorytmów rekurencyjnych:

● zakończenie algorytmu jest jasno określone;

● problem został rozłożony na problem elementarny, którego rozwiązanie jest znane.

Nie należy stosować rekurencji:

● gdy ważna jest szybkość działania algorytmu;

● gdy można spodziewać się dużej ilości wywołań rekurencyjnych;

● gdy pewne obliczenia będą musiały być powtórzone wielokrotnie.

Algorytm siłowy (brute-force)

Siłowy begin if (szukane rozwiązanie akceptowalne) or (istnieje tylko jedno rozwiązanie) then

sprawdzaj kolejne możliwości do momentu znalezienia rozwiązania;

if (szukane rozwiązanie najlepsze) then sprawdź wszystkie możliwości i wybierz najlepszą; end;

Algorytm zachłanny (żarłoczny, greedy algorithm)

zachłanny(W) begin rozwiązanie=zbiór pusty; while (nie znaleziono pełnego rozwiązania)

and (W nie jest zbiorem pustym) do begin X=wybor(W); if pasuje(X) then

rozwiązanie=rozwiązanie + X; end; end;

Algorytm „dziel i zwyciężaj” („dziel i rządź”, divide and conquer)

dziel_i_zwyciezaj(N) begin if (N wystarczająco mały) then zwróć przypadek elementarny(N)

else begin podziel problem (N) na k podproblemów; for i:=1 to k do dziel_i_zwyciezaj(Ni);

zwróć wynik na podstawie wyników cząstkowych; end; end;

Algorytm oparty na programowaniu dynamicznym (dynamic programming)

tab:array [1..N] of (rozwiązanie podproblemu) begin

for i:=1 to (ilość przypadków elementarnych) do wypełnij tab[i];

for i:=(ilość przypadków elementarnych + 1) to N do

wyznacz tab[i] na podstawie elementów od tab[1] do tab[i-1]; end;

Algorytm z powrotami (backtracking)

próbuj następny krok begin repeat wybierz następnego kandydata;

if (kandydat poprawny) then begin zapisz go; if (rozwiązanie niepełne) then

begin próbuj następny krok; if (próba nieudana) then usuń zapis; end; end;

until próba udana lub brak kandydata; end;

Algorytm podziału i ograniczeń (branch and bound algorithm)

próbuj (kandydat) begin if (włączenie obiektu jest akceptowalne) then

begin dołącz kandydata do zbioru wynikowego; if (kandydat nie jest ostatni) then

próbuj(kolejny kandydat) else sprawdź optymalność; usuń kandydata ze zbioru wynikowego;

end; if (wykluczenie obiektu jest akceptowalne) then begin zapisz kandydata;

if (kandydat nie jest ostatni) then próbuj(kolejny kandydat) else sprawdź optymalność; end; end;

RODZINY ALGORYTMÓW

✔ sortowanie danych ✔ wyszukiwanie danych, poszukiwanie wzorca ✔ algorytmy numeryczne

✔ kodowanie ✔ kompresja

Sposoby sprawdzania poprawności algorytmu:

- analiza kodu;

- sprawdzenie struktury programu;

- przeprowadzenie testów funkcjonalnych;

- przeprowadzenie weryfikacji programu.

Weryfikacja programu - logiczny dowód poprawności kodu we wszystkich przypadkach.

Specyfikacja - określa wynik działania programu oraz związek pomiędzy danymi wejściowymi i wyjściowymi; jest niezależna od kodu. Weryfikacja powinna stwierdzić, że kod programu jest zgodny z jego specyfikacją, czyli że program posiada własność częściowej poprawności.

W specyfikacji określone są dwa warunki:

warunek wstępny (precondition, asercja początkowa)

– warunek określający dane wejściowe, który musi być spełniony na początku programu;

warunek końcowy (postcondition, asercja końcowa)

– dotyczy wyjścia programu, opisuje wartości, które program oblicza.

Pętla z wartownikiem:

wczytaj daną;{odczyt początkowy} while dana nie jest wartownikiem do

begin operacje wczytaj daną end

Niezmiennik pętli z wartownikiem:

Wszystkie wartości wejściowe, oprócz ostatniej, zostały przetworzone.

Żadna z wartości wejściowych, oprócz być może ostatniej, nie jest wartownikiem.

Pętla z licznikiem:

i := a; while i <= b do begin operacje i:=i+1; end

Niezmiennik pętli z licznikiem:

Elementy od a do i - 1 zostały przetworzone.

a <= i. Jeżeli a <= b to i <= b + 1, w przeciwnym wypadku i = a.

Złożoność obliczeniową

definiuje się jako iloczyn złożoności czasowej T i złożoności przestrzennej S:

O(n)= T(n)×S(n)

przy czym T i S wyrażane są jako funkcje długości n ciągu wejściowego.

Notacja „wielkie O”

Definicja:

f(n) jest O(g(n)) jeśli istnieją liczby dodatnie c, N takie, że f(n) ≤ cg(n) dla wszystkich n ≥ N.

f(n) = aknk + ak-1nk-1 + ... + a1n + a0 -> O(nk)

Notacja „wielkie Ω”

Definicja:

f(n) jest Ω(g(n)) jeśli istnieją liczby dodatnie c, N takie, że f(n) ≥ cg(n) dla wszystkich n ≥ N.

f(n) = Ω(g(n)) <=> g(n) = O(f(n))

Notacja „wielkie θ”

Definicja:

f(n) jest θ(g(n)) jeśli istnieją liczby dodatnie c1, c2 , N takie, że c1g(n) ≤ f(n) ≤ c2 g(n)

dla wszystkich n ≥ N.

f(n) = θ(g(n)) <=> f(n) = O(g(n)) oraz f(n) = Ω(g(n))

Mieszanie

wyliczenie pozycji elementu w tablicy na podstawie wartości klucza.

Funkcja mieszająca – funkcja h(k), gdzie k jest wartością klucza, przekształcająca klucz w indeks.

Doskonała funkcja mieszająca – funkcja mieszająca zwracająca różne wartości indeksu dla różnych wartości klucza.

Minimalna doskonała funkcja mieszająca – doskonała funkcja mieszająca, która do umieszczenia n elementów wykorzystuje nelementową tablicę.

Kolizja – sytuacja, w której funkcja mieszająca zwraca tą samą wartość dla różnych kluczy.

Dzielenie:

h(k) = k mod Tsize gdzie: k – klucz, TSize – wielkość tablicy h(k) = (k mod p) mod TSize

gdzie: p – liczba pierwsza i p > Tsize np.: h(54321) = 54321 mod 100 = 21

Składanie z przesuwaniem:

h(k): podziel klucz na fragmenty; dodaj fragmenty; h(k) = (k mod d + k div d) mod TSize

gdzie: k – klucz, d – dzielnik, TSize – wielkość tablicy np.: h(54321) = 54+321 = 375

h(54321) = 5+43+21 = 69

Składanie brzegami:

h(k): podziel klucz na fragmenty; zamień kolejność cyfr w co drugim fragmencie;

dodaj fragmenty; … ((k1 mod 10) * 10) + (k1 div 10) ... gdzie: k1 – fragment klucza

np.: h(54321) = 54+123 = 177 h(54321) = 5+34+21 = 60

Środek kwadratu:

h(k): podnieś klucz do kwadratu; wytnij środkową część wyniku;

h(k) = (k*k div d1 mod d2) mod Tsize gdzie: k – klucz, d1, d2 – dzielnik, TSize – wielkość tablicy

np.: h(54321) = [(54321)2 = 2950771041] = 77

Wycinanie:

h(k): wybierz dowolny fragment klucza;

np.: h(54321) = 321

h(54321) = 543

h(54321) = 43

Zamiana podstawy:

h(k): przekształć klucz do postaci zapisanej w systemie

pozycyjnym o innej podstawie;

np.: h(54321)= [system ósemkowy] = 15206

h(54321) = [system dziewiątkowy] = 8245

ADRESOWANIE OTWARTE:

jeśli pozycja h(k) jest zajęta, sprawdzane są pozycje:

norm(h(k)+p(i))

gdzie: norm – funkcja normująca p – funkcja przyrostu,

i = 1, 2, ...; dopóki nie zostanie znaleziona wolna pozycja.

Metoda Cichelliego:

h(słowo)=((długość słowa) + g(pierwsza litera słowa) + g(ostatnia litera słowa)) mod TSize

gdzie: g – funkcja, którą należy znaleźć, przekształcająca literę w liczbę,

tak, aby funkcja h nie powodowała kolizji, TSize – wielkość tablicy. wybierz wartość max (ograniczenie rekurencji);

oblicz liczbę wystąpień każdej pierwszej i ostatniej litery w zbiorze słów;

uporządkuj słowa ze względu na częstość występowania pierwszych i ostatnich liter;

dla wszystkich słów:

jeśli dla pierwszej lub ostatniej litery l słowa s nie jest znana wartość g

powtarzaj:

wyznacz wartość g(l), jako pierwszą niebadaną wartość

z przedziału <0, max>;

do momentu znalezienia wartości g(l), która nie powoduje kolizji

w funkcji h(s) lub przekroczeniu wartości max;

jeśli wartość max została przekroczona

cofnij się do poprzedniej litery i wyznacz jej nową wartość

klucze:

MERKURY, WENUS, ZIEMIA, MARS, JOWISZ, SATURN, URAN, NEPTUN

max = 3, TSize = 8

pierwsze i ostatnie litery z ilością wystąpień M-2, Y-1, W-1, S-3, Z-2, A-1, J-1, N-4, U-1

litery w kolejności: N-4, S-3, M-2, Z-2, Y-1, W-1, A-1, J-1, U-1

Wyszukiwanie wzorca w tekście

Algorytm brute-force:

analiza ewentualnych zgodności – przeszukiwany znak po znaku, kolejne znaki tekstu porownywane są z pierwszym znakiem wzorca: ● jeśli takie same, to: ● porownywane kolejne znaki tekstu z kolejnymi znakami wzorca: ● jeżeli takie same to porownywana kolejna para ● jeżeli to ostatni znak wzorca, to znaczy, że wzorzec znaleziony ● jeżeli rożne to cofnięcie w tekście do znaku po pierwszym zgodnym i wzorca do pierwszego znaku wzorca

Algorytm Boyera i Moore'a

Metoda opiera się na wykrywaniu niezgodności. porownywany jest ostatni znak wzorca ze znakiem na miejscu = długości wzorca: ● jeżeli znak nie należy do wzorca to przesunięcie w tekście o długość wzorca ● jeżeli należy do wzorca to przesunięcie tak, aby znaki się pokryłyi porownywanie od końca

Algorytm Rabina i Karpa

na zasadzie porownania funkcji mieszającej H:

● dla wzorca Hw = H(wzorzec), wartość wyznaczana raz

● odczytywanie na bieżąco M znakow tekstu i obliczanie Ht = H(tekst[M) (najpierw pierwsze M znakow, potem dla znakow od drugiego do M+1, potem od trzeciego do M+2 itd.)

● porownywanie Hw i Ht :

● jeśli rowne – najprawdopodobniej znaleziono wzorzec

(o ile H dobrano tak, aby nie było kolizji)

● jeśli rożne – obliczanie kolejnej wartości Ht

Wbrew pozorom algorytm jest szybki, jeżeli właściwie dobrano H – funkcja powinna umożliwiać obliczenie kolejnej wartości Ht' na podstawie poprzednio wyliczonej wartości Ht

KODOWANIE

Jest to przedstawienie informacji w postaci nadającej się do zapamiętania i przesyłu. Przykładem kodowania jest kod ASCII (8-bitowy), pozwalający zapisać znaki za pomocą bitow (0 i 1).

SZYFROWANIE

Szyfr to rodzaj kodu, system umownych znakow stosowany celu zatajnienia wiadomości, żeby była ona niemożliwa (lub bardzo trudna) do odczytania przez każdego, kto nie posiada odpowiedniego klucza.

Szyfrowanie natomiast jest procedurą przekształcania wiadomości nie zaszyfrowanej w zaszyfrowaną. Wiadomość przed zaszyfrowaniem nazywa się tekstem jawnym, a wiadomość

zaszyfrowaną – szyfrogramem.

Szyfry historyczne musiały umożliwiać szyfrowanie i deszyfrowanie przez człowieka, a więc opierać się na bardzo prostych operacjach. Wspołczesne komputery potrafią złamać praktycznie każdy tego typu szyfr. Szyfry klasyczne (historyczne): ● Szyfr przesuwający ● Szyfr podstawieniowy ● Szyfr monoalfabetyczny ● Szyfr polialfabetyczny

Szyfr przesuwający (ang. shift cipher) to szyfr, w ktorym każdemu znakowi

tekstu jawnego odpowiada dokładnie jeden znak w szyfrogramie, przesunięty

o określoną, stałą liczbę znakow w alfabecie. Litery z końca alfabetu stają się

literami z jego początku.

Szyfr Cezara - szyfr stosowany przez Gajusza Juliusza Cezara, rzymskiego wodza i polityka, będący klasycznym przykładem szyfru przesuwającego z kluczem rownym 3.

Przykład: Ala ma kota -> Dod pd nrwd

Szyfry podstawieniowe to szyfry, ktorych działanie opiera się na podstawianiu

pod znaki alfabetu jawnego znakow alfabetu szyfrowego.

Kodowanie tabelkowe polega na przypisaniu każdej literze numeru,

Szyfr monoalfabetyczny to szyfr, w ktorym jednej literze alfabetu jawnego odpowiada dokładnie jedna litera alfabetu tajnego – wszystkie przedstawione do tej pory szyfry spełniają ten warunek.

Szyfr taki nigdy nie zapewniał bezpieczeństwa i nie zapewnia go tym bardziej dzisiaj.

Metody łamania szyfru monoalfabetycznego:

● w przypadku znanego choćby małego fragmentu tekstu jawnego z powtarzającymi się znakami - umiejscowienie go w tekście tajnym poprzez poszukiwanie podobnych wzorcow, np. jeśli występuje słowo "baobab", szukamy ciągu liter (xb, xa, xo, xb, xa, xb), czyli takiego, gdzie na pierwszym,

czwartym i szostym miejscu występuje ten sam znak, oraz na drugim i piątym ten sam, ale inny od tamtych, a jeszcze inny na trzecim.

● w ogolniejszym przypadku należy policzyć rozkład statystyczny znakow w zaszyfrowanym tekście i porownać z rozkładem w dowolnym tekście jawnym z tego samego języka (najlepiej, ale niekoniecznie, tego samego autora na podobny temat). Przy dłuższym tekście tajnym pozwala to na idealne rozszyfrowanie.

Szyfr polialfabetyczny – uogolnienie szyfru monoalfabetycznego na większą liczbę przekształceń. Szyfr taki składa się z n przekształceń, takich że pierwszą literę szyfrujemy pierwszym przekształceniem, drugą drugim itd., po czym powtarzamy przekształcenia od początku począwszy od litery n+1. Szyfry polialfabetyczne maja wspołcześnie wyłącznie historyczne znaczenie.

Każdy z wierszy tablicy odpowiada szyfrowi Cezara, przy czym w pierwszym wierszu przesunięcie wynosi 0, w drugim 1 itd. Aby zaszyfrować pewien tekst, potrzebne jest słowo kluczowe. Słowo kluczowe jest tajne i mowi, z ktorego wiersza (lub kolumny) należy w danym momencie skorzystać.

Podpisujemy klucz pod tekst. Następnie wykonujemy szyfrowanie w następujący sposob: litera szyfrogramu odpowiada literze (z tabeli) znajdującej się na przecięciu wiersza, wyznaczanego przez literę tekstu jawnego i kolumny wyznaczanej przez literę słowa kluczowego.

Odszyfrowywanie przebiega bardzo podobnie: Pobieramy kolejne litery szyfrogramu oraz odpowiadające im litery słowa kluczowego (podobnie, jak przy szyfrowaniu). Wybieramy kolumnę

odpowiadającą literze słowa kluczowego. Następnie w tej kolumnie szukamy litery szyfrogramu. Numer wiersza odpowiadający znalezionej literze jest numerem litery tekstu jawnego. Przy łamaniu tego szyfru nie zadziała analiza statystyczna, bo jedna liczba kodowana jest w wiele. Wszystkie przedstawione do tej pory szyfry to szyfry symetryczne. Do kodowania i dekodowania wykorzystują ten sam klucz.

Wspołcześnie metody szyfrowania możemy podzielić na 3 grupy:

● szyfry asymetryczne,

● symetryczne szyfry blokowe,

● symetryczne szyfry strumieniowe.

W szyfrowaniu asymetrycznym występują 2 klucze – klucz publiczny służący do szyfrowania, oraz klucz prywatny służący do deszyfrowania. Ponieważ nie ma potrzeby rozpowszechniania klucza prywatnego, bardzo małe są szanse, że wpadnie on w niepowołane ręce. Szyfry asymetryczne

opierają się na istnieniu pewnych trudnych do odwrocenia problemow.

RSA to pierwszy i obecnie jeden z dwoch najpopularniejszych (obok ElGamala) algorytmow kryptografii asymetrycznej. Stworzony w roku 1978 przez zespoł: Ronald Rivest, Adi Shamir, Leonard Adleman. RSA jest akronimem utworzonym z pierwszych liter nazwisk jego tworcow.

RSA opiera się na trudności faktoryzacji dużych liczb (znalezieniu liczb całkowitych ktorych iloczyn jest rowny danej) – znalezienie szybkiej metody faktoryzacji doprowadziłoby do złamania RSA, aczkolwiek nie ma dowodu, że nie da się złamać RSA w inny sposob. Żeby wygenerować klucz RSA losujemy dwie duże liczby pierwsze p i q, oraz liczbę e względnie pierwszą z zakresu 1..(p − 1)(q − 1).

Szyfry blokowe...

...to procedury, ktore szyfrują niewielkie bloki danych (znacznie mniejsze od typowej wiadomości).

Wspołcześnie jest to najczęściej 128 bitow (AES), choć do niedawna przeważały 64-bitowe bloki (DES, 3DES, Blowfish, IDEA). Klucze są znacznie mniejsze, mają zwykle od 128 do 256 bitow, przy czym wartości mniejsze od 80 (DES – 56) są uważane za niewystarczające.

DES (ang. Data Encryption Standard) to blokowy szyfr symetryczny. Opiera się na mieszaniu i rozpraszaniu. Jedna seria przekształceń to runda. W DES stosuje się 16 takich samych rund. Tekst dzielony na bloki 64 bity. Klucz ma długość 56 bitow (jest kodowany jako 64-bitowe słowo).

Schemat jednej rundy:

● podział 64b tekstu na dwa bloki po 32b (lewy L i prawy R),

● blok R łączony jest z kluczem,

● do wyniku dosumowywany blok L,

● wynik zapisywany jako nowe R,

● nowe L = poprzednie, niezmienione R.

Szyfry strumieniowe...

...szyfrują każdy znak tekstu jawnego osobno, generując znak strumienia szyfrującego i przekształcając go na przykład z użyciem funkcji XOR ze znakiem danych.

W związku z tym nie jest konieczne oczekiwanie na cały blok danych, jak w przypadku szyfrow blokowych. Najpopularniejszym wspołczesnym szyfrem strumieniowym jest RC4. Inne popularne szyfry strumieniowe to A5/1 i A5/2 stosowane w telefonii komorkowej. Do szyfrow strumieniowych należą też historyczne szyfry polialfabetyczne i monoalfabetyczne.

Zasada Kerckhoffsa

to jedna z podstawowych zasad wspołczesnej kryptografii, sformułowana w XIX wieku przez holenderskiego kryptologa Augusta Kerckhoffsa:„System kryptograficzny powinien być bezpieczny nawet wtedy, gdy wszystkie szczegóły jego działania – oprócz klucza – są znane.” Zasadę tę spełniają wszystkie wspołcześnie stosowane algorytmy szyfrujące (DES, AES i inne), ktorych specyfikacje są w pełni jawne. Utajnienie algorytmu szyfrującego może wpłynąć na bezpieczeństwo, ale tylko wtedy gdy jest on wykorzystywany w ograniczonym środowisku, np. na szczeblu rządowym (np. polski szyfr NASZ = Narodowy Algorytm Szyfrujący). Większość tajnych algorytmow, ktore wprowadzano na rynek w celach komercyjnych i na skalę masową, została szybko ujawniona i złamana

Metoda Newtona

zi = zi-1 – f(zi-1)/f'(zi-1) function zero(x0:real):real; begin if f(x0)<eps then zero:=x0 else

zero(x0-f(x0)/fp(x0)) end;

Metoda Lagrange'a

function interpol:real; var wnz, om, w : real; i, j : integer; begin wnz:=0; om:=1; for i:=0 to n do begin om:=om*(z-x[i]); w:=1; for j:=0 to n do if i<>j then w:=w*(x[i]-x[j])

wnz:=wnz+y[i]/(w*(z-x[i])) end; interpol:=wnz*om; end;

Metoda Simpsona

var s, h:real; i:integer; f:array[0..2*n] of real; ... s:=0; h:=(b-a)/(2*n); i:=0; repeat s+=h*(f[i]+4*f[i+1]+f[i+2])/3

i:=i+2;

until i>=2*n;