Ten artykuł został stworzony dla starszych wersji GameMakera i może nie być aktualny.

Wstep do algorytmow

Niedziela, 13 Czerwca 2004, 13:35
Czas czytania 3 minuty, 18 sekund
Poprawność całkowita i częściowa algorytmu, złożoność obliczeniowa algorytmu, złożoność czasowa średnia i pesymistyczna oraz rząd funkcji, czyli kilka podstawowych pojęć o algorytmach.
    Treść artykułu powstała przy pomocy skryptu stworzonego przez Panią Dr. Jolantę Koszelew z Politechiniki Białostockiej.

Def:
    Analiza algorytmów to dział informatyki zajmujący się szukaniem najefektywniejszych, poprawnych algorytmów dla danych problemów komputerowych.

----Poprawność całkowita i częściowa algorytmu-----

WP - warunek początkowy - formuła logiczna definiująca dane wejściowe algorytmu.

WK - warunek końcowy - formuła logiczna definiująca dane wyjściowe algorytmu uzyskane dla danych wejściowych spełniających WP.


Def:
    Algorytm A jest częściowo poprawny względem danego warunku WP i danego warunku WK wtedy i tylko wtedy, gdy dla dowolnych danych wejściowych spełniających warunek WP, jeżeli algorytm A zatrzymuje się, to dane wyjściowe algorytmu spełniają warunek WK.

Def:
    Algorytm A jest całkowicie poprawny względem danego warunku WP i danego warunku WK wtedy i tylko wtedy, gdy dla dowolnych danych wejściowych spełniających warunek WP algorytm A zatrzymuje się i dane wyjściowe tego algorytmu spełniają warunek WK.

Też nie przepadam za regółkami i definicjami.. dlatego poniżej zamieszczam przykład.
( Wyjasnienie -> slowa w niawiasach oznaczaja symbole logiczne stosowane w matematyce ktorych nie da sie wyswietlic na stronie).

WP: n>0 ^ n(należy do)N
WK: s=1+3+5+...+n n mod 2(różne od)0(lub) s=1+3+5+...+n-1 ^ n mod 2=0

Algorytm:
kods:=0; i:=1;
while i<>n+2 do
begin
    s:=s + i;
    i:=i+2;
end

    Algorytm jest poprawny częściowo, ale nie całkowicie. Dla n parzystego pętla nie ma stopu, ale dla dowolnego n nieparzystego pętla kończy się po skończonej liczbie kroków i wartość końcowa zmiennej s spełnia WK.

------ Złożoność obliczeniowa algorytmu -------

    Złożoność obliczeniowa algorytmu to nic innego jak ilość zasobów komputerowych, potrzebnych do jego wykonania. Zasoby komputerowe natomiast to czas działania i ilość zajmowanej pamięci.

d - dane wejściowe algorytmu, czyli takie, które spełniają warunek WP.
|d|- rozmiar danych d
Przykład:
A1:
WP: a1, a2, ..., an- ciąg liczb całkowitych (n >0)
WK: Ciąg a1, a2, ..., an posortowany niemalejąco
d - ciąg a1, a2, ..., an liczb całkowitych (n >0)
|d| - n

A2:
WP: a0, a1, ..., an- ciąg liczb rzeczywistych (n >= 0) definiujący współczynniki danego wielomianu W, x- dana liczba rzeczywista
WK: Liczba W(x) &#8211; wartość wielomianu W dla argumentu x
d - ciąg a0, a1, ..., an , ciąg liczb rzeczywistych (n >= 0) definiujący współczynniki danego wielomianu W
|d|- n+1

A3:
WP: t1, t2, ..., tn- ciąg znaków tekstu (n > 0)
w1, w2, ..., wm - ciąg znaków wzorca (n >= m > 0)
WK: p - zmienna logiczna przyjmuje wartość true, gdy wzorzec występuje w tekście, a false, gdy wzorzec nie występuje w tekście.
d - t1, t2, ..., tn- ciąg znaków tekstu (n > 0)
w1, w2, ..., wm - ciąg znaków wzorca (n >= m > 0)
|d|- n, m

Def :
    Operacja elementarna (inaczej operacja dominująca) to operacja charakterystyczna dla danego algorytmu. To taka operacja, że łączna ich liczba jest proporcjonalna do liczby wykonań wszystkich operacji jednostkowych w dowolnej komputerowej realizacji algorytmu.

Przykłady:

A1 - operacją elementarną jest operacja porównywania elementów sortowanego ciągu albo operacja przestawiania elementów ciągu w czasie sortowania.

A2 - operacją elementarną jest operacja arytmetyczna mnożenia albo operacja arytmetyczna dodawania realizowana w procesie obliczania wartości wielomianu dla danego x.

A3 - operacja porównywania znaków wzorca ze znakami tekstu w procesie sprawdzania, czy wzorzec występuje w tekście.

Za jednostkę złożoności czasowej przyjmuje się wykonanie jednej operacji elementarnej (dominującej). Złożoność czasowa algorytmu jest funkcją rozmiaru danych.

-------Złożoność czasowa średnia i pesymistyczna--------

cdn...
Komentarze (łącznie 3):
gnysek (Pią., 02 Lip. 04, 19:49)
#1

ee... a może od początku...
Albo wiem ja wam opowiem o liczbach zespolonych...

l
lion (Wto., 27 Lip. 04, 16:51)
#2

z Politechniki Białostockiej ??? Nie wiedziałem że w moim mieście są takie mądre ludzie :D

Marmot (Sob., 31 Lip. 04, 22:39)
#3

Widzę że dałeś przykład na pascala :D .

Najnowsze wersje GameMakera:

Stabilna
2024.2.0.132 • 2024.2.0.163
wydana 15 dni temu
LTS
2022.0.2.51 • 2022.0.2.49
wydana 154 dni temu
Beta
2024.400.0.516 • 2024.400.0.537
wydana  5 dni temu
= IDE, = Runtime
Użytkownicy online
2 użytkowników aktywnych:
gości: 1, userów: 1
 Adriann
(~ostatnie 15 minut)
Discord
16 użytkowników online na discordzie:
DungeonFairy🧚, Carl-bot, p..., Add92, SuperEnduro, Filyps, fervi, YoungKrystian, Kalor, antek, Uzjel, Dyno, Ulti, bagno, g..., Shockah
Shoutbox
I am Lord (19:15, 17.03.24)
6h mam na to hmmm
I am Lord (19:06, 17.03.24)
Ale temat fajny
gnysek (01:33, 13.03.24)
Powinno działać, jest w kodzie sortowanie wg. najbliższego startu :)
Uzjel (21:59, 11.03.24)
Nie, ale za pierwszym razem zrobiłem fuckup, że było "Tura testowa" X_X
I am Lord (16:58, 11.03.24)
A co Uzjel już masz nawymyślane 100 tematów? 😅
Uzjel (20:08, 10.03.24)
@gnysek a jak bym dodał kilka lig na raz to walnie?
Uzjel (20:08, 10.03.24)
Liga będzie zawsze od piątku 16:00 do poniedziałku 23:59, zawsze w środku miesiąca.
gnysek (08:48, 10.03.24)
Tak, to też jest do poprawy X_X
Adriann (18:22, 09.03.24)
Tylko myślę czy nie leiej gdyby mówiło że zostało tyle i tyle dni i ileś godzin a nie tylko w godzinach ;d Albo konkretna data obok, byłoby czytelniej
I am Lord (15:08, 08.03.24)
o super z tą ligą :)
Starsze wpisy znajdziesz w Archiwum.
Ankieta
Ile zarobiłeś do tej pory na grach stworzonych w GM?