Autor Wątek: Algorytmy - podstawowe pytanie czym one są ?  (Przeczytany 2587 razy)

Offline tomaszwir

  • Użytkownik

# Styczeń 08, 2013, 12:44:58
Witam!

Mam takie banalne pytanie odnośnie samych algorytmów, jak wiadomo jest to bardzo ważna rzecz w programowaniu ale co to jest ? Proszę się krzywo nie patrzeć w tym momencie ale jakoś nie potrafię sobie wyobrazić np przedmiotu w szkole algorytmika czy samej znajomości algorytmów. Polega to na tym że są pewne algorytmy które trzeba znać i wiedzieć kiedy użyć ? Nie jestem początkującym jeżeli chodzi o programowanie ani kimś zaawansowanym trochę programów już napisałem ale tylko na własny użytek, nigdzie w zawodzie nie pracowałem a podobno są pytania na rozmowach kwalifikacyjnych odnośnie algorytmów. Póki co to ja to sobie wyobrażam tak: jest jakiś problem, program musi odpowiednio reagować na odpowiednie wartości np otrzymywanych zmiennych no to się pisze odpowiedni kawałek kodu np instrukcjami warunkowymi
« Ostatnia zmiana: Luty 19, 2013, 23:13:10 wysłana przez Netrix »

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline Avaj

  • Użytkownik

  • +1
# Styczeń 08, 2013, 12:56:14
Ja bym powiedział, że są dwa podejścia do algorytmów, akademickie i praktyczne. Akademickie to bardziej się skupia na dowodzeniu poprawności algorytmów, to się przydaje jak chcesz własne wymyślać, w praktycznym podejściu korzystasz z już gotowych i chodzi o to, żeby wiedzieć jaki zastosować i kiedy. Przykładowo, chcesz posortować tablicę elementów. Możesz użyć sortowania bąbelkowego lub przez wybór, ale to głupota bo prawie zerowym kosztem implementacyjnym można zapuścić quicksorta/mergesorta lub coś w tym stylu. Ale to dzięki znajomości algorytmów wiesz, że bąbelkowe ma złożoność obliczeniową O(n^2) a taki mergesort ma O(n log n).
Inny przykład - szukanie drogi. Ktoś kto nie zna się na algorytmach, może próbować BFSem szukać drogi. Znajdzie tą drogę ale bardzo nieefektywnie. Lepiej zastosować Djikstrę albo A*, który jest dużo szybszy bo od razu ciągnie go do celu zamiast równomiernie obchodzić teren.

Aczkolwiek z algorytmami też trzeba uważać. Zawsze mówi się, że wektor jest zły bo dużo alokuje się przy rozszerzaniu a jak się często usuwa/dodaje elementy to lepiej użyć listę. Jednak jak przychodzi co do czego, wektor się cwanie powiększa (podwaja swój rozmiar) i jest jednym blokiem pamięci a lista jest rozsiana po całej pamięci, więc wektor może wyjść szybszy przez różnego rodzaju techniki cache'owania procesora.

Offline shinosuke

  • Użytkownik

# Styczeń 08, 2013, 15:32:30
Algorytm - to najprościej rzecz ujmując przepis na zrobienie czegoś (rozwiązanie pewnego problemu).
Tak jak już wspomniał Avaj podczas pisania różnych programów będziesz spotykał się z problemami, które są już ogólnie znane (jak posortowanie tablicy, znalezienie najkrótszej ścieżki w grafie, itd. itp.). W zależności od tego z czym będziesz miał konkretnie do czynienia (np. tablica liczb - całkowitych, rzeczywistych?, konkretne warunki, itp.) istnieje już do większości Twoich problemów gotowe rozwiązanie - "przepis" lub inaczej algorytm, który rozwiąże Twój problem poprawnie i najszybciej jak się da.
Takie zajęcia najczęściej są na wyższej uczelni i najczęściej występują w połączeniu ze strukturami danych. Na takich zajęciach będziesz poznawać najpopularniejsze struktury danych (rzeczy które w Twoim kodzie programu będą przechowywać Twoje zmienne (tutaj troszkę upraszczam ;) ) i tworzyć logiczne zależności między nimi (to jest najistotniejsze)) takie jak: tablice, listy, drzewa, kopce, itp. itd. a także algorytmy działające na tych dobrze znanych strukturach. Czyli właśnie takie przepisy jak najszybciej osiągnąć jakiś konkretny cel na takiej strukturze danych. Dodatkowo prawdopodobnie poznasz takie biblioteki (i nauczysz się ich optymalnie używać) jak np. STL, która zawiera najczęściej potrzebne i używane struktury danych i algorytmy najczęściej w sposób najszybszy rozwiązujące pewne problemy (istota złożoności) po to aby nie wynajdywać koła na nowo i zaoszczędzić swój czas na inne rzeczy podczas programowania :) Dzięki temu wszystkiemu Twoje programy będą szybsze, stabilniejsze, łatwiej rozwijalne i zajmowały mniej miejsca w cały czas cennej pamięci.

