Zadania maturalne

ASCII [aski] (ang. American Standard Code for Information Interchange) – 7-bitowy kod przyporządkowujący liczby z zakresu 0-127: literom (alfabetu angielskiego), cyfrom, znakom przestankowym i innym symbolom oraz poleceniom sterującym. Na przykład litera "a" jest kodowana liczbą 97, a znak spacji jest kodowany liczbą 32.

Litery, cyfry oraz inne znaki drukowane tworzą zbiór znaków ASCII. Jest to 95 znaków o kodach 32-126. Pozostałe 33 kody (0-31 i 127) to tzw. kody sterującesłużące do sterowania urządzeniem odbierającym komunikat, np. drukarką czyterminalem.

Ponieważ kod ASCII jest 7-bitowy, a większość komputerów operuje na 8-bitowychbajtach, dodatkowy bit można wykorzystać na powiększenie zbioru kodowanych znaków do 256 symboli. Powstało wiele różnych rozszerzeń ASCII wykorzystujących ósmy bit (np. norma ISO 8859, rozszerzenia firm IBM lub Microsoft), nazywanychstronami kodowymi. Również kodowanie UTF-8 można uważać za rozszerzenie ASCII, tutaj jednak dodatkowe znaki są kodowane na 2 i więcej bajtach.

Szyfrowanie asymetryczne

Szyfrowanie asymetryczne

Szyfrowanie asymetryczne (szyfrowanie z kluczem publicznym) jest nieco bardziej skomplikowane od szyfrowania symetrycznego. Podstawowa różnica polega na tym, że tutaj wyróżniamy dwa klucze - prywatny i publiczny. Oba klucze generowane są przez odbiorcę.

Szyfry asymetryczne wykorzystują dwa klucze: publiczny, który służy do zaszyfrowania wiadomości i prywatny - tajny, do odszyfrowania. Odbiorca wiadomości wysyła jawnie swój klucz publiczny, nadawca szyfruje nim wiadomość i wysyła. Do odszyfrowania służy klucz prywatny. Przechwycenie klucza publicznego nie pozwala na odszyfrowanie wiadomości. Nie można także w żaden sposób na jego podstawie odtworzyć klucza prywatnego. Szyfry asymetryczne są bardzo bezpieczne ale bardzo wolne. Dlatego najczęściej stosuje się kombinację tych dwóch typów szyfrowania. Samą wiadomość szyfruje się szybkim szyfrem symetrycznym a klucz bezpiecznym szyfrem asymetrycznym.

Algorytmy szyfrujące

Kryptoanaliza zajmuje się zarówno odtworzeniem tekstu jawnego (danych przed zaszyfrowaniem) gdy nie jest znany klucz kryptograficzny jak i odtworzeniem samego klucza. 
1. Przestawianie kolumnowe: 5kolumn:
K R Y P T
O A N A L
I Z A
szyfr odczytujemy rzędami: KOI RAA YN PA TL
2.Szyfr płotowy.Litery tekstu jawnego zapisuje się tu tak, aby tworzyły kształt przypominający wierzchołek płotu zbudowanego ze sztachet. Tekst zaszyfrowany otrzymujemy odczytując kolejne wiersze tak utworzonej konstrukcji. Proces szyfrowania możemy przedstawić na prostym przykładzie
Przykład. "JUTRO JEST SOBOTA" (pomińmy przy zapisie spacje):J            O              T               O
 U      R       J       S      S       B     T
    T                E                O             A


Przykład. "JUTRO JEST SOBOTA" (pomińmy przy zapisie spacje):J            O              T               O
 U      R       J       S      S       B     T
    T                E                O             A


3 Szyfry  wieloalfabetyczne:
BASI:
Mamy 4 alfabety:
B C D E F.... A
A B C... Z
S T U... R
I J K... H
 I z każdego alfabtu wybieramy odpowiadające znaki, np.  DRUK = ERUL
TELFON - ZNAK = SOLP

Słowo klucz(litery nie mogą się powtarzać):

Wyszukiwanie wzorca w tekście

Algorytm Knutha-Morrisa-Pratta- algorytm wyszukiwania wzorca w tekście. Wykorzystuje fakt, że w przypadku wystąpienia niezgodności ze wzorcem, sam wzorzec zawiera w sobie informację pozwalającą określić gdzie powinna się zacząć kolejna próba dopasowania, pomijając ponowne porównywanie już dopasowanych znaków. Dzięki temu właściwy algorytm działa w czasie liniowym od długości przeszukiwanego tekstu i wzorca (co dla dużych wzorców ma znaczenie).
Algorytm został wynaleziony przez Donalda Knutha i Vaughana Pratta i niezależnie przez J. H. Morrisa w 1977, ale wszyscy trzej opublikowali go wspólnie.

Algorytm wydawania reszty, palindromy, sortowanie tekstu oraz anagramy

Problem wydawania reszty – zagadnienie z dziedziny algorytmiki, problem polegający na wybraniu z danego zbioru monet o określonych nominałach takiej konfiguracji, by wydać żądaną kwotę przy użyciu minimalnej liczby monet. Jego rozwiązania są wykorzystywane w automatach z napojami, bankomatach itd.

