Prezentowane materiały są przeznaczone dla uczniów szkół ponadgimnazjalnych. Autor artykułu: mgr Jerzy Wałaszek Wersja 2.0 - zakończono XX.XX.2008, odwiedzono 76826 razy.

©2010 mgr Jerzy Wałaszek I LO w Tarnowie

Artykuł opisuje algorytmy wyszukujące informację w różnych zbiorach danych. Stanowi on kompilację wielu lat zajęć z młodzieżą licealną na kole informatycznym. Prezentowany materiał starałem się maksymalnie "odchudzić" ze zbędnych treści. Stąd ascetyczny wygląd poszczególnych rozdziałów. Mam jednak nadzieję, iż istotne treści w nich przetrwały.

Spis rozdziałów

Wstęp
Przedziały liczbowe i liczby

Liczby parzyste i nieparzyste
Liczby podzielne lub niepodzielne przez zadane podzielniki
NWD - algorytm Euklidesa
Liczby względnie pierwsze
Najmniejsza wspólna wielokrotność
Odwrotność modulo - rozszerzony algorytm Euklidesa
Liczby pierwsze - generacja przez sprawdzanie podzielności
Liczby pierwsze - generacja sitem Eratostenesa
Liczby pierwsze - generacja sitem liniowym
Liczby pierwsze - generacja sitem Atkina-Bernsteina
Czynniki pierwsze - metoda próbnych dzieleń
Czynniki pierwsze - metoda Fermata
Pierwszość liczby naturalnej - algorytmy naiwne
Pierwszość liczby naturalnej - Chiński Test Pierwszości
Pierwszość liczby naturalnej - Małe Twierdzenie Fermata
Pierwszość liczby naturalnej - test Millera-Rabina
Liniowe generatory liczb pseudolosowych
Generator pseudolosowy Park-Miller
Generator pseudolosowy Mersenne Twister
Wbudowane generatory liczb pseudolosowych
Generowanie liczb pseudolosowych
Liczby Fibonacciego
System liczbowy Fibonacciego
Całkowity pierwiastek kwadratowy

Tablice - wektory

Podstawowe operacje na tablicach
Wyszukiwanie liniowe
Wyszukiwanie liniowe z wartownikiem
Zliczanie wg kryterium
Wyszukiwanie max lub min
Jednoczesne wyszukiwanie max i min
Zastosowania wyszukiwania - sortowanie przez wybór
Wyszukiwanie najczęstszej wartości w zbiorze - dominanta
Wyszukiwanie lidera
Wyszukiwanie binarne
Wyszukiwanie interpolacyjne
Wyszukiwanie k-tego największego elementu
Wyszukiwanie szybkie k-tego największego elementu
Wyszukiwanie mediany zbioru

Łańcuchy znakowe

Podstawowe pojęcia dotyczące przetwarzania tekstów
Podstawowe operacje na łańcuchach znakowych
Naiwne wyszukiwanie wzorca w tekście
Wyszukiwanie maksymalnego prefikso-sufiksu
Szybkie wyszukiwanie wzorca algorytmem Morrisa-Pratta
Szybkie wyszukiwanie wzorca algorytmem Knutha-Morrisa-Pratta
Szybkie wyszukiwanie wzorca uproszczonym algorytmem Boyera-Moore'a
Szybkie wyszukiwanie wzorca pełnym algorytmem Boyera-Moore'a
Wyszukiwanie wzorca algorytmem Karpa-Rabina
Zliczanie słów w łańcuchu
Dzielenie łańcucha na słowa
Wyszukiwanie najdłuższego słowa w łańcuchu
Wyszukiwanie najdłuższego wspólnego podłańcucha
Wyszukiwanie najdłuższego wspólnego podciągu
Wyszukiwanie najkrótszego wspólnego nadłańcucha
Wyszukiwanie słów podwójnych
Wyszukiwanie palindromów
MasterMind - komputer kontra człowiek
MasterMind - człowiek kontra komputer
Szyfr Cezara
Szyfrowanie z pseudolosowym odstępem
Szyfr Enigmy
Szyfrowanie RSA

Macierze

Podstawowe pojęcia dotyczące macierzy
Reprezentacja macierzy w pamięci komputera
Mnożenie macierzy przez skalar
Dodawanie macierzy
Transponowanie macierzy
Mnożenie macierzy
Eliminacja Gaussa
Eliminacja Gaussa-Crouta
 

Listy

Drzewa

Grafy

Spis algorytmów

Przedziały liczbowe i liczby

