Przykładowe zadania maturalne. Liczby cd.

Przykładowe zadania maturalne. Cyfry.

Przykładowe zadania maturalne. Liczby.

Przykładowe zadania maturalne.

Spotkanei 49. Szyfrowanie asymetryczne

1. Definicja szyfrowania asymetrycznego.
Kryptografia klucza publicznego (nazywana również kryptografią asymetryczną) - to rodzaj kryptografii, w którym używa się zestawów dwu lub więcej powiązanych ze sobą kluczy, umożliwiających wykonywanie różnych czynności kryptograficznych. Jeden z kluczy może być udostępniony publicznie bez utraty bezpieczeństwa danych zabezpieczanych tym kryptosystemem.

Algorytmy mające zastosowanie w kryptografii asymetrycznej wykorzystują operacje jednokierunkowe - takie, które da się łatwo przeprowadzić w jedną stronę a bardzo trudno w drugą. Np. mnożenie jest łatwe, a faktoryzacja trudna (na czym opiera się RSA). Potęgowanie modulo jest łatwe, a logarytmowanie dyskretne jest trudne (na czym opierają się ElGamal, DSA i ECC).

2. Najważniejsze zastosowania.
Najważniejsze zastosowania kryptografii asymetrycznej – szyfrowanie i podpisy cyfrowe – zakładają istnienie 2 kluczy – prywatnego i publicznego, przy czym klucza prywatnego nie da się łatwo odtworzyć na podstawie publicznego. W niektórych innych zastosowaniach kluczy może być więcej. 
  
3. Podpisy cyfrowe.
Strona uwierzytelniająca wylicza skrót (ang. hash) podpisywanej wiadomości. Następnie szyfruje ten skrót swoim kluczem prywatnym i jako podpis cyfrowy dołącza do oryginalnej wiadomości. Dowolna osoba posiadająca klucz publiczny może sprawdzić autentyczność podpisu, poprzez odszyfrowanie skrótu za pomocą klucza publicznego nadawcy i porównanie go z własnoręcznie wyliczonym na podstawie wiadomości.  

4. Schemat szyfrowania.

  Krok 1.
Alice przesyła do Boba swój klucz publiczny. 

 Krok 2 i 3.
Bob szyfruje wiadomość kluczem publicznym Alice, która to następnie  otrzymuje zaszyfrowaną wiadomość i rozszyfrowuje ją kluczem prywatnym.
 

Spotkanie 48. Szyfrowanie - wstęp

1. Szyfrowanie.

Metody szyfrowania tekstów oparte były głownie na zamianie i przestawianiu znaków lub symboli, a skuteczność utajniania zależała przede wszystkim od utrzymania w tajemnicy sposobu szyfrowania.Samą kryptologię można także postrzegać jako gałąź matematyki stosowanej i informatyki. Faktycznie w zastosowaniach informatycznych kryptologia nabiera praktycznego znaczenia w połączeniu z zagadnieniami dostępu do systemów operacyjnych, baz danych oraz sieci komputerowych i przesyłania danych.

2. Metody szyfrowania.

2.1. Szyfry przestawieniowe.

Szyfry te zmieniają uporządkowanie znaków w danych według pewnego schematu. Zazwyczaj dokonuje się przestawienia za pomocą pewnej figury geometrycznej. Szyfrowanie przebiega więc w dwóch krokach: tekst jawny wpisuje się do figury w sposób określony pewną tzw. ścieżką zapisu, a następnie odczytuje się go według określonego porządku (ścieżki odczytu) otrzymując tekst zaszyfrowany. Klucz obejmuje więc figurę geometryczną oraz ścieżki zapisu i odczytu.

Jako pierwszy przykład weźmy prosty 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. 

2.2. Szyfry podstawieniowe wieloalfabetyczne.

Stosuje się w nich wiele odwzorowań znaków tekstu jawnego na znaki kryptogramu, przy czym każde odwzorowanie jest z reguły typu jeden do jednego. Jak więc widzimy szyfry wieloalfabetyczne ukrywają rozkład częstości przez użycie wielu podstawień.

Szyfrowanie wiadomości przebiega tu na podstawie dowolnie wybranego słowa kluczowego (hasła). W przypadku znaków ASCI może to być dowolny ich ciąg. Do numeru każdego kolejnego znaku tekstu jawnego dodajemy numer odpowiadającego mu znaku słowa kluczowego i uzyskujemy znak kryptogramu. Gdy słowo kluczowe się skończy, bierzemy je kolejny raz od początku.

2.3. Szyfry podstawieniowe poligramowe.

Szyfry tego typu, w odróżnieniu od wyżej przedstawionych innych rodzajów szyfrów podstawieniowych, "obrabiają" jednocześnie większe grupy liter. Złamanie takiego szyfru jest zatem dużo trudniejsze dzięki odebraniu znaczenia częstości występowania liter lub znaków.

