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
2023.11.1.129 • 2023.11.1.160
wydana 69 dni temu
LTS
2022.0.2.51 • 2022.0.2.49
wydana 128 dni temu
Beta
2024.200.0.499 • 2024.200.0.516
wydana  wczoraj
= IDE, = Runtime
Użytkownicy online
2 użytkowników aktywnych:
gości: 1, userów: 1
 Adriann
(~ostatnie 15 minut)
Discord
44 użytkownicy online na discordzie:
LadyLush❄, 🧁Cupcake🧁, DungeonFairy🧚, MKP, s..., Alice, Nitro Slav, Carl-bot, Voytec, Wielki Druid, Add92, Kowu, Kuzyn, YoungKrystian, Radek Ignatów, PhysX ᴺⱽᴵᴰᴵᴬ, r..., lethian, HappyOrange, Moldis, Arrekin, MagnusArias, LeD, yazaa, Domeen0, Dyno, Deusald, Korodzik, 𝕳𝖚𝖌𝖔 𝕲𝖔𝖓𝖝𝖆𝖑𝖊𝖝, blackamul, Marco, m..., bagno, Tidżi, Mtax, g..., Alkapivo, moeglich, Nikas, Krzysiek1250, Shockah, Kandif, Cosplyfanka, xVANiLL
Shoutbox
gnysek (10:49, 20.02.24)
Ja czekam na pluginy do IDE, czego YYG nie zrobi, zrobimy sami.
Adriann (11:50, 16.02.24)
Ciekawe jak go przerobią, osobiście liczę na jakąś większą rewolucję a nie tylko usprawnienie bo narazie jest jak jest :d
gnysek (10:32, 08.02.24)
Edytor roomów ma swoje minusy. Ale ma być tworzony nowy wkrótce, chociaż pewnie 6-12 miesięcy zanim trafi do wersji stabilnej jak nic.
p
pablo1517 (08:40, 07.02.24)
No ja odkąd zacząłem w ue4 pracować to niestety z GMLem dawno nie obcowalem
exp (20:13, 30.01.24)
@pablo1517 ja przerzuciłem się z klasycznego GM na Studio cztery lata temu, więc przeskok trochę mniejszy, ale generalnie idea dużo się nie zmieniła. jest trochę upierdliwości i niepotrzebnych według mnie zmian, ale też duże usprawnienia (edytor roomów to raj na ziemi w porównaniu z tym oryginalnym)
Adriann (18:59, 28.01.24)
Takk..strasznie są upierdliwe :D
I am Lord (17:08, 28.01.24)
Mniej czasu się straci tworząc system particli z kodu od zera niż się męczyć z importem ich z edytora, 🤦‍♂️🤦‍♂️
I am Lord (16:56, 28.01.24)
Co jest nie tak z tymi particlami z IDE, masakra jakaś. Ile to trzeba kombinować żeby użyć je prosto z kodu
p
pablo1517 (17:57, 27.01.24)
Czyli GML nie dostał jakiś drastycznych zmian?
gnysek (14:47, 26.01.24)
Czy ja wiem... generalnie zamysł ten sam, tylko IDE nieco inne.
Starsze wpisy znajdziesz w Archiwum.
Ankieta
Ile zarobiłeś do tej pory na grach stworzonych w GM?