001 Algorytm wyszukiwania liczb wg kryterium
002 Algorytm wyznaczania liczb wg kryterium
003 Algorytm generacji liczb parzystych
004 Algorytm wyznaczania liczb podzielnych przez zadane czynniki - wersja nr 1
005 Algorytm wyznaczania liczb podzielnych przez zadane czynniki - wersja nr 2
006 Algorytm wyszukiwania liczb niepodzielnych przez zadane liczby
007 Algorytm Euklidesa - wersja nr 1
008 Algorytm Euklidesa - wersja nr 2
009 Algorytm Euklidesa - wersja binarna
010 Algorytm wyznaczania liczb względnie pierwszych
011 Algorytm wyznaczania najmniejszej wspólnej wielokrotności
012 Algorytm wyznaczania odwrotności modulo
013 Algorytm wyznaczania liczb pierwszych przez sprawdzanie podzielności
014 Algorytm wyznaczania liczb pierwszych przez sprawdzanie podzielności - wersja ulepszona
015 Algorytm sita Eratostenesa
016 Algorytm ulepszonego sita Eratostenesa - wersja nr 1
017 Algorytm ulepszonego sita Eratostenesa - wersja nr 2
018 Algorytm sita liniowego
019 Algorytm sita Atkina-Bernsteina
020 Algorytm rozkładu liczby naturalnej na czynniki pierwsze - wersja nr 1
021 Algorytm rozkładu liczby naturalnej na czynniki pierwsze - wersja nr 2
022 Algorytm rozkładu liczby naturalnej na czynniki pierwsze metodą Fermata - wersja nr 1
023 Algorytm rozkładu liczby naturalnej na czynniki pierwsze metodą Fermata - wersja nr 2
024 Algorytm sprawdzania pierwszości liczby naturalnej - wersja nr 1
025 Algorytm sprawdzania pierwszości liczby naturalnej - wersja nr 2
026 Algorytm sprawdzania pierwszości liczby naturalnej - wersja nr 3
027 Algorytm obliczania a × b mod n
028 Algorytm obliczania a^e mod n
029 Algorytm testu pierwszości Fermata
030 Algorytm sprawdzania pierwszości nieparzystej liczby naturalnej testem Millera-Rabina
031 Algorytm generacji liczb pseudolosowych
032 Algorytm generatora pseudolosowego Park-Miller
033 Algorytm inicjowania rejestru generatora pseudolosowego Mersenne Twister
034 Algorytm generatora pseudolosowego Mersenne Twister
035 Algorytm mieszania pseudolosowego
036 Algorytm losowania bez powtórzeń
037 Algorytm generacji liczb Fibonacciego metodą rekurencyjną
038 Algorytm generacji liczb Fibonacciego metodą iteracyjną
039 Algorytm obliczania wartości liczby zapisanej w systemie Fibonacciego
040 Algorytm przeliczania liczby dziesiętnej na zapis w systemie Fibonacciego
041 Algorytm obliczania całkowitego pierwiastka kwadratowego - wersja nr 1
042 Algorytm obliczania całkowitego pierwiastka kwadratowego - wersja nr 2
043 Algorytm obliczania całkowitego pierwiastka kwadratowego - wersja nr 3

Tablice - wektory

044 Algorytm wyszukiwania liniowego/sekwencyjnego
045 Algorytm wyszukiwania liniowego z wartownikiem
046 Algorytm zliczania liniowego
047 Algorytm zliczania liniowego z wartownikiem
048 Algorytm wyszukiwania elementu maksymalnego w zbiorze
049 Algorytm wyszukiwania pozycji elementu maksymalnego w zbiorze
050 Algorytm jednoczesnego wyszukiwania max i min w zbiorze
051 Algorytm sortowania przez wybór
052 Algorytm znajdowania najczęstszej wartości - wersja nr 1
053 Algorytm znajdowania najczęstszej wartości - wersja nr 2
054 Algorytm znajdowania najczęstszej wartości - wersja nr 3
055 Algorytm znajdowania najczęstszej wartości - wersja nr 4
056 Algorytm wyszukiwania lidera w zbiorze
057 Algorytm wyszukiwania binarnego
058 Algorytm wyszukiwania interpolacyjnego
059 Algorytm wyszukiwania k-tego największego elementu - wersja nr 1
060 Algorytm wyszukiwania k-tego największego elementu - wersja nr 2
061 Algorytm wyszukiwania k-tego największego elementu - wersja nr 3
062 Algorytm partycjonowania zbioru wg pierwszego elementu
063 Algorytm szybkiego wyszukiwania k-tego największego elementu
064 Algorytm szybkiego sortowania i znajdowania mediany
065 Algorytm szybkiego wyszukiwania mediany
066 Algorytm Wirtha szybkiego wyszukiwania mediany

Łańcuchy znakowe