Palindrom (gr. palindromeo – biec z powrotem) – wyrażenie brzmiące tak samo czytane od lewej do prawej i od prawej do lewej. Przykładem palindromu jest: Kobyła ma mały bok. Współcześnie palindromy pełnią funkcję gry słownej.

Anagram – nazwa wywodząca się od słów greckich: ana- (nad) oraz grámma(litera), oznacza wyraz, wyrażenie lub całe zdanie powstałe przez przestawienie liter bądź sylab innego wyrazu lub zdania, wykorzystujące wszystkie litery (głoski bądź sylaby) materiału wyjściowego. 

Palindrom

Palindrom (tudzież anagram odwrotny) jest to wyraz, liczba, który odczytany zarówno normalnie (od przodu), jak i wspak (od tyłu) daje taki sam ciąg, np. palindromem jest wyraz "kajak", czy liczba 656. Ponadto ciąg składający się z mniej niż dwóch znaków jest palindromem (np. litera K).

Algorytm

 1. boolean is_palindrome(string S)
 2. begin
 3.    integer I ← (ilość znaków z S) div 2 // przyjmujemy S[0] = pierwsza litera S
 4.    while I > 0 do
 5.    begin
 6.        I ← I - 1
 7.        if S[I] != S[ilość znaków z S - I - 1] then return false
 8.    end
 9.    return true
10. end

3. Deklaracja zmiennej I i przypisanie do niej połowy długości ciągu (zaniedbując część ułamkową), przekazanego w parametrze funkcji.
7. Jeśli I-ty znak ciągu S jest różny od znaku na pozycji: ilość znaków z S - I - 1, zwróć false - ciąg nie jest palindromem.
9. Podczas działania pętli, nie została zwrócona wartość false, więc ciąg jest palindromem.

Ogólny problem plecakowy

Dyskretny problem plecakowy (ang. discrete knapsack problem) jest jednym z najczęściej poruszanych problemów optymalizacyjnych. 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 plecakowy często przedstawia się jako problem złodzieja rabującego sklep – znalazł on N towarów; j–ty przedmiot jest wart  oraz waży . Złodziej dąży do zabrania ze sobą jak najwartościowszego łupu, przy czym nie może zabrać więcej niż B kilogramów. Nie może też zabierać ułamkowej części przedmiotów (byłoby to możliwe w ciągłym problemie plecakowym).

Podobny problem pojawia się często w kombinatoryce, teorii złożoności obliczeniowej, kryptografii oraz matematyce stosowanej.

Decyzyjna wersja przedstawionego zagadnienia to pytanie "czy wartość co najmniej Cmoże być osiągnięta bez przekraczania wagi W?"

Definicja

Definicja formalna: mamy do dys­pozycji plecak o maksymalnej pojemności  oraz zbiór  elementów , przy czym każdy element ma określoną wartość  oraz wielkość .

Dyskretny problem plecakowy (ang. 0-1 knapsack problem)

formalnie problem może być zdefiniowany:

zmaksymalizuj 

przy założeniach: 

Problem plecakowy, w którym liczba elementów danego typu jest ograniczona przez podaną wartość (ang. bounded knapsack problem).

Formalnie:

zmaksymalizuj 

przy założeniach: 

Można rozważać także przypadek w którym nie ma wartości ograniczającej liczbę elementów danego typu (ang. unbounded knapsack problem).

W ciągłym problemie plecakowym można brać ułamkowe części przedmiotów.

W przypadku, gdy problem jest rozważany przy założeniach, że

• jest problemem decyzyjnym
• jest dyskretny
• dla każdego elementu waga równa się wartości 

utożsamiany jest z problemem: czy dla danego zbioru liczb całkowitych istnieje taki jego podzbiór, że suma jego liczb wynosi dokładnie W? Zagadnienie to nazywane jest problemem sumy podzbioru.

Problem plecakowy może być rozwiązany przy użyciu programowania dynamicznego, ale rozwiązanie wielomianowe nie jest znane. Problem plecakowy oraz sumy podzbioru są problemami NP trudnymi, co było powodem użycia sumy podzbioru jako podstawy w niektórych systemach kryptografii asymetrycznej takich jak Merkle-Hellman. Algorytmy takie używały grup, nie liczb całkowitych. Merkle-Hellman oraz kilka podobnych algorytmów zostało w późniejszym czasie złamanych, ponieważ szczególny problem sumy podzbioru użyty w tych algorytmach były rozwiązywalne w czasie wielomianowym^.

Decyzyjna wersja problemu plecakowego opisana wyżej jest problemem NP zupełnym i jest jednym z 21 NP zupełnych problemów Karpa.

Realizacje algorytmu

Przegląd zupełny

Przegląd zupełny (bruteforce, metoda siłowa) – metoda nieefektywna obliczeniowo (ale optymalna, gdyż znajduje rozwiązanie najlepsze); w jego przypadku złożoność obliczeniowa al­gorytmu wyniesie , co zdecydowanie zawyży czas działania dla dużych n. Złożoność wynosi  ponieważ jest tyle możliwych ciągów zero jedynkowych na n polach. Złożoność można również obliczyć ze wzoru dwumianowego Newtona (dwumian Newtona) podstawiając za a i b jedynki.