IMG962 (5)

•    typ podstawy T

•    skończony zbiór elementów który jest pusty

•    zawiera korzeń z dwoma rozłączonymi binarnymi drzewami lewym i prawym pod drzewem korzenia

Przykład:

•    drzewo genetyczne

•    zapis rozgrywanych turniej

Operacje:

• metody przeglądania drzewa:

o PREORDER przejście wzdłużne o POSTORED przejście wsteczne o INORDER przejście poprzeczne

KRYPTOGRAFIA

cel — umożliwienie bezpiecznego przesyłu danych

Wymagania wobec szyfru:

•    algorytm SiO powinny być wydajny

•    dla dowolnych MiK musi zachodzić D(K,S(K,M)) = M

•    szyfr musi być bezpieczny

Jak zdefiniować bezpieczny szyfr:

Zasada KERCKHOFFS:

Szyfr (S,D)musi być bezpieczny nawet jeśli Ewa zna algorytm SiO. Ewa nie zna klucza K.

Zły pomysł:

Szyfr jest bezpieczny jeśli Ewa nie potrafi zgadnąć wiadomości M na podstawie szyfrogramu C=SfK,M)

Definicja bezpieczeństwa mówimy że szyfr jest (t,a) bezpieczny jeśli żadna Ewa dysponująca czasem t nie potrafi zgadnąć czy Alicja wybrała M czy N prawdopodobieństwem większym 0,5t a

Idealny szyfr powinien być bezpieczny (°°,0)

Doskonały szyfr Vermana mówi że klucz musi być tej samej długości co wiadomość. Nie można używać klucza wielokrotnie.

Twierdzenie Shannona - każdy doskonałym szyfrze klucz nie może być krótszy niż wiadomość