067 Algorytm naiwny wyszukiwania wzorca w łańcuchu tekstowym
068 Algorytm naiwny wyszukiwania wzorca z wartownikami
069 Algorytm naiwny wyszukiwania maksymalnego prefikso-sufiksu
070 Algorytm Morrisa-Pratta wyszukiwania maksymalnego prefikso-sufiksu
071 Algorytm Morrisa-Pratta wyszukiwania wzorca
072 Algorytm Knutha-Morrisa-Pratta tworzenia tablicy KMPNext
073 Algorytm Knutha-Morrisa-Pratta wyszukiwania wzorca
074 Algorytm tworzenia tablicy Last[] dla algorytmu Boyera-Moore'a
075 Uproszczony algorytm  Boyera-Moore'a wyszukiwania wzorca
076 Algorytm etapu nr 1 tworzenia tablicy BMNext[ ] dla pełnego algorytmu Boyera-Moore'a
077 Algorytm etapu nr 2 tworzenia tablicy BMNext[ ] dla pełnego algorytmu Boyera-Moore'a
078 Pełny algorytm Boyera-Moore'a wyszukiwania wzorca
079 Algorytm Karpa-Rabina wyszukiwania wzorca
080 Algorytm zliczania wyrazów
081 Algorytm podziału łańcucha na słowa
082 Algorytm wyszukiwania najdłuższego słowa w łańcuchu
083 Algorytm wyszukiwania najdłuższego wspólnego podłańcucha
084 Algorytm dynamiczny wyszukiwania najdłuższego wspólnego podłańcucha - wersja nr 1
085 Algorytm dynamiczny wyszukiwania najdłuższego wspólnego podłańcucha - wersja nr 2
086 Algorytm znajdowania długości najdłuższego wspólnego podciągu - wersja rekurencyjna
087 Algorytm znajdowania najdłuższego wspólnego podciągu - wersja rekurencyjna
088 Algorytm znajdowania długości najdłuższego wspólnego podciągu - wersja dynamiczna
089 Algorytm znajdowania najdłuższego wspólnego podciągu - wersja dynamiczna
090 Algorytm wyszukiwania najkrótszego wspólnego nadłańcucha
091 Algorytm wyszukiwania najdłuższego sufiksu pasującego do prefiksu w drugim łańcuchu
092 Algorytm wyszukiwania słów podwójnych w łańcuchu - wersja nr 1
093 Algorytm wyszukiwania słów podwójnych w łańcuchu - wersja nr 2
094 Algorytm naiwny wyszukiwania palindromów
095 Algorytm Manachera wyszukiwania palindromów
096 Algorytm gry MasterMind - komputer kontra człowiek
097 Algorytm gry MasterMind - człowiek kontra komputer
098 Algorytm szyfrowania tekstu kodem Cezara
099 Algorytm deszyfrowania tekstu zaszyfrowanego kodem Cezara
100 Algorytm szyfrowania z pseudolosowym odstępem
101 Algorytm deszyfrowania z pseudolosowym odstępem
 

Macierze

102 Algorytm mnożenia macierzy przez skalar
103 Algorytm dodawania macierzy
104 Algorytm transponowania macierzy
105 Algorytm transponowania macierzy kwadratowej w miejscu
106 Algorytm mnożenia macierzy
107 Algorytm eliminacji Gaussa
108 Algorytm eliminacji Gaussa-Crouta

Listy

Drzewa

Grafy

Literatura

1. Wprowadzenie do algorytmów, T.H.Cormen, C.E.Leiserson, R.L.Rivest, WNT 1997,2004
2. Algorytmy + Struktury danych = Programy, N.Wirth, WNT 2001
3. Algorytmy i struktury danych, L.Banachowski, K.Diks, W.Rytter, WNT 2006
4. Język C++, Stroustroup, WNT 2002
5. C++, 50 efektywnych sposobów na udoskonalenie Twoich programów, S.Meyers, HELION 2003.
6. Język C++ bardziej efektywny, S.Meyers, WNT 1998
7. STL w praktyce. 50 sposobów efektywnego wykorzystania, S.Meyers, HELION 2004
8. Symfonia C++, J.Grębosz, Oficyna Kallimach, Kraków 1999
9. Język ANSI C, B.Kernighan, D.Ritchie, WNT 2004
10. Wydajne programowanie – Extreme Programming, K.Beck, A.Cynthia, Mikom 2005
11. Jak pisać efektywne przypadki użycia, A.Cockburn, WNT 2004
12. 7 nawyków skutecznego działania, S.Covey, REBIS 2002
13. Aspekty kombinatoryki, V.Bryant, WNT 1977
14. Matematyka Konkretna, R.L.Graham, D.E.Knuth, O.Patashnik, PWN 1996
15. Kombinatoryka dla programistów, W.Lipski
16. Analiza kombinatoryczna, W.Lipski, W.Marek, PWN 1986
17. Metody numeryczne, Z.Fortuna, B.Macukow, J.Wąsowski, WNT Warszawa, 1982, 2005
18. Przegląd metod i algorytmów numerycznych, M.Dryja, J. i M.Jankowscy, WNT 1988
19. Wprowadzenie do teorii grafów, R.J.Wilson, PWN 1985
20. Wstęp do matematyki, H.Rasiowa, PWN 1971, 1984, 1998
21. Teoria mnogości, K.Kuratowski, A.Mostowski, PWN 1978
22. The Art of Computer Programming, D.E.Knuth, Addison-Wesley Publishing Company
23. Programming Pearls, J.Bentley, Addison-Wesley Publishing Company 2000
24. Data Structures and Program Design in C++, R.L. Kruse, A.J. Ryba, Prentice Hall
25. Jewels of stringology, W.Rytter, M.Crochemore, World Scientific 2003
26. Software Engineering, R.Pressman, McGraw-Hill 1997.