Szukaj na tym blogu

Algorytmy

Zadania:

Poziom podstawowy

Zagadnienia:

  • Definicja, własności, zapis (opis słowny, lista kroków, drzewo, schemat blokowy, pseudokod, kod)
  • Algorytmy w SP
  • Euklidesa, szyfrujące, sortujące, sito Eratostenesa, inne Min, Max, podzielność liczb i inne 
  • Strategie;

Własności algorytmów:

  • skończona liczba operacji,
  • jednoznaczność operacji,
  • porządek operacji,

Strategie

  • przeszukiwania liniowego może być wykorzystana do: sprawdzenia, czy dany znak występuje w tekście, znalezienia najmniejszego elementu w ciągu liczb;
  • dziel i zwyciężaj.

Algorytmy 

Sortujące:
  • przez wstawianie*,
  • wybór*,
  • szybkie*,
  • bąbelkowe,
  • kubełkowe
  • przez scalanie

    * algorytmy sortowania przez porównania

Szyfrujące (kryptograficzne, zapewniają bezpieczeństwo przesyłanych informacji):
  •  RSA
  •  PGP
Algorytm Euklidesa służy do obliczania największego wspólnego dzielnika dwóch liczb (NWD).
Algorytm zwany sitem Eratostenesa polegający na „wykreślaniu” wielokrotności kolejnych (niewykreślonych wcześniej) liczb naturalnych służy wyznaczeniu liczb pierwszych z zadanego przedziału.
Schemat Hornera służy do obliczania wartości wielomianu dla danej wartości przy minimalnej liczbie operacji mnożenia..

Poziom rozszerzony

Zagadnienia:

  • Hornera, sito Eratostenesa, inne np. szyfrujące, sortujące
  • Złożoność i wydajność
  • Strategie
Algorytmy

  • Schemat Hornera
    i ← n
    y ← a[n]
    dopóki i ≠ 0 wykonuj
      i ← i – 1
      y ← y * z + a[i]
  • Sortowanie bąbelkowe,
    dla j = 1, 2, ..., n-1
      dla i = 1, 2, ... , n-1
        jeśli A[i] > A[i+1] to A[i] ↔ A[i+1]

Strategie

  • zachłanna.

 Złożoność algorytmu 

  • liniowa
  • kwadratowa
  • wykładnicza
  • logarytmiczna (najbardziej wydajny)

Palindromy

Palindromem nazywamy słowo, które czytane od lewej i od prawej strony jest takie samo.
Na przykład palindromami są słowa:
JABFDFBAJ
HAJAHAJAH
ABBA
Słowo JANA nie jest palindromem.

Wyszukiwania wzorca w tekście metodą naiwną


Szyfr Cezara

Podstawieniowy szyfr Cezara z przesunięciem (kluczem) k polega na zastąpieniu każdego znaku jawnego znakiem leżącym w alfabecie o k pozycji w prawo od zastępowanego znaku. Przykład: znak ‘B’ po zakodowaniu kluczem k=3 zastąpiony zostanie znakiem ‘E’. 

… A B C D E F …
     > > >
     1 2 3

Przy szyfrowaniu znaku należy postępować w sposób cykliczny, to znaczy, jeżeli znak nie posiada w alfabecie następnika przesuniętego o k pozycji, to alfabet „zawija się" i za literą Z następuje znów litera A. Przykład: jawny znak ‘X’ po zakodowaniu kluczem k=3 zastąpiony zostanie znakiem ‘A’, znak ‘Y’ – znakiem ‘B’, natomiast ‘Z’ – znakiem ‘C’. 

… W X Y Z A B C D …
     > > >
     1 2 3

Szyfr kolumnowy

Szyfrowanie kolumnowe jest jedną z metod szyfrowania przestawieniowego, polegającego na zmianie kolejności znaków w szyfrowanym tekście. W tej metodzie jest wykorzystywana tabela o dodatniej liczbie wierszy równej k. Liczba k jest nazywana kluczem. Wiersze i kolumny tabeli są numerowane liczbami naturalnymi, począwszy od 1. Znaki tekstu, który ma być zaszyfrowany, wpisujemy do kolejnych kolumn tabeli, zaczynając od jej lewego górnego rogu. W kolumnach nieparzystych znaki wpisujemy od góry do dołu, a w parzystych od dołu do góry. Puste miejsca w ostatniej rozpoczętej kolumnie wypełniamy znakiem „_” oznaczającym spację. Następnie odczytujemy kolejne wiersze od góry do dołu (każdy z nich od lewej do prawej), w wyniku czego uzyskujemy szyfrogram.

Przykład: dla klucza k=3 i tekstu MATURA_Z_INFORMATYKI budujemy tabelę:

M A _ F O Y K

A R Z N R T I

T U _ I M A _

i otrzymujemy szyfrogram MA_FOYKARZNRTITU_IMA_.

Zadania (źródła):

Filmy

Złożoność obliczeniowa

Metody sortowania

Przypisy

  1. https://cke.gov.pl/egzamin-maturalny/egzamin-maturalny-w-formule-2015/arkusze/
  2. https://cke.gov.pl/images/_EGZAMIN_MATURALNY_OD_2015/Materialy/Zbiory_zadan/Matura_Zbi%C3%B3r_zada%C5%84_Informatyka.pdf
  3. https://cke.gov.pl/images/_EGZAMIN_MATURALNY_OD_2015/Informatory/2015/Informatyka.pdf
  4. https://cke.gov.pl/egzamin-maturalny/egzamin-w-starej-formule/arkusze/
Subskrybuj: Posty (Atom)