Dobrym, choć dosyć prostym, przykładem szyfru poligramowego jest szyfr Playfaira, wykorzystywany przez Anglików w czasie I wojny światowej. Kluczem jest tu macierz o wymiarach 5x5, w której skład wchodzą wszystkie litery alfabetu łacińskiego z wyjątkiem J. Użyjmy jako słowa-klucza słowa SZYFR. Zatem pierwszą czynnością będzie zapisanie liter alfabetu w kwadracie 5 x 5, zaczynając od słowa kluczowego i łącząc litery I oraz J.
 

 

Spotkanie 47. Odwrotna notacja Polska

1. Definicja ONP.
Odwrotna notacja Polska (ONP) (ang. RPN – Reverse Polish Notation) - zwana często również notacją Postfix, wymyślono w celu zapisywania dowolnych wyrażeń arytmetycznych bez nawiasów.

Notacja ONP jest szeroko wykorzystywana w kompilatorach języków wysokiego poziomu. Istnieją również języki, które do obliczeń stosują jedynie ONP – np. Forth.

W normalnym zapisie arytmetycznym operatory znajdują się pomiędzy argumentami:

2 + 2     6 - 4     3 * 5     12 / 3

Operatory posiadają priorytety, czyli "ważność". Jeśli w wyrażeniu wystąpią operatory o różnych priorytetach, to najpierw zostaną wykonane te ważniejsze:

3 + 5 * 2 = 3 + 10 = 13

Jeśli chcemy zmienić kolejność wykonywania działań, musimy używać nawiasów:

(3 + 5) * 2 = 8 * 2 = 16

W ONP problem ten nie występuje. Operator zawsze występuje po swoich argumentach:

2 2 +     6 4 -     3 5 *     12 3 /

Dzięki tej prostej zasadzie nawiasy stają się zbędne:

3 + 5 * 2 → 3 5 2 * + = 3 10 + = 13

(3 + 5) * 2 → 3 5 + 2 * = 8 2 * = 16

2. Zasada ONP.

Do obliczenia wartości wyrażenia zapisanego w ONP potrzebujemy stosu. Zasada jest następująca:

Wyrażenie ONP przeglądamy od strony lewej do prawej. Jeśli napotkamy liczbę, to umieszczamy ją na stosie. Jeśli napotkamy operator, to ze stosu pobieramy dwie ostatnie liczby, wykonujemy na nich działanie zgodne z napotkanym operatorem i wynik umieszczamy z powrotem na stosie. Gdy wyrażenie zostanie przeglądnięte do końca, na szczycie stosu będzie znajdował się jego wynik.

Przed przystąpieniem do zaprojektowania algorytmu ONP musimy poczynić pewne ustalenia. Dla prostoty umawiamy się, że używać będziemy tylko czterech operatorów arytmetycznych:

• + - dodawanie
• - - odejmowanie
• * - mnożenie
• / - dzielenie

 3. Przykład.

Spotkanie 46. Wyszukiwanie wzorca w tekście

1. Problem wyszukiwania wzorca.
W łańcuchu znakowym s znaleźć wszystkie wystąpienia wzorca p.

Problem Wyszukiwania Wzorca – WW (ang. pattern matching) to jeden z podstawowych problemów tekstowych, który intensywnie badali wybitni informatycy.

 2. Rozwiązanie.
Rozwiązaniem jest wskazanie w ciągu s wszystkich pozycji i takich, że zachodzi równość:

s[i : i + |p|] = p

Oznacza to, iż wzorzec p jest fragmentem łańcucha s występującym na pozycji i-tej.

Algorytm N – naiwny – ustawia okno o długości wzorca p na pierwszej pozycji w łańcuchu s. Następnie sprawdza, czy zawartość tego okna jest równa wzorcowi p. Jeśli tak, pozycja okna jest zwracana jako wynik, po czym okno przesuwa się o jedną pozycję w prawo i cała procedura powtarza się. Algorytm kończymy, gdy okno wyjdzie poza koniec łańcucha. Klasa pesymistycznej złożoności obliczeniowej algorytmu N jest równa O(n × m), gdzie n oznacza liczbę znaków tekstu, a m liczbę znaków wzorca. Jednakże w typowych warunkach algorytm pracuje w czasie O(n), ponieważ zwykle wystarczy porównanie kilku początkowych znaków okna z wzorcem, aby stwierdzić, iż są one niezgodne.

3. Rozwiązanie w C++

 

Spotkanie 45. Anagramy

1. Definicja anagramów.
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.
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.

2. C++

 

Spotkanie 44. Problem plecakowy - programowanie zachłanne

Dyskretny problem plecakowy - 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).