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 73 dni temu
LTS
2022.0.2.51 • 2022.0.2.49
wydana 132 dni temu
Beta
2024.200.0.499 • 2024.200.0.516
wydana  5 dni temu
= IDE, = Runtime
Użytkownicy online
1 użytkownik aktywny:
gości: 1,
(~ostatnie 15 minut)
Discord
20 użytkowników online na discordzie:
LadyLush❄, DungeonFairy🧚, MKP, Carl-bot, p..., wojzx, Tival, YoungKrystian, PhysX ᴺⱽᴵᴰᴵᴬ, debil debilowski, Uzjel, lethian, HappyOrange, LeD, Dyno, Deusald, bagno, Tidżi, l..., Draczeq
Shoutbox
S
Sutikku (23:23, 23.02.24)
powiedziałbym, że może jakiś gigantyczny czerwony baner by się przydał, ale obawiam się, że mógł taki być, a ja go nie widziałęm
S
Sutikku (23:22, 23.02.24)
uwierzcie mi, że wchodzę na gmclan naprawdę bardzo często, ale jakoś tej ligi nie zauważyłem :(
I am Lord (12:01, 23.02.24)
Kurde kolejna tura mnie omineła 🙈
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, 🤦‍♂️🤦‍♂️
Starsze wpisy znajdziesz w Archiwum.
Ankieta
Ile zarobiłeś do tej pory na grach stworzonych w GM?