SZUKAJ NA TYM BLOGU

Algorytmy ()

Zadania:

Zagadnienia:

  • Definicja i własności, zapis (kod, schemat blokowy, pseudokod, lista kroków, opis słowny, drzewo )
  • Euklidesa, Hornera, szyfrujące, sortujące, sito Eratostenesa, inneMin, Max
  • Złożoność i wydajność
  • Strategie

Własności algorytmów:

  • skończona liczba operacji,
  • jednoznaczność operacji,
  • porządek operacji,
Złożoność algorytmu 
  • liniowa
  • kwadratowa
  • wykładnicza
  • logarytmiczna (najbardziej wydajny)
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;
  • zachłanna.

Algorytmy 

Sortujące:
  • przez wstawianie*,
  • wybór*,
  • szybkie*,
  • 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]
  • 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, NWW).
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..
i ← n
y ← a[n]
dopóki i ≠ 0 wykonuj
  i ← i – 1
  y ← y * z + a[i]
 

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/