Nasze strony: gmclan.org gameonly.pl ps-plus.pl gameswithgold.pl n-switch.pl hmt.pl
Fastbar
Powrót do strony głównej
Trzymaj pliki na gmclan.org!
Game Maker w pytaniach i odpowiedziach!
Polska dokumentacja
Tabela wyników ligi 24
Pobierz GM
Akademia GMCLANu
Kategorie bazy artykułów
Artykuły -> Kąciki programowania -> Algorytmy i struktury danych
Treść artykułu
Wstep do algorytmow
autor: Choosen (13.06.04) | czas czytania: 3 minuty, 18 sekund
     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...
głosów: 2 | ocena: 9.00 oceń zasób | dodał: Ranmus
Komentarze
stron: 1

1


av

gnysek (19:49, 2.07.2004)

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

av

lion (16:51, 27.07.2004)

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

av

Marmot (22:39, 31.07.2004)

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

stron: 1

1



Dodaj komentarz:
Treść:
Menu
Panel użytkownika
Jesteś niezalogowany!

Nie masz konta? Zarejestruj się
Użytkownicy on-line
17 użytkownik(ów) aktywny(ch) przez ostatnie 15 minut:
gości: 17, userów: 0, ukrytych: 0
Użytkownicy na czacie discord
Shoutbox
UzjelUzjel (20:00, 2.07.22):
Zrobiłem test i działa naprawdę spoko, można wydać coś małego na GXa
gnysekgnysek (19:40, 30.06.22):
Polecam newsa o multiplayerze, fajny przykład jak robić sterowanie w grze w betach GM 2022.6+ (i zapewne w GM 2022.8 już normalnie)
ChellChell (11:14, 29.06.22):
słyszałem już o ludziach biorących kredyty na drugą połówkę, ale o subskrybujących GMa na ich kartę pierwsze słyszę
gnysekgnysek (9:14, 28.06.22):
A nie masz jakiegoś 3D secure czy coś, którego może Stripe nie obsługuje?
IgnatusIgnatus (20:14, 26.06.22):
Hmm coś nie tak z kartą (co dziwne bo są mam na niej inne, działające subskrypcje), na żony zadziałało XD
IgnatusIgnatus (11:41, 26.06.22):
Hmm, Jak mam zapłacić za subskrypcję GM? Polska nie jest obsługiwana? Odrzuca kartę i Gpay..
ThreefThreef (19:08, 25.06.22):
Zmienna keyboard_string zawiera wszystkie klawisze jakie wciśnięto. Możesz ją sobie wyzerować przed wpisywaniem keyboard_string = ""
IgnatusIgnatus (18:03, 25.06.22):
Jak w najprostszy sposób zapisać wpisany z klawiatury tekst jako zmienną którą mogę potem z czymś porównać?
IgnatusIgnatus (21:42, 24.06.22):
Tak. Kwestia jest taka że poza GM nie umiem totalnie nic (a GM używałem 5 lat temu). Może ktoś wie jak się do tego zabrać w GM (w sensie tutoriali lub assetów do kupienia)
ChellChell (17:13, 24.06.22):
podejrzewam że dużo prościej byłoby Ci zrobić to po webowo
ChellChell (17:13, 24.06.22):
hej 👋 dobrze rozumiem że chcesz robić prostą aplikację przeglądarkową w GM?
IgnatusIgnatus (21:39, 23.06.22):
Hello! Mam małą misję. Potrzebuje stworzyć apkę na www która będzie otwierała obrazki po wpisaniu ich dwu-członowej nazwy. To będzie trudne w GM? z 5 lat go nie ruszałem ;p
AdriannAdriann (19:34, 21.06.22):
o, naprawili
gnysekgnysek (16:00, 21.06.22):
Help > Report bug Samo sie nie naprawi Ale dzisiejsza beta ma jakiś fix na Spine.
AdriannAdriann (17:50, 20.06.22):
w sumie nawet nie sprawdzałem gdzie się to zgłasza :o
gnysekgnysek (13:54, 20.06.22):
A zgłoszone?
AdriannAdriann (22:08, 14.06.22):
Ech! Spine dalej nie naprawione :<
HunterHunter (13:36, 8.06.22):
Pytanie do starych wyjadaczy jest jeszcze gdzieś dostępna gra MAGI od TeeGee ?
gnysekgnysek (11:25, 8.06.22):
Ja pamiętam, jak była funkcja draw_image_alpha i po 5-6 grafikach FPS spadał.
expexp (18:27, 7.06.22):
i uruchamiała się jedną sekundę
expexp (18:25, 7.06.22):
łezka w oku się kręci jak wspominam czasy kiedy nowa wersja GM wychodziła raz na x lat i było zero problemów
AdriannAdriann (14:32, 4.06.22):
No i gdzie te aktualizacje:| Popsuli i zostawili
gnysekgnysek (12:24, 30.05.22):
A mogli wydać we wtorek, to jeszcze byłby nadal maj...
gnysekgnysek (12:24, 30.05.22):
Obstawiam, że kolejny raz między ostatnią betą a wydaniem stabilnym dodali "jeszcze dwa małe fixy" i wszystko się sypnęło. Ze spine to jest potwierdzony już błąd.
BorekBorek (20:32, 27.05.22):
Oczywiście jest weekend, także wywalona kiełbasa Jedynie można wrócić do poprzedniej wersji i cieszyć się, że ta wersja akurat nie była wymyagana np. dla nowszych wersji Google API Już raz mnie tak załatwili...
BorekBorek (20:29, 27.05.22):
Ostatnie stable jest bardziej rozwalone niż beta. Większość użytkowników nie może odpalić swoich projektów po wczorajszym stable Kocham GM Dobrze, że nie robiłem aktualizacji...
AdriannAdriann (11:23, 27.05.22):
I postacie ze spine zaczęły dziwnie się zachowywać(nie ruszałem w nich nic poza aktualizacjami na bieżąco) A dziwnie znaczy grafiki na różnych layerach często się nie przełączają mimo że powinny
AdriannAdriann (11:22, 27.05.22):
Mam wrażenie że coś się popsuło po ostatnich aktualizacjach gma Bardzo często nie działa mi room_restart() tj raz odpalę grę i działa raz nie
gnysekgnysek (22:58, 11.05.22):
ale tam 39dll chyba też dział, tylko trzeba było dodać brakujące argumenty z numerem bufora (bo GMS nie umiał już ustawiać niezdefiniowanych zmiennych na 0).
SutikkuSutikku (18:34, 11.05.22):
tfu, gms w ogóle, nie gms2
SutikkuSutikku (18:34, 11.05.22):
jak nauczyłem się korzystać z 39dll, to gms2 wyszedł o i tyle z moich nauk
gnysekgnysek (23:29, 9.05.22):
Pisałem już, że przekompilowałem 39dll do x64 i działa w GMS2 ?
gnysekgnysek (21:28, 28.04.22):
Pusty WP - 30-40mb ramu na 1 request.
ChellChell (14:25, 27.04.22):
narzeczona troche bardziej oblatana w temacie mi powiedziala co tam moge poinstalowac i na co zwrocic uwage zeby to zabezpieczyc, ale wciaz smiech na sali
ChellChell (14:24, 27.04.22):
stawialem ostatnio jeden landing na wp dla klienta (wykonany przez jakiegos zewnetrznego kontraktora), w tydzien jakies boty pozmienialy podstrony
ChellChell (14:23, 27.04.22):
jasne, ze powinni zaorac - najnowszy WP ma "wsparcie beta" dla php 8 (ktory wyszedl poltora roku temu), gdzie 7.4 nie jest aktywnie wspierany od 4 miesiecy.
gnysekgnysek (12:56, 26.04.22):
Wordpressa powinni zaorać. Dziwię się, że nikt nie zrobił lżejszego odpowiednika.
ChellChell (11:01, 25.04.22):
aa, nawet nie zauwazylem ze to bylo 3 dni temu
AdriannAdriann (10:09, 25.04.22):
Dziękuje ale już kolega mi to ogarnął i wszystko śmiga :3
ChellChell (9:59, 25.04.22):
nie jestem na tyle kompetentny zeby sie zdzwaniac i to tlumaczyc, ale jak mi podrzucisz dostepy to moge Ci dzisiaj wieczorem to postawic
AdriannAdriann (15:39, 23.04.22):
O kuwa, na wishliście codziennie wpadało po +-5 a tu dzisiaj walnęło i zrobiło się 82 z 28!
AdriannAdriann (22:01, 22.04.22):
privie *
AdriannAdriann (22:01, 22.04.22):
Tak, właśnie problem że nie mam się do kogo zwrócić a to sporo informacji, najlepiej byłoby na provie
gnysekgnysek (21:59, 22.04.22):
Ciężko pomóc jak napiszesz "nie działa". Coś musi się dziać. Biała strona, domyślna strona .html na serwerze, itp.
AdriannAdriann (18:58, 22.04.22):
To nie za bardzo moja dziedzina i nie wiem czy powinienem zrobić coś jeszcze żeby odpalił się instalator
AdriannAdriann (18:57, 22.04.22):
Wziąłem masterneta z któego już kiedyś korzystałem. Tylko coś mi nie działa, dawno tego nie robiłem i nie wiem co może być nie tak. Zalogowałem się do serwera ftp wg danych które wysłali i wrzuciłem rozpakowane pliki wordpressa ale strona nie działa
ChellChell (16:23, 22.04.22):
cloudways fajne na wordpressa
gnysekgnysek (20:14, 20.04.22):
Jutro o 17:00 będzie stream o przyszłości GMa, nie wrzucam newsa, bo napiszę podsumowanie pod koniec po fakcie
gnysekgnysek (20:13, 20.04.22):
ja polecam dhosting
Ankieta
» Kiedy wyjdzie GameMaker 3.0?
Q1 2022
Q2 2022
Q3 2022
Q4 2022
2023 albo i później

GMCLAN to serwis o programie Game Maker i nie tylko.
[ Polityka prywatności ]
Copyright © 2002-2022. GMCLAN.ORG
Wszelkie prawa zastrzeżone. Kopiowanie materiałów bez zgody redakcji zabronione!
© 2002-2017 Ranmus, © 2017-2022 {=|=} fable_inside();

[ Czas generowania strony: 0.53644 sekund ] [ Liczba zapytań MySQL: 13 ]