Offline nembutal

  • Użytkownik

# Styczeń 08, 2013, 15:49:20
Dodajmy, że zarówno w szkole jak i na rozmowie kwalifikacyjnej, będą od ciebie wymagać znajomości najpopularniejszych algorytmów - czyli tych, które zostały już zaimplementowane w dziesiątkach popularnych bibliotek i są szczegółowo opisane w książkach, na forach i na blogach. (co znaczy mniej więcej tyle, że nikt nie musi ich implementować z pamięci).
Poza tym, IMHO, znajomość 50 popularnych algorytmów nie sprawi, że będziesz w stanie samodzielnie napisać poprawny i optymalny algorytm do 51-ego problemu.
« Ostatnia zmiana: Styczeń 08, 2013, 15:54:51 wysłana przez nembutal »

Offline Xion

  • Redaktor
    • xion.log

  • +1
# Styczeń 08, 2013, 21:25:15
Zacznijmy od tego, że algorytmy są rozumiane na dwa sposoby.

Pierwszy jest ogólniejszy i dotyczy po prostu sposobu rozwiązania jakiegoś problemu, jakkolwiek drobny by on nie był. Obliczenie koordynatów pozwalających wyśrodkować okno na ekranie to też algorytm, tyle że składający się z dwóch linii.
W praktyce jeśli usłyszysz termin "algorytm" w dyskusjach programistów, będzie to dotyczyło sposobu realizacji jakiegoś zadania, często specyficznego dla danego projektu. Algorytm może być treścią jednej funkcji, składać z wielu funkcji, modułów i/lub klas.

Drugie znaczenie jest węższe i, z tego co zdążyłem zauważyć, używane raczej przez studentów / mniej doświadczonych programistów. Dotyczy ono pewnego zestawu "klasycznych" algorytmów służących do rozwiązywania "nieśmiertelnych" problemów: sortowania, przeszukiwania grafów, pewnych operacji graficznych, teorioliczbowych, etc.
Nie jestem pewien, ale wydaje mi się, że kluczową cechą tego sposobu rozumienia algorytmów jest to, że są one wyizolowane od reszty programu. Często są więc w jakiejś zewnętrznej bibliotece (np. standardowej dla danego języka), rzadziej są wydzieloną funkcją albo modułem w samym programie. W każdym razie taki "algorytm" to bardziej czarna skrzynka która tylko przyjmuje wejście i wypluwa ustalone wyjście.

Oczywiście w rzeczywistych systemach takie podejście się nie sprawdza, bo niemal nigdy nie da się książkowego algorytmu tak po prostu zastosować do każdego nietrywialnego problemu. Zazwyczaj np. dane wejściowe będą zbyt duże albo nieznane z góry; część rezultatów trzeba będzie cache'ować; inną część trzeba będzie wykonać współbieżnie, itd. Krótko mówiąc, rzekomo zamknięte skrzynki zaczynają się "rozłazić" po całym programie.

@OP: Wydaje mi się, że im prędzej porzucisz ograniczone (drugie) rozumienie algorytmów i przerzucisz się na to pierwsze, tym lepiej dla rozwoju twoich umiejętności jako programisty.

Offline msm

  • Użytkownik

# Styczeń 13, 2013, 03:15:57
Trochę spóźniona odpowiedź, ale może ktoś skorzysta...

Cytat: Avaj
Ktoś kto nie zna się na algorytmach, może próbować BFSem szukać drogi. Znajdzie tą drogę ale bardzo nieefektywnie. Lepiej zastosować Djikstrę albo A*, który jest dużo szybszy bo od razu ciągnie go do celu zamiast równomiernie obchodzić teren.
Niestety, nieprawda - BFS ( O(n) ) jest szybszy od Dijkstry ( O(|E|+|V|·log|V|), oraz ma znacznie większą stałą ) i może być szybszy od A* (dla złej heurystyki wykładniczy (!), dla sensownej można udowodnić wielomianowość ale dokładna analiza zawsze jest trudna - jeśli można stworzyć dobrą heurystykę to jest szybszy, ale nie istnieje (oczywiście, to by było zbyt piękne ;) ) sensowna heurystyka dla dowolnego grafu).
Aczkolwiek rację masz w tym że faktycznie istnieją szybsze algorytmy uzależniające czas działania od faktycznej odległości w krawędziach między wierzchołkami (za pomocą techniki Man In The Middle)

Cytat: Awaj
Aczkolwiek z algorytmami też trzeba uważać. Zawsze mówi się, że wektor jest zły bo dużo alokuje się przy rozszerzaniu a jak się często usuwa/dodaje elementy to lepiej użyć listę. Jednak jak przychodzi co do czego, wektor się cwanie powiększa (podwaja swój rozmiar) i jest jednym blokiem pamięci a lista jest rozsiana po całej pamięci, więc wektor może wyjść szybszy przez różnego rodzaju techniki cache'owania procesora.
Przede wszystkim wektor ma O(n) usuwania elementów ze środka a lista O(1) - za to wektor ma dostęp w czasie stałym do dowolnego elementu, a lista musi pesymistycznie wykonywać liniową ilość operacji.
Zawsze można korzystać z jakiegoś drzewa które mają log(n) dla tych działań.
Ale fakt jest faktem, dobrym domyślnym wyborem jest wektor.
Przepraszam, już się nie czepiam

Cytuj
Dodajmy, że zarówno w szkole jak i na rozmowie kwalifikacyjnej, będą od ciebie wymagać znajomości najpopularniejszych algorytmów - czyli tych, które zostały już zaimplementowane w dziesiątkach popularnych bibliotek i są szczegółowo opisane w książkach, na forach i na blogach. (co znaczy mniej więcej tyle, że nikt nie musi ich implementować z pamięci).
Poza tym, IMHO, znajomość 50 popularnych algorytmów nie sprawi, że będziesz w stanie samodzielnie napisać poprawny i optymalny algorytm do 51-ego problemu.
Ha, bardzo trafnie ;].
Na pocieszenie powiem, że na szczęście nie w każdej firmie wymagają znajomości algorytmów (gorzej kiedy na rozmowie kwalifikacyjnej zadają zagadki logiczne - tak jakby umiejętność szacowania odległości od ziemi do marsa za pomocą kredki i zużytej żarówki stanowiła o tym czy umiem programować) - szczególnie niewielkie firmy podchodzą do tego normalnie (ale może to tylko moja opinia).

No dobrze, to teraz moja odpowiedź na temat:
Formalna definicja algorytmu to `Jakaś czarna skrzynka która coś tam przyjmuje, coś tam sobie mieli i wypluwa wynik spełniający jakieś tam założenia` (może i formalna definicja, ale niezbyt formalnie napisana).
Dla przykładu, mnie kiedyś uczono na przykładzie pieczenia ciasta - masz mąkę, mleko i co tam jeszcze (warunki początkowe), mieszasz, wrzucasz do pieca (operacje) i wyciągasz coś co się nadaje do zjedzenia (zazwyczaj).

Jeśli chodzi o programowanie (bo to nas przecież interesuje), jakiś `algorytm` realizuje każda funkcja programu (np. `algorytm rysowania gracza`, `algorytm kolizji wielokątów`, `algorytm sterowania`). To jak najbardziej prawda, ale zazwyczaj jeśli już ktoś zaczyna o algorytmach to ma na myśli:
(1) działanie ogólne, nie specyficzne dla jednego konkretnego programu i/lub
(2) działanie w którym istotny jest czas wykonania (tzn. żeby był jak najmniejszy)

W praktyce wadą algorytmów książkowych jest to, że wszystkie są już przez kogoś zaimplementowane lepiej niż Ty byś to zrobił (przynajmniej bez długiego czytania i nauki) - prawie zawsze lepiej skorzystać z gotowca niż wymyślać koło samodzielnie.
Znajomość klasycznych algorytmów przydaje się na pewno na OI, ale w pracy (no, chyba że będziesz algorytmikiem) będą Ci płacić raczej za tworzenie nowych rozwiązań a nie wymyślanie koła na nowo ;).

Za to na pewno warto przynajmniej rozumieć czym jest złożoność obliczeniowa, może uratuje Cię to od zostania kolejną osobą która przyśpieszanie programu zaczyna od zamiany x = y * 2 na x = y << 1 żart, ale zdarza się niestety, a i jeśli będziesz znał kilka prostych algorytmów to Twój umysł na tym tylko zyska ;].
(edit: dla jasności, nie mam nic przeciwko OI, wbrew temu co niektórzy czasami piszą, nie polega ona na przepisywaniu algorytmów bezmyślnie z książki, tylko na umiejętności dostrzeżenia natury problemu, wymyślenia wydajnego rozwiązania i czasami praktycznego zastosowania jakiegoś klasycznego algorytmu - czyli bardzo dobrze zorganizowane)

PS. Takim moim skromnym zdaniem, wzorce projektowe to też algorytmy, tylko przeniesione z płaszczyzny linijek kodu na płaszczyznę klas. Jako że nikt na razie nie wymyślił języka obiektowego pozwalającego tworzyć wystarczająco silne abstrakcje (jakimi dla kodu są szablony na przykład) na poziomie systemu typów pozwalającego zamknąć dowolny wzorzec projektowy do czarnej skrzynki, jeśli chce się je stosować, trzeba je pisać zawsze od zera ;].
Co śmieszne, istnieją frameworki enkapsułujące `wzorce architektoniczne` które są jeszcze bardziej abstrakcyjne (dotyczą architektury programu).
Nie wiem czy ten akapit jest chociaż trochę zrozumiały, trochę już późno i mi się słowa plączą...
« Ostatnia zmiana: Styczeń 13, 2013, 03:24:43 wysłana przez msm »

Offline Xion

  • Redaktor
    • xion.log

# Styczeń 13, 2013, 17:29:59
Cytuj
Jako że nikt na razie nie wymyślił języka obiektowego pozwalającego tworzyć wystarczająco silne abstrakcje (jakimi dla kodu są szablony na przykład) na poziomie systemu typów pozwalającego zamknąć dowolny wzorzec projektowy do czarnej skrzynki, jeśli chce się je stosować, trzeba je pisać zawsze od zera ;]
Zależy od języka i zależy od konkretnego wzorca. Wiele wzorców jest po prostu wbudowanych w niektóre języki, jak np. iterator czy singleton. Niektóre można zaimplementować raz i korzystać z nich potem jak z czarnej skrzynki. Część trzeba aczkolwiek implementować za każdym razem od nowa (np. singleton w Javie).

Cytuj
Co śmieszne, istnieją frameworki enkapsułujące `wzorce architektoniczne` które są jeszcze bardziej abstrakcyjne (dotyczą architektury programu).
Masz na myśli wynalazki typu MVC, MVP, MVVM itp. czy coś jeszcze innego?

Offline Avaj

  • Użytkownik

# Styczeń 13, 2013, 17:37:16
Przede wszystkim wektor ma O(n) usuwania elementów ze środka a lista O(1) - za to wektor ma dostęp w czasie stałym do dowolnego elementu, a lista musi pesymistycznie wykonywać liniową ilość operacji.
Jak nie obchodzi nas kolejność elementów można zamienić element usuwany z ostatnim i skrócić tablicę o 1 i wtedy jest w czasie stałym.