ZADANIA MATURALNE

Na lekcjach staramy się zmierzyć z zadaniami maturalnymi.
Między innymi, w trakcie naszej pracy poruszyliśmy:

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ące służące do sterowania urządzeniem odbierającym komunikat, np. drukarką czy terminalem.

Ponieważ kod ASCII jest 7-bitowy, a większość komputerów operuje na 8-bitowych bajtach, 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), nazywanych stronami 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. Odbiorca za pomocą klucza prywatnego odszyfrowuje klucz i za pomocą tego klucza całą wiadomość. Jest to metoda szybka i bezpieczna.

Schemat działania szyfru asymetrycznego przedstawia poniższy rysunek.

Algorytmy szyfrujące

 Algorytmy szyfrujące

1.Szyfr (inaczej kryptograficzny algorytm szyfrujący) – jest to funkcja matematyczna wykorzystywana do szyfrowania tekstu jawnego lub jego deszyfrowania. Zazwyczaj jedna funkcja wykorzystywana jest do szyfrowania, a inna do deszyfrowania wiadomości. Wiadomość przed zaszyfrowaniem nazywana jest tekstem jawnym, zaś wiadomość zaszyfrowaną nazywamy szyfrogramem. Proces zamiany tekstu jawnego na szyfrogram nazywamy szyfrowaniem^.

Kryptoanaliza zajmuje się zarówno odtworzeniem tekstu jawnego (danych przed zaszyfrowaniem) gdy nie jest znany klucz kryptograficzny jak i odtworzeniem samego klucza.

2. 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

3.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

4. Szyfry  wieloalfabetyczne:

Słowo klucz(litery nie mogą się powtarzać):
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

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; Anagramy ; Sortowanie tekstu

 Problem wydawania reszty

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.

Przykładowe zadanie

Dane są trzy nominały – 1 zł, 2 zł i 5 zł. Ile minimalnie monet potrzeba, by wydać 13 zł?

Rozwiązanie

Poniżej pokazano dwa popularne rozwiązania tego problemu dla wariantu problemu, w którym zakłada się dostępność dowolnej liczby monet każdego nominału: jedno przy pomocy algorytmu zachłannego, drugie z wykorzystaniem programowania dynamicznego.

Niech:

k – żądana kwota; wg przykładu 13

n – największy element zbioru nominałów

x – liczba potrzebnych monet; początkowo 0

Algorytm zachłanny

Algorytm zachłanny jest poprawny dla tego problemu w większości stosowanych obecnie systemów monetarnych, jednak nie działa np. dla systemu (1, 4, 5) (kontrprzykładem jest kwota 8).

W tym przypadku, algorytm będzie wartość:

k – w każdym kroku pomniejszał o n

n – porównywał z wartością k, by stwierdzić, czy jest ona mniejsza lub równa

x – w każdym kroku zwiększał o 1

Algorytm odejmuje od zadanej kwoty największy spośród nominałów mniejszych i równych kwocie. Następnie, o ile kwota jest większa od zera, powtarza czynność. Liczba powtórzeń jest liczbą potrzebnych monet.

Dla powyższego przykładu algorytm zadziała następująco:

k	13	8	3	1
n	5	5	2	1
x	1	2	3	4

Zaletą powyższego algorytmu jest szybkość i prostota implementacji.

 Palindrom

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. Prawdopodobnie tak było również i w przeszłości, choć pewne znaleziska sugerują, że palindromy mogły też mieć znaczenie magiczne.

 Anagram

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. W czasopismach szaradziarskich pojawiają się zadania polegające na odgadnięciu wykreskowanego anagramu na podstawie wierszowanego komentarza, a także anagramy rysunkowe polegające na ułożeniu hasła z wszystkich liter właściwego określenia rysunku. Formami spokrewnionymi z anagramem są stenoanagram, egzoanagram i endoanagram.

Najprostszy anagram to poukładanie liter w odwrotnej kolejności, np. kebab – babek. Przykładem jednego z prostych przestawień jest zamiana sylab w wyrazie ranty, dająca anagram: tyran. Przestawiając pojedyncze litery możemy otrzymać np. anagram narty.

W 1998 Barbara i Adam Podgórscy w swoim Vademecum szaradzisty (Wydawnictwo Kurpisz) jako rekordowy podało anagram złożony z 16 elementów: krasa, Arska, raska, sarka, askar, kasar, Raksa, sakra, Arkas, Araks, Karsa, rakas, Karas, Sakar, Skara, Askra. Nie należy go jednak traktować jako niezmiennik, ponieważ przybywa zarówno słów, jak i metod wyszukiwania. Już choćby w podanym „rekordzie” dociekliwy czytelnik zauważy brak jednego potocznego wulgaryzmu oraz słowa Ksara.