Artykuły do poprawy

Kapuściane materiały

Kapustka
Ten artykuł wymaga dopracowania!

Jeżeli możesz popraw ten artykuł według zaleceń, które możesz znaleźć na stronie [[Artykuły do poprawy]]. Po dopracowaniu tego tekstu można usunąć ten komunikat.

DefinicjeProblemyAlgorytmy

KAPUŚCIANE MATERIAŁY

Postanowiłem ułatwić wam (i sobie) dyskusję na forum.
Będę gromadził tu definicje, problemy programistyczne i algorytmy. Nie wszystkie one kwalifikują się na osobny artykuł, stąd pomysł na jeden "zbiorczy". Na forum mam zamiar często dawać tu linka - w nadziei, że wzbjemy się na wyższy poziom rozmawiania o problemach.

DEFINICJE

Algorytmika:powrót do menu.
problem decyzyjnytaki problem, którego wynikiem jest strwierdzenie "tak" lub "nie",
np. problemem decyzyjnym jest pytanie: czy zadana liczba jest liczbą pierwszą?
problem obliczeniowyproblem, który wymaga dostarczenia w odpowiedzi pewnych wartości,
np. problemem obliczeniowym jest: oblicz kwadrat zadanej liczby
metoda obliczeniowaprocedura przekształcająca dane wejściowe w wynik za pomocą jednoznacznie zdefiniowanych, elementarnych kroków
algorytm częściowo poprawnyniekoniecznie kończą się metoda obliczeniowa, która ma następującą cechę: jeśli sie zatrzyma to zawsze w odpowiedzi zwróci prawidłowy wynik
metoda numerycznabędąca rozwiązaniem problemu obliczeniowego metoda obliczeniowa, której odpowiedź nie jest precyzyjna tylko przybliżona, przy czym znamy granice tego przybliżenia (tzn. znamy wartość maksymalnego względnego błędu jaki może wystąpić)
metoda probabilistycznabędąca rozwiązaniem problemu decyzynego taka metoda obliczeniowa, że udzielana odpowiedź jest czasami błędna, przy czym prawdopodobieństwo wystąpienia tego błędu jest nam znane
algorytm całkowicie poprawnymetoda obliczeniowa, która dla każdego zestawu danych wejściowych zawsze się zakończy w skończonej liczbie kroków i zwróci wynik, który zawsze będzie poprawny
złożoność obliczeniowacecha algorytmu, funkcja czasu od zmiennych wejściowych, która dla danych wartości określa jak dużo czasu upłynie do chwili zakończenia alogrytmu i udzielenia odpowiedzi.
... mówimy, że problem ma złożoność:
stałą - jeśli funkcja ta jest stała
logarytmiczną - jeśli funkcja ta jest logarytmem
liniową - jeśli funkcja ta jest liniowa, czyli jest wielomianem stopnia 1
kwadratowa - jeśli jest wielomianem stopnia 2
wielomianową - jeśli funkcja ta jest wielomianem dowolnego stopnia
wykładniczą - jeśli funkcja ta jest wykładnicza (tzn. wykładnikiem potęgi jest zmienna)
górne ograniczenie problemuzłożoność obliczeniowa najlepszego (czyli takiego, którego złożoność obliczeniowa jest najmniejsza) odkrytego w danej chwili całkowicie poprawnego algorytmu, będącego rozwiązaniem danego problemu
dolne ograniczenie problemuteoretycznie udowodniona, nieprzekraczlna dolna granica złożoności obliczeniowej dla każdego całkowicie poprawnego algorytmu będącego rozwiązaniem danego problemu
problem zamkniętytaki problem, którego dolne i górne ograniczenia się zeszły, czyli dla którego odnaleziony już został najszybszy całkowicie poprawny algorytm rozwiązujący ten problem
luka algorytmicznasytuacja, gdzie wyznaczone zostało dolne ograniczenie pewnego problemu i jednocześnie najszybszy znany, całkowicie poprawny algorytm dla tego problemu ma złożonść obliczeniową większą od tegoż dolnego ograniczenia
problem łatwo roziązywalnyproblem, którego dolne ograniczenie jest funkcją co najwyżej wielomianową
problem trudno rozwiązywalnyproblem, którego dolne ograniczenie jest funkcją wykładniczą
problem nierozwiązywalnytaki problem, dla którego udowodniono, że nie może istnieć jakikolwiek, całkowicie poprawny rozwiązujący go algorytm
Matematyka:powrót do menu.
"x"dla każdego x", kwantyfikator ogólny (od angielskiego "all")
$x"istnieje taki x", kwantyfikator szczególny (od angielskiego "exists")
zbiór{a1,a2,...an} pojęcie podstawowe: elementy zbioru nie mogą się powtarzać i są nieuporządkowane (tzn. żaden element zbioru nie jest "pierwszy"), szczególnie ważne są:
N- zbiór liczb naturalnych
Z- zbiór liczb całkowitych
Q- zbiór liczb wymiernych
IQ- zbiór liczb niewymiernych
R- zbiór liczb rzeczywistych
C- zbiór liczb zespolonych
para uporządkowana(a,b) º { {a,b},a }
zbiór dwuelementowy, w którym jeden element jest wyróżniony jako poprzednik
iloczyn kartezjańskiAxB º { (a,b): aÎA, bÎB }
zbiór wszystkich par (a,b), takich że aÎA oraz bÎB
</tr>podzbiór</td>AÍB Û "aÎA: aÎB
A jest podzbiorem B gdy każdy element A należy do B</td></tr>relacja binarna</td>r Í AxB
podzbiór iloczynu kartezjańskiego</td></tr>funkcja</td>f:A®B º rÍAxB: "aÎA istnieje co najwyżej jeden taki bÎB, że (a,b)Îr
relacja - czyli zbiór par - gdzie każdy poprzednik ma co najwyżej jednego następnika</td></tr>ciąg</td>(a1,a2,...an) º ( f(k1),f(k2),...f(kn) )
f:N®A      a1,a2,...anÎA,      k1<k2<...<kn</sub>ÎN
elementy ciągu mogą się powtarzać i są uporządkowane, ciąg jest funkcją</td></tr>alfabet</td>niepusty i skończony zbiór symboli (symbol jest pojęciem podstawowym), elementy tego zbioru nazywamy literami np. zbiór S={a,ab,c,ccc} jest alfabetem do którego należą litery a, ab, c oraz ccc</td></tr>słowo nad alfabetem</td>dowolny skończony ciąg liter danego alfabetu np. przykładami słów nad powyższym alfabetem S, są: aba, aab, słowo puste oraz cc</td></tr>część całkowita x</td>największa z liczb całkowitych n takich że n£x np. część całkowita 2.4=2, część całkowita -4.3=-5</td></tr></table>Pseudo-język:</td>powrót do menu.</td></tr></table>Do opisu algorytmów używam umownego pseudo-języka programowania wysokiego poziomu.
Nazwy procedur są zapisywane wielkimi literami, natomiast zmienne małymi.
Tablice są indeksowane od 1 (indeksy w nawiasach kwadratowych).
x:=y</td>operacja przypisania, "przypisz wartość y do x"</td></tr>x«y</td>operacja zamiany wartości x i y
odpowiada ona schematowi:
t:=x
x:=y
y:=t
</td></tr>x=y</td>zdanie logiczne, "x jest równe y"</td></tr>x!=y</td>zdanie logiczne, "x nie jest równe y"</td></tr>x div y</td>część całkowita ilorazu x/y</td></tr>x mod y</td>reszta dzielenia całkowitego x/y</td></tr>length(tab)</td>indeks ostatniego elementu w tablicy</td></tr></table>

PROBLEMY

Problem odpowiedniości słów:</td>powrót do menu.</td></tr></table>typ:</td>decyzyjny</td>ogr.dolne:</td>-</td>ogr.górne:</td>-</td>status:</td>nierozwiązywalny</td></tr></table>Dane wejściowe:
alfabet S
dwa równoliczne ciągi słów nad alfabetem S, X(x1,x2,...xn) i Y(y1,y2,...yn).
Wynik:
tak - jeśli istnieje taki ciąg indeksów I(i1,i2,...ik), że (xi1,xi2,...xik)=(yi1,yi2,...yik).
nie - w przeciwnym wypadku.

przykład:
alfabet S = {a,b}
</td>1</td>2</td>3</td>4</td></tr>X</td>aa</td>b</td>aa</td>ab</td></tr>Y</td>a</td>abaa</td>b</td>a</td></tr></table>Wynikiem jest "tak", gdyż ciąg indeksów 1,2,3,2,4,1,1,1 generuje to samo słowo w X i Y, mianowicie:
aabaababaaaaaa

ALGORYTMY

Algorytm mnożenia chłopów rosyjskich:</td>powrót do menu.</td></tr></table>typ:</td>całkowicie poprawny</td>złożoność obl:</td>logarytmiczna</td>błąd/prawd:</td>-</td></tr></table>Dane wejściowe:
liczba naturalna x
liczba rzeczywista y
Wynik:
wartość iloczynu xy

MNOŻENIE_CHŁOPÓW_ROSYJSKICH (x,y)
1. z:=0
2. while x!=0
    2.1 if x mod 2=1 then z:=z+y
    2.2 x:=x div 2
    2.3 y:=y2
3. stop, wynik=z
Binpower:</td>powrót do menu.</td></tr></table>typ:</td>całkowicie poprawny</td>złożoność obl:</td>logarytmiczna</td>błąd/prawd:</td>-</td></tr></table>Dane wejściowe:
liczba naturalna x
liczba rzeczywista y
Wynik:
wartość yx

BINPOWER (x,y)
1. z:=1
2. while x!=0
    2.1 if x mod 2=1 then z:=zy
    2.2 x:=x div 2
    2.3 y:=yy
3. stop, wynik=z
Pierwiastek dowolnego stopnia:</td>powrót do menu.</td></tr></table>typ:</td>całkowicie poprawny</td>złożoność obl:</td>logarytmiczna</td>błąd/prawd:</td>-</td></tr></table>Dane wejściowe:
liczba rzeczywista x
liczby naturalne n, m
Wynik:
pierwiastek n-tego stopnia z liczby x
przy dokładności do m miejsc po przecinku

PIERWIASTEK (x,n,m)
1. y:=0, p:=0, d:=1
2. while p!=x
    2.1 if p>x
        2.1.1 y:=y-d
        2.1.2 d:=d/10
        2.1.3 if m=0 then stop, wynik=y
        2.1.4 m:=m-1
    2.2 y:=y+d
    2.3 p:=1
    2.4 for i:=1 to n
        2.4.1 p:=py
3. stop, wynik=y
Test Rabina-Millera:</td>powrót do menu.</td></tr></table>typ:</td>metoda probabilistyczna</td>złożoność obl:</td>-</td>błąd/prawd:</td>błąd na 25%</td></tr></table>Dane wejściowe:
liczba naturalna x
Wynik:
tak - jeśli x jest liczbą pierwszą
nie - w przeciwnym wypadku

TEST_RABINA-MILLERA (x)
1. a:=1
2. do
    2.1 a:=a+1
    2.2 untill NWD(a,x)=1
3. d:=x-1
4. s:=0
5. while d mod 2=0
    5.1 d:=d/2
    5.2 s:=s+1
6. if (ad) mod x=1 then stop, wynik="tak", 25% szansa popełnienia błędu
7. for r:=0 to s
    7.1 if a((2^r)d) mod x=x-1 then stop, wynik="tak", 25% szansa popełnienia błędu
8. stop, wynik="nie"
Algorytm Euklidesa:</td>powrót do menu.</td></tr></table>typ:</td>całkowicie poprawny</td>złożoność obl:</td>liniowa</td>błąd/prawd:</td>-</td></tr></table>Dane wejściowe:
dwie liczby naturalne n, m
Wynik:
największy wspólny dzielnik zadanych liczb

EUKLIDES (n,m)
1. if n>m then n«m
2. if n>0 then EUKLIDES (n,m-n)
3. stop, wynik=m

więcej
Największy wspólny dzielnik:</td>powrót do menu.</td></tr></table>typ:</td>całkowicie poprawny</td>złożoność obl:</td>logarytmiczna</td>błąd/prawd:</td>-</td></tr></table>Dane wejściowe:
dwie liczby naturalne n£m
Wynik:
największy wspólny dzielnik zadanych liczb

NWD_1 (n,m)
1. if n>0 then NWD_1 (m mod n,n)
2. stop, wynik=m

więcej
Największy wspólny dzielnik:</td>powrót do menu.</td></tr></table>typ:</td>całkowicie poprawny</td>złożoność obl:</td>logarytmiczna</td>błąd/prawd:</td>-</td></tr></table>Dane wejściowe:
dwie liczby naturalne n, m
oraz w:=1
Wynik:
największy wspólny dzielnik liczb n i m

NWD_2 (n,m,w)
1. if n=0 then stop, wynik=wm
2. if m=0 then stop, wynik=wn
3. if (n mod 2=0 and m mod 2=0) then NWD_2 (n/2,m/2,2w)
4. if n mod 2=0 then NWD_2 (n/2,m,w)
5. if m mod 2=0 then NWD_2 (n,m/2,w)
6. if n>=m then NWD_2 (n-m,m,w)
7. NWD_2 (n,m-n,w)
Sortowanie przez wstawianie:</td>powrót do menu.</td></tr></table>typ:</td>całkowicie poprawny</td>złożoność obl:</td>kwadratowa</td>błąd/prawd:</td>-</td></tr></table>Dane wejściowe:
niepusta tablica porównywalnych elementów tab
Wynik:
posortowana malejąco tablica tab

INSERTION_SORT (tab)
1. for k:=1 to length(tab)
    1.1 i:=k-1
    1.2 while i>0 and tab[k]>tab[i]
        1.2.1 tab[k]«tab[i]
        1.2.2 i:=i-1
2. stop

więcej
Sortowanie przez scalanie:</td>powrót do menu.</td></tr></table>typ:</td>całkowicie poprawny</td>złożoność obl:</td>nlog(n)</td>błąd/prawd:</td>-</td></tr></table>Dane wejściowe:
niepusta tablica porównywalnych elementów tab
oraz p:=1, k:=length(tab)
Wynik:
posortowana malejąco tablica tab

MERGE_SORT (tab,p,k)
1. if p!=k
    1.1 d:=(k-p) div 2
    1.2 m:=p+d
    1.3 MERGE_SORT (tab,p,m)
    1.4 MERGE_SORT (tab,m+1,k)
    1.5 w1:=p, w2:=m+1
    1.6 for i:=0 to (k-p)
        1.6.1 if w1>m or (w2<=k and tab[w2]>tab[w1])
            1.6.1.1 temp[i]:=tab[w2]
            1.6.1.2 w2:=w2+1
        1.6.2 else
            1.6.2.1 temp[i]:=tab[w1]
            1.6.2.2 w1:=w1+1
    1.7 for i:=0 to (k-p)
        1.7.1 tab[p+i]:=temp[i]
2. stop
Quicksort:</td>powrót do menu.</td></tr></table>typ:</td>całkowicie poprawny</td>złożoność obl:</td>n*log(n)</td>błąd/prawd:</td>-</td></tr></table>Dane wejściowe:
niepusta tablica porównywalnych elementów tab
oraz p:=1, k:=length(tab)
Wynik:
posortowana malejąco tablica tab

QUICK_SORT (tab,p,k)
1. if p>=k then stop
2. m:=1
3. for i:=(p+1) to k
    3.1 if tab[i]>tab[p]
        3.1.1 m:=m+1
        3.1.2 tab[m]«tab[i]
4. tab[p]«tab[m]
5. QUICK_SORT (tab,p,m-1)
6. QUICK_SORT (tab,m,k)

więcej
Algorytm wyszukiwania binarnego:</td>powrót do menu.</td></tr></table>typ:</td>całkowicie poprawny</td>złożoność obl:</td>logarytmiczna</td>błąd/prawd:</td>-</td></tr></table>Dane wejściowe:
niepusta posortowana tablica elementów tab
element a
oraz p:=1, k:=length(tab)
Wynik:
0 jeśli element a nie znajduje się w tab
w przeciwnym wypadku indeks pierwszego wystąpienia elementu a

BINSEARCH (tab,a,p,k)
1. if p!=k
    1.1 d:=(k-p) div 2
    1.2 if a>tab[p+d] then BINSEARCH (tab,a,p+d+1,k)
    1.3 BINSEARCH (tab,a,p,p+d)
2. if tab[p]=a then stop, wynik=p
3. stop, wynik=0
<address>Ostatnia aktualizacja: 23 stycznia 2003</address>
powrót do menu.</td>avatar8.jpg</td></tr></table></p>
Z pogranicza Artykuły do poprawy

12 komentarzy

GR

usuńcie te " " bo się czytać nie da
(a potem usuńce mój komentarz :-) )

lofix

Hłasko byłby z Ciebie dumny...Karpia zjem!!

DR

tyyy miałeś jakąś ściąge :D

PE

Wiesz Kapustka art swietny tylko ja bym jeszcze dodal jakis krociotki komentarzyk do kazdego bo taka sucha teoria do nie mnie przemawia. Ale i bez tego art zaslugujacy na jakas nagrode :)

PT

jestem 1000 osobą odlądającą to coś :)

aZgon

Kapusta, każdy twój artykół wiąże sie z zakupem nowej ryzy papieru (bo ja je lubie drukować) Jak ty tyle żeczy wiesz to napisz książke tak jak Adam ...

SE

Nic nie rozumiem ale fajnie że Ci sie chce :)

Kapustka

Studiuję informatykę ...

... i zapewniam że NIE PRZEPISYWAŁEM. Czasami spojrzałem do zeszytu z wykładów albo książki (niejednej) po to tylko, aby upewnić się w swojej wiedzy (a nie przepisywać obce mi definicje).

Już wkrótce do działu wpadnie dostawa ciekawych problemów programistycznych ...

pozdrawiam i dziękuję za ciepłe słowa

samson

dobry artykuł

Szymek

Kapustka co ty studiujesz??
Gały mnie bolą od patrzenia na to, ale fajny dział. Może napisz książkę, tylko taką dla tOpornych. Chętnie kupię. :)

Deti

yyyy ty chyba to skąś przepisałeś.... :))))