Witam

Chciałem zapytać jaki jest dzisiejszy stan wiedzy na temat programów
samo-modyfikujących się. Chodzi mi o coś "więcej" niż trywialne
doklejenie wirusa, albo przekopiowanie jednej procedury w miejsce
drugiej.

Np. dane mogą stanowić jakiś problem dla którego najlepsze znane algorytmy
dają rozwiązanie np. w czasie wielomianowym wysokiego stopnia X.
Jednak po zastosowaniu algorytmu samo-modyfikującego, w oparciu o analizę
danych, ciąg instrukcji algorytmu zostanie tak przebudowany (raz lub
iteracyjnie wiele razy), aby istotnie zmniejszyć stopień wielomianu X.

Np. dzięki technikom programowania dynamicznego można zapamiętać
rozwiązania częściowe, następnie przez łączenie rozwiązań częściowych
można uzyskać rozwiązanie całego problemu w znacznie lepszym czasie.
Czy są znane jakieś algorytmy dla pewnych problemów które analogicznie
budują/modyfikują ciąg instrukcji zamiast rozwiązań częściowych i
dzięki temu też uzyskują lepszą złożoność.

Pozdrawiam










--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

Dnia 07.08.2009 Mariusz Marszałkowski <b...@W...gazeta.pl> napisał/a:

> Chciałem zapytać jaki jest dzisiejszy stan wiedzy na temat programów
> samo-modyfikujących się. Chodzi mi o coś "więcej" niż trywialne
> doklejenie wirusa, albo przekopiowanie jednej procedury w miejsce
> drugiej.

Na temat nietrywialnych zastosowań samomodyfikującego się kodu zobacz:
"Synthesis: An Efficient Implementation of Fundamental Operating System
Services", Henry Massalin, 1992 (Ph.D. dissertation).

--
Daniel 'Nathell' Janus, m...@n...korpus.pl, http://danieljanus.pl
Microsoft Windows is to computing as the Ottoman Empire was to late
nineteenth century politics: it covers a lot of territory, but
no-one takes it seriously anymore. [Robert Uhl, comp.lang.lisp]

do góry

On Fri, 7 Aug 2009 23:35:58 +0000 (UTC), "Mariusz Marszałkowski"
<b...@W...gazeta.pl> wrote:

>Witam
>
>Chciałem zapytać jaki jest dzisiejszy stan wiedzy na temat programów
>samo-modyfikujących się. Chodzi mi o coś "więcej" niż trywialne
>doklejenie wirusa, albo przekopiowanie jednej procedury w miejsce
>drugiej.
>

What is partial evaluation?

Partial evaluation creates a specialized version of a general program.
The specialized program may be much faster than the general one.
Let p be a program which takes two inputs d1 and d2. Ordinarily, the
application of p to (d1,d2) would be evaluated in one step:

Evaluate p with input (d1, d2), to produce the result res.

However, alternatively it may be evaluated in two steps:
(1) Partially evaluate p with input d1, to produce a new
program r.
(2) Evaluate r with input d2, to produce the result res.

The program r is a specialized version of p (for the particular value
d1 of the first input), and is called a residual program. The process
of producing r (in step 1) is called partial evaluation, or program
specialization. The benefit of partial evaluation is speed of
execution: the specialized program r is often much faster than the
general program p.

Ksiaka jes tdo sciagniecia ze strony autora

How to obtain a copy of the book
Download the full text in Postscript (2.3 MB) or in PDF (US letter)
(1.7 MB) or PDF (A4) (1.7 MB).

http://www.dina.dk/~sestoft/pebook/pebook.html

A.L.

P.S. Tamze, jednego z autorow powyzszej, doskonala ksiazka o
zlozonosci obliczeniowej

http://www.diku.dk/hjemmesider/ansatte/neil/comp2boo
k2007/book-whole.pdf

do góry

On Aug 8, 1:35 am, "Mariusz Marszałkowski"
<b...@W...gazeta.pl> wrote:

> Np. dane mogą stanowić jakiś problem dla którego najlepsze znane algorytmy
> dają rozwiązanie np. w czasie wielomianowym wysokiego stopnia X.
> Jednak po zastosowaniu algorytmu samo-modyfikującego, w oparciu o analizę
> danych, ciąg instrukcji algorytmu zostanie tak przebudowany (raz lub
> iteracyjnie wiele razy), aby istotnie zmniejszyć stopień wielomianu X.

Takich rzeczy nie ma. Samomodyfikacja może przyspieszyć o stały
czynnik, ale nigdy nie jest konieczna dla poprawy asymptotycznej
złożoności. Innymi słowy można zastąpić kompilator interpreterem.

do góry

dodam jeszcze że
- bywa, że system operacyjny umieszcza kod wykonywalny programu w
takim obszarze pamięci, którego się nie da modyfikować - plus dla
security, negat dla samomodyfikacji
- dużo jest fajnych zastosowań instrumentacji kodu - gdyby ta
instrumentacja odbywała się w trakcie działania programu jakoś
sprytnie, byłby to szczególny przypadek samomodyfikacji

do góry

Marcin 'Qrczak' Kowalczyk <q...@k...org.pl> napisał(a):

> On Aug 8, 1:35=A0am, "Mariusz Marsza=B3kowski"
> <b...@W...gazeta.pl> wrote:

> Takich rzeczy nie ma.
Jakie jest źródło tej informacji? Skąd to wiadomo?

> Samomodyfikacja może przyspieszyć o stały czynnik, ale nigdy nie jest
> konieczna dla poprawy asymptotycznej złożoności.
Jakie jest źródło tej informacji? Skąd to wiadomo?

Pozdrawiam


--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

Użytkownik "Mariusz Marszałkowski" napisał:

> Chciałem zapytać jaki jest dzisiejszy stan wiedzy na temat programów
> samo-modyfikujących się. Chodzi mi o coś "więcej" niż trywialne
> doklejenie wirusa, albo przekopiowanie jednej procedury w miejsce
> drugiej.

Kolejne androny zamiast sensacji o UFO, czy potworze z Loch Ness. Kompletna
bzdura i bełkot.

Remek

do góry

On Fri, 7 Aug 2009 23:35:58 +0000 (UTC), "Mariusz Marszałkowski"
<b...@W...gazeta.pl> wrote:

>budują/modyfikują ciąg instrukcji zamiast rozwiązań częściowych i
>dzięki temu też uzyskują lepszą złożoność.

Zlozonosc czego?...

A.L.

do góry

On Fri, 7 Aug 2009 23:11:57 -0700 (PDT), "Marcin 'Qrczak' Kowalczyk"
<q...@k...org.pl> wrote:

>Innymi słowy można zastąpić kompilator interpreterem.

To znaczy co?... Inperpreter moze "poprawic zlozonosc"? Ale czego?
Zawsze wydawalo mi sie ze "zlozlnosc" to zlozonosc problemu a nie
implementacji, chyba ze sie tu jakas inna zlozlnosc rozumie

A.L.

do góry

On 8 Sie, 13:33, "Mariusz Marszałkowski" <b...@N...gazeta.pl>
wrote:
> Marcin 'Qrczak' Kowalczyk <q...@k...org.pl> napisał(a):
>
> > Samomodyfikacja może przyspieszyć o stały czynnik, ale nigdy nie jest
> > konieczna dla poprawy asymptotycznej złożoności.
>
> Jakie jest źródło tej informacji? Skąd to wiadomo?

Chodzi o to, że każdy program który jest samomodyfikujący się można
też wykonywać w emulatorze naszego pierwotengo systemu - i wtedy już
nie wykonujemy programu samomodyfikującego się. Emulacja zwykłych
programów nie zmienia asympototycznej złożoności ich algorytmów - po
prostu każda instrukcja się wykonuje np. 100 razy wolniej i tyle.

A czy są niezwykłe programy? Może mogą być, gdy w jakiś nietrywialny
sposób oddziałują z systemem operacyjnym (tak, że taka emulacja wprost
się załamuje). Na przykład wywołują funkcje systemu operacyjnego,
która oblicza skrót kryptograficzny wybranego fragmentu pamięci
zawierającej kod wykonywanego programu (normalnie takich funkcji nie
ma, ale to tylko przykład).

-ms

do góry