Tip:
Highlight text to annotate it
X
Czym jest algorytm?
W informatyce
algorytm to zestaw instrukcji
potrzebnych do rozwiązania danego problemu.
Algorytmy są zwykle wykonywane przez komputer,
ale my, ludzie, też ich używamy.
Na przykład, w jaki sposób
policzyłbyś wszystkie osoby w pokoju?
Pewnie tak jak ja,
czyli wskazałbyś na każdą osobę
i liczył od zera:
i liczył od zera:
1,2,3,4 i tak dalej.
To jest właśnie algorytm.
Wyraźmy to bardziej formalnie,
za pomocą pseudokodu
ze składnią jak w języku angielskim,
podobną do języka programowania.
Niech n równa się 0.
Dla każdej osoby n = n + 1.
Co oznacza ten pseudokod?
Wiersz 1 określa tak zwaną
zmienną n
i nadaje jej wartość początkową 0.
To znaczy, że na początku algorytmu
narzędzie, którym liczymy
ma wartość 0.
Nie zdążyliśmy jeszcze przecież
nic policzyć.
Nazywanie tej zmiennej n to tylko konwencja.
Można ją nazwać dowolnie.
Wiersz 2 oznacza początek pętli,
serii kroków, które zostaną wykonane kilka razy.
W tym przypadku krokiem jest
liczenie osób w pokoju.
Wiersz 3 opisuje szczegółowo,
sposób liczenia.
Wcięcie oznacza,
że wiersz 3 będzie powtarzany.
Tak więc pseudokod mówi,
że zaczynając od zera
przy każdej osobie w pokoju
n wzrośnie o 1.
Czy algorytm jest poprawny?
Sprawdźmy.
Czy zadziała, jeśli w pokoju będą 2 osoby?
Czy zadziała, jeśli w pokoju będą 2 osoby?
W wierszu 1 n wynosi zero.
Potem dla każdej osoby
zwiększamy n o 1.
W pierwszej pętli
n wzrasta do 1,
a w drugiej pętli, identycznej,
n wzrasta do 2.
Na końcu algorytmu n wynosi 2,
i tyle jest osób w pokoju.
Na razie wszystko gra.
Może jakiś nietypowy przykład?
Załóżmy, że w pokoju jest zero osób,
poza mną, ja liczę.
W wierszu 1 n znowu wynosi 0.
Tym razem jednak wiersz 3 nie jest wykonany,
bo w pokoju nie ma nikogo.
N pozostaje 0,
co zgadza się z liczbą osób.
Proste, prawda?
Ale liczenie każdej osoby oddzielnie jest mozolne.
Zróbmy to lepiej!
Policzmy po dwie osoby na raz.
Zamiast 1,2,3,4,5,6,7,8, itd.,
można policzyć
2,4,6,8 i tak dalej.
Będzie dużo szybciej.
Wyraźmy to za pomocą pseudokodu.
Niech n równa się zero.
Dla każdej pary osób w pokoju
n = n + 2.
Prosta zmiana.
Zamiast liczyć pojedynczo,
liczymy po dwie osoby na raz.
Algorytm jest więc dwa razy szybszy.
Algorytm jest więc dwa razy szybszy.
Ale czy jest poprawny?
Czy działa, jeśli w pokoju są 2 osoby?
W wierszu 1 n równa się zero.
Dla tej pary zwiększamy n o 2.
I na koniec otrzymujemy 2,
czyli rzeczywistą liczbę osób.
Teraz załóżmy, że w pokoju jest zero osób.
W wierszu 1 n to zero.
Jak poprzednio wiersz 3 zostanie ominięty,
bo w pokoju nie ma żadnej pary.
N pozostaje zero,
co równa się liczbie osób.
A jeśli w pokoju będą 3 osoby?
Co zrobi algorytm?
Sprawdźmy.
W wierszu 1 n równa się 0.
Dla tej pary
zwiększymy n o 2,
i co potem?
Nie ma już pełnej pary w pokoju,
więc wiersz 2 nie jest użyty.
Na koniec algorytmu
n wciąż wynosi 2, co jest błędem.
Algorytm jest wadliwy,
ma błąd.
Poprawmy to nowym kodem.
Niech n równa się zero.
Dla każdej pary w pokoju,
n = n + 2.
Jeśli 1 osoba zostaje bez pary,
n = n + 1.
By rozwiązać ten problem
wprowadziliśmy w wierszu 4 warunek,
znany jako rozgałęzienie.
Będzie wykonany tylko wtedy,
kiedy ktoś zostanie bez pary.
Teraz algorytm policzy wszystkie osoby,
czy będzie ich 1 czy 3
albo każda inna ilość.
Da się to poprawić?
Można na przykład liczyć po 3, 4, 5
albo nawet 10 osób,
ale trudno byłoby je wskazać.
Algorytmy, niezależnie od tego,
czy wykonywane przez komputery czy ludzi,
to zestawy instrukcji
do rozwiązywania problemów.
Pokazaliśmy tylko trzy.
A ty jaki problem rozwiążesz za pomocą algorytmu?