Dnia 16.10.2012 Michoo <m...@v...pl> napisał/a:
> On 16.10.2012 04:12, Baranosiu wrote:
>> Dnia 15.10.2012 Michoo<m...@v...pl> napisał/a:
>>
>> Dochodzi jeszcze kwestia tego co rozumie się przez zbiór "czynnoiści
>> elementarnych"
>
> Ale one nie muszą być "elementarne". W algorytmie znajdowania przecięci
> zbiorów może być "posortuj oba zbiory w ciągi rosnące" bez
> wyspecyfikowania metody, nie trzeba wplatać logiki sortowania do środka.

Dla zbiorów dyskretnych (a ściślej dla dyskretnych ich reprezentacji w
maszynie) to jak najbardziej algorytm zadziała, ale nie wszystkie
zbiory są przeliczalne (a więc nie zawsze dają się posortować) i... z
algorytmu "dupa" :D Dziedzina KAŻDEGO algorytmu to nie tylko dane na
jakich on działa, ale także zbiór operacji jakie musi być w stanie
wykonać maszyna inaczej się nie da (spróbuj znaleźć przecięcie
zbiorów, jeśli maszyną jest na przykład kucharz, nie da się,
choć... kucharz może zrealizować algorytm sporządzenia zupy
pomidorowej :D).



>
>> , bo na przykład kiedyś konstruowano komputery
>> analogowe, które jedną "czynnością elementarną" przechodziły przez
>> nieskończoną liczbę stanów i algorytm działający na maszynie
>> analogowej może już nie być algorytmem na maszynie dyskretnej.
>
> Dlatego napisałem - "na pewnej abstrakcyjnej maszynie".

Na "abstrakcyjnej" czyli na żadnej :D Zwykle w informatyce przyjmuje
się w domyśle maszyny Turinga, ale samo pojęcie algorytmu nie musi ich
dotyczyć :D


>> Tak
>> więc definicja "abstrakcyjnej maszyny" jest też częścią algorytmu a
>> nie tylko same czynności
>
> Mamy maszynę, więc definiujemy w oparciu o nią algorytm. W tym sensie
> definicja maszyny jest częścią algorytmu. Nie wciągałbym jednak
> szczegółów maszyny do samego algorytmu.

Wszystkie współczesne komputery cyfrowe (łącznie z kwantowymi) to
maszyny Turinga, więc rozróżnienia się nie robi, w tym sensie można
pominąć szczegóły maszyny, ale samo pojęcie algorytmu to coś więcej
niż "proces wykonywany przez maszynę cyfrową".


>> Mnie na studiach uczono (a były to
>> lata 90-te), że tak na prawdę nie ma jednej uniwersalnej matematycznej
>> definicji czym jest algorytm, dlatego w różnych kontekstach przyjmuje
>> się różne "modele" tego pojęcia.
>
> Czy nie ma uniwersalnej to bym się kłócił, ale jak to zwykle im coś
> bardziej uniwersalne tym ogólniejsze. Istnieją więc też "definicje
> szczegółowe" np. "algorytm na NDTM", "algorytm na DNA", "algorytm na
> studencie".

Ok, są, ale to są tylko konkretne modele. Można na przykład
zdefiniować pojęcie algorytmu w oparciu o maszyny Turinga ale... takie
pojęcie algorytmu już nie będzie pasowało do "przepisu na zrobienie
pomidorowej". Ogólnej definicji algorytmu (w sensie matematycznym) nie
ma, a w informatyce przyjmuje się pewien "podzbiór" tego pojęcia w
kontekście określonej klasy maszyn, aby się na tym matematykę dało
uprawiać :D No ale to już wykracza poza główny temat wątku :D

do góry

Użytkownik "Michoo" napisał w wiadomości grup
dyskusyjnych:k5jc44$lnn$...@m...internetia.pl...

>Praca rozrusznika serca nie daje się opisać algorytmem. Praca rozrusznika
>składa się z:
>- odczytu parametrów
>- algorytmu obliczenie parametrów pochodnych
>- algorytmu decyzyjnego "czy kopnąć serce"
>
> Wykonywanych w nieskończonej pętli.

Właśnie opisałeś "algorytm rozrusznika". Gratulacje.

Skończoność w algorytmach dotyczy zapisu algorytmu (tj. musi się dać
zapisać). Ograniczenie czasu do skończonego (tj. z jawnym ograniczeniem, bo
wiadomo że Wszechświat kiedyś tam coś) było - i być może jest - potrzebne
jedynie dla udowodnienia obliczalności. Nie każdy jednak algorytm służy do
numeryki.

>ogólnej" podczas gdy jest to czysta matematyka. Z informatyki należy pobrać
>ograniczenia rzeczywistej maszyny (skończona pamięć, koszt

Algorytmy tworzono circa 2000 i więcej lat temu. Komputerów nie było.

>> Dlatego lepiej określa "czym jest algorytm" definicja: "efektywna metoda
>> osiągnięcia celu, przedstawiona jako skończony zapis dobrze określonych
>> instrukcji".

>Przeraźliwie ogólne. Algorytmem sortowania byłoby "wynajęcie programisty w
>Indiach".

Jeżeli spodziewasz się, że będzie to: efektywne i zapewni osiągnięcie celu
(bo jak widać daje się zapisać w postaci skończonej i zrozumiałej) - to ok,
to jest BARDZO DOBRY ALGORYTM.

(Nota bene, jest to często naprawdę dobre rozwiązanie - tj. zlecić komuś
innemu, aby coś dla nas zrobił.)

No, może być kłopotliwe... jeżeli nie rozumiesz czegoś z tego co sam
napisałeś, np.: "wynajęcie programisty w Indiach". Wiesz jak to zrobić?
Wynajmowałeś kiedyś już? Jesteś w stanie to zrobić? Jeżeli nie - to ten
fragment (jaki napisałeś) nie jest "dobrze określoną instrukcją" lecz
mniemanologią niestosowaną. Bo nie potrafisz tej instrukcji wykonać. Więc
dla ciebie to nie-instrukcja.

Odwrotnie, jeżeli np. regularnie pośredniczysz w zbieraniu zamówień na
programy i kontaktujesz się z programistami w Indiach - to jest to "dobrze
określona instrukcja" (np. spowoduje, że wyślesz e-mail z opisem problemu do
Indii, zaczniesz negocjować stawki i terminy) - oraz, jednocześnie, jest to
metoda efektywna - w znaczeniu "dająca, gdy tego potrzeba, spodziewane,
poprawne rezultaty i to w akceptowalnym czasie".

do góry

On 16.10.2012 13:07, slawek wrote:
> Użytkownik "Michoo" napisał w wiadomości grup
> dyskusyjnych:k5jc44$lnn$...@m...internetia.pl...
>
>> Praca rozrusznika serca nie daje się opisać algorytmem. Praca
>> rozrusznika składa się z:
>> - odczytu parametrów
>> - algorytmu obliczenie parametrów pochodnych
>> - algorytmu decyzyjnego "czy kopnąć serce"
>>
>> Wykonywanych w nieskończonej pętli.
>
> Właśnie opisałeś "algorytm rozrusznika". Gratulacje.
>
> Skończoność w algorytmach dotyczy zapisu algorytmu (tj. musi się dać
> zapisać). Ograniczenie czasu do skończonego (tj. z jawnym ograniczeniem,
> bo wiadomo że Wszechświat kiedyś tam coś) było - i być może jest -
> potrzebne jedynie dla udowodnienia obliczalności. Nie każdy jednak
> algorytm służy do numeryki.

Algorytm gotowania zupy jest skończony i z numeryką nie ma nic
wspólnego. Ten w sumie też jest skończony - do końca życia pacjenta ;)

A poważniej - mnie uczono, że właśnie algorytm ma w skończonym czasie
dać określony wynik. Więc jeżeli czas jest nieskończony albo wynik
niedeterministyczny to nie mamy do czynienia z algorytmem. W myśl tego
był to opis/schemat pracy rozrusznika, ale nie algorytm.

I ma to sens praktyczny - interesuje nas jak się zachowa rozrusznik w
cyklu pracy, liczba cykli jest nieistotna dla problemu. Każdy
nieskończony (w pewnym przypadku) cykl pracy da się przeciąć i uzyskać
algorytm opisujący pracę zakończoną decyzją czy pracować dalej.

>
>> ogólnej" podczas gdy jest to czysta matematyka. Z informatyki należy
>> pobrać ograniczenia rzeczywistej maszyny (skończona pamięć, koszt
>
> Algorytmy tworzono circa 2000 i więcej lat temu. Komputerów nie było.

tmsidn


--
Pozdrawiam
Michoo

do góry

Dnia 16.10.2012 slawek <h...@s...pl> napisał/a:
> Użytkownik "Michoo" napisał w wiadomości grup
> dyskusyjnych:k5jc44$lnn$...@m...internetia.pl...
>
>>Praca rozrusznika serca nie daje się opisać algorytmem. Praca rozrusznika
>>składa się z:
>>- odczytu parametrów
>>- algorytmu obliczenie parametrów pochodnych
>>- algorytmu decyzyjnego "czy kopnąć serce"
>>
>> Wykonywanych w nieskończonej pętli.
>
> Właśnie opisałeś "algorytm rozrusznika". Gratulacje.
>
> Skończoność w algorytmach dotyczy zapisu algorytmu (tj. musi się dać
> zapisać). Ograniczenie czasu do skończonego (tj. z jawnym ograniczeniem, bo
> wiadomo że Wszechświat kiedyś tam coś) było - i być może jest - potrzebne
> jedynie dla udowodnienia obliczalności. Nie każdy jednak algorytm służy do
> numeryki.


Skończoność tyczy się nie zapisu (zawsze można się umówić, że ciąg
n1,n2,n3.... zapiszę symbolem nx i już z nieskończoności zrobiłem
skończoność :D) tylko właśnie skończonej pesymistycznej złożoności (a
więc istnienia warunku stopu). Aby tego typu "rozrusznik serca" badać
pojęciem algorytmu, to trzeba przyjąć, że każde uderzenie serca, to
pojedyńcze wykonanie trzech wspomnianych czynności "bez pętli"
(i wtedy każde "kopnięcie serca" to odpalenie algorytmu na innych
danych). Algorytm jest czymś w rodzaju dowodu twierdzenia, pokazuje
jak z danych wejściowych (założenie twierdzenia) uzyskać dane
wyjściowe (teza) przy użyciu środków udostępnianych przez maszynę
(przyjęta aksjomatyka). Dowód twierdzenia zawsze ma skończoną liczbę
kroków (nawet jeśli zastosujemy zasadę indukcji matematycznej) tak
samo jak algorytm ma zawsze skończoną liczbę operacji (nawet jeśli
działa na nieskończonym zbiorze danych wejściowych).
To że jakieś działanie da się opisać "swoimi słowami" jeszcze nie
oznacza, że taki opis to algorytm (tak samo jak nie każde
"uzasadnienie słowne" jest dowodem twierdzenia matematycznego), czasem
trzeba nieco "dopasować" opis do teorii :D

do góry

Dnia Tue, 16 Oct 2012 13:52:29 +0200, Michoo napisal:

> A poważniej - mnie uczono, że właśnie algorytm ma w skończonym czasie dać
> określony wynik. Więc jeżeli czas jest nieskończony albo wynik
> niedeterministyczny to nie mamy do czynienia z algorytmem. W myśl tego był
> to opis/schemat pracy rozrusznika, ale nie algorytm.

A czy potrafiłbyś opisać jak to się ma do algorytmów używających random?

Oczywiście takie MC używa random, ale ma to tylko częściowy wpływ na czas
algorytmu, bo co najwyżej obiera inne określonej długości ścieżki. Natomiast
nie wiem jak to się ma do algorytmów w ogólności, w końcu random może wpływać
nie tylko na to "kiedy algorytm się zakończy" (uczenie durnej sieci neuronowej
aż błąd będzie mniejszy-niż może się nie skończyć - kiepski algorytm ale
wciąż algorytm), ale teoretycznie random może wpływać na same elementy
algorytmu i przez to definiowalność czy i kiedy się skończy zależy - hmm,
od random, o ile inne prawa nie określają jakieś konwergencji.

--
Edek

do góry

On 16.10.2012 14:17, Edek Pienkowski wrote:
> Dnia Tue, 16 Oct 2012 13:52:29 +0200, Michoo napisal:
>
>> A poważniej - mnie uczono, że właśnie algorytm ma w skończonym czasie dać
>> określony wynik. Więc jeżeli czas jest nieskończony albo wynik
>> niedeterministyczny to nie mamy do czynienia z algorytmem. W myśl tego był
>> to opis/schemat pracy rozrusznika, ale nie algorytm.
>
> A czy potrafiłbyś opisać jak to się ma do algorytmów używających random?
>
> Oczywiście takie MC używa random, ale ma to tylko częściowy wpływ na czas
> algorytmu, bo co najwyżej obiera inne określonej długości ścieżki. Natomiast
> nie wiem jak to się ma do algorytmów w ogólności, w końcu random może wpływać
> nie tylko na to "kiedy algorytm się zakończy" (uczenie durnej sieci neuronowej
> aż błąd będzie mniejszy-niż może się nie skończyć - kiepski algorytm ale
> wciąż algorytm), ale teoretycznie random może wpływać na same elementy
> algorytmu i przez to definiowalność czy i kiedy się skończy zależy - hmm,
> od random, o ile inne prawa nie określają jakieś konwergencji.
>
Oidp (to było jednak kilka lat temu) to wyglądało to tak:
- jak wynik jest niedeterministyczny to nie jest to algorytm
- jak wynik jest deterministyczny, ale mamy nałożone na niego pewne
ograniczenia to jest to algorytm probabilistyczny

--
Pozdrawiam
Michoo

do góry

W dniu 2012-10-16 14:20, Michoo pisze:
> On 16.10.2012 14:17, Edek Pienkowski wrote:

>>
> Oidp (to było jednak kilka lat temu) to wyglądało to tak:
> - jak wynik jest niedeterministyczny to nie jest to algorytm
> - jak wynik jest deterministyczny, ale mamy nałożone na niego pewne
> ograniczenia to jest to algorytm probabilistyczny

Taż tak zawsze myślałem. Mamy algorytmu randomizowane(probabilistyczne),
np qsort, a takie monte carlo to metoda, nie algorytm.

Ale... gdzie wtedy wstawić test Millera-Rabina?
Niby do algorytmów, ale przecież może dać zły wynik.

Do tego właśnie znalazłem to:
http://en.wikipedia.org/wiki/Monte_Carlo_algorithm

"In computing, a Monte Carlo algorithm is a randomized algorithm
whose running time is deterministic, but whose output may be incorrect
with a certain (typically small) probability."

Wynik niedeterministyczny, a jednak algorytm (probabilistyczny).


Zresztą, czy to nie taksonomia i zbieranie znaczków;-)

pzdr
bartekltg

do góry

W dniu 2012-10-16 09:09, kenobi pisze:
> (tak z ciekawosci chodzi
> mi o dowiedzenie sie czym sie zajmujesz (bez
> skrecania w strone danych personalnych))

Równania różniczkowe cząstkowe.

Do tego trochę fizyki, trochę numeryki.

pzdr
bartekltg

do góry

Dnia Tue, 16 Oct 2012 14:20:29 +0200, Michoo napisal:

> On 16.10.2012 14:17, Edek Pienkowski wrote:
>> Dnia Tue, 16 Oct 2012 13:52:29 +0200, Michoo napisal:
>>
>>> A poważniej - mnie uczono, że właśnie algorytm ma w skończonym czasie dać
>>> określony wynik. Więc jeżeli czas jest nieskończony albo wynik
>>> niedeterministyczny to nie mamy do czynienia z algorytmem. W myśl tego był
>>> to opis/schemat pracy rozrusznika, ale nie algorytm.
>>
>> A czy potrafiłbyś opisać jak to się ma do algorytmów używających random?
>>
>> Oczywiście takie MC używa random, ale ma to tylko częściowy wpływ na czas
>> algorytmu, bo co najwyżej obiera inne określonej długości ścieżki. Natomiast
>> nie wiem jak to się ma do algorytmów w ogólności, w końcu random może wpływać
>> nie tylko na to "kiedy algorytm się zakończy" (uczenie durnej sieci neuronowej
>> aż błąd będzie mniejszy-niż może się nie skończyć - kiepski algorytm ale
>> wciąż algorytm), ale teoretycznie random może wpływać na same elementy
>> algorytmu i przez to definiowalność czy i kiedy się skończy zależy - hmm,
>> od random, o ile inne prawa nie określają jakieś konwergencji.
>>
> Oidp (to było jednak kilka lat temu) to wyglądało to tak:
> - jak wynik jest niedeterministyczny to nie jest to algorytm
> - jak wynik jest deterministyczny, ale mamy nałożone na niego pewne
> ograniczenia to jest to algorytm probabilistyczny

- w pozostałych przypadkach: nie tylko wykładowca, ale sam najwyższy się
w tym pogubił

--
Edek

do góry

W dniu 2012-10-16 09:39, Edek Pienkowski pisze:
> Dnia Mon, 15 Oct 2012 22:54:07 +0200, bartekltg napisal:


>> Tak, ten konkursik sprawdza zdolności matematyczne/algorytmiczne,
>> nie jakość kodu. No i?
>
> Mi te zadanka pachną olimpiadą. Czy to dobrze czy źle nie oceniam,

W sumie, nie tylko klimat identyczny, ale i wejście/wyjście.
Ale to chyba międzynarodowy standard w tego typu zabawach.

> ale oprócz wymienionych powyżej sprawdzają dwie kluczowe: umiejętność
> zrozumienia istoty zadania pomijając błędy w definicjach oraz właśnie
> "eliminację zagmatwania", ponownie w celu zrozumienia istoty zadania.

Dostajesz bajkę o szpiegach i królewnie, a nie
'napisz algorytm taki a taki':)

Sprawdzają coś jeszcze. Umiejętność szybkiego poradzenia sobie
z problemem. Rano sobie drukniesz, po drodze do roboty przeczytasz,
w czasie obiadu pomyślisz i wieczorkiem można się godzinkę
w implementacje pobawić.
Mało kto ma czas siedzieć cały dzień:]


> IOW wyglądają na trudniejsze niż są dzięki zagmatwaniau.

Zerknąłem, co tam wysyłałem w zeszłym roku. Sporo rozwiązań
to <100 linii. Oczywiście, tych łatwych:)

pzdr
bartekltg

do góry