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.06.2.162 • 2024.6.1.208
wydana  2 dni temu
LTS
2022.0.2.51 • 2022.0.2.49
wydana 274 dni temu
Beta
2024.600.0.585 • 2024.600.0.609
wydana 20 dni temu
= IDE, = Runtime
Użytkownicy online
2 użytkowników aktywnych:
gości: 1, userów: 1
 Chell
(~ostatnie 15 minut)
Discord
34 użytkownicy online na discordzie:
Kysiu, s..., Alice, Nitro Slav, Carl-bot, LadyLush, debil debilowski, OdrzuconyKrakers, HappyOrange, fervi, Sevitaus, PhysX ᴺⱽᴵᴰᴵᴬ, lethian, Michał Parkoła, Draczeq, MKP (GEM), Arrekin, Dyno, 🆅🅸🆃🅾74🅼, LeD, 𝕳𝖚𝖌𝖔 𝕲𝖔𝖓𝖝𝖆𝖑𝖊𝖝, Miłosz, ArturG, m..., bagno, Tidżi, Danieo, g..., l..., Add92, Shockah, Cosplyfanka, exigo, PeekoHiko
Shoutbox
gnysek (11:36, 08.07.24)
Ale w sumie taki numer GG był bezpieczniejszy niż nr. telefonu czy kontakt społecznościowy. Utrudniał stalkowanie i ułatwiał banowanie.
Wojo (08:08, 08.07.24)
Niestety to już nie te czasy kiedy pytało się kasjerki o wiek i numer Gadu-Gadu...
Adriann (08:28, 05.07.24)
Albo okraść :|
Adriann (08:28, 05.07.24)
Może pani chciała zobaczyć twoje dane i Cię poderwać :d
gnysek (10:38, 03.07.24)
Mnie ostatnio w Żabce zapytali o wiek. A mam już ponad dwie osiemnastki.
Wojo (08:27, 30.06.24)
Ogólnie to miał być żart ponieważ portal internetowy, którego można opisać jako PH jest portalem przeznaczonym dla dorosłych. Miało być śmiesznie wyszło żenująco, a wiadomości w shoutboxie nie mogę skasować :P
Wojo (09:40, 28.06.24)
Tymon jak co wizytę musiałem potwierdzić wiek
gnysek (14:15, 17.06.24)
Bo Łapusz woli alkohol, niż się organizować. Co tam Pixel Heaven, sprawdźcie jego zbiórki na książki...
Adriann (21:02, 13.06.24)
Bardzo słusznie, straszna patola z tą organizacją :D
I am Lord (08:35, 13.06.24)
Ale co jak co, zrobiło się o imprezie głośno.
Starsze wpisy znajdziesz w Archiwum.
Ankieta
Ile zarobiłeś do tej pory na grach stworzonych w GM?