Zeszyt do informatyki : marca 2014

niedziela, 30 marca 2014

Palindrom

Palindrom (tudzież anagram odwrotny) jest to wyraz, liczba, który odczytany zarówno normalnie (od przodu), jak i wspak (od tyłu) daje taki sam ciąg, np. palindromem jest wyraz "kajak", czy liczba 656. Ponadto ciąg składający się z mniej niż dwóch znaków jest palindromem (np. litera K).

Algorytm

1. boolean is_palindrome(string S)
2. begin
3.    integer I ← (ilość znaków z S) div 2 // przyjmujemy S[0] = pierwsza litera S
4.    while I > 0 do
5.    begin
6.        I ← I - 1
7.        if S[I] != S[ilość znaków z S - I - 1] then return false
8.    end
9.    return true
10. end

3. Deklaracja zmiennej I i przypisanie do niej połowy długości ciągu (zaniedbując część ułamkową), przekazanego w parametrze funkcji.
7. Jeśli I-ty znak ciągu S jest różny od znaku na pozycji: ilość znaków z S - I - 1, zwróć false - ciąg nie jest palindromem.
9. Podczas działania pętli, nie została zwrócona wartość false, więc ciąg jest palindromem.

środa, 26 marca 2014

Ogólny problem plecakowy

Dyskretny problem plecakowy (ang. discrete knapsack problem) jest jednym z najczęściej poruszanych problemów optymalizacyjnych. Nazwa zagadnienia pochodzi od maksymalizacyjnego problemu wyboru przedmiotów, tak by ich sumaryczna wartość była jak największa i jednocześnie mieściły się w plecaku. Przy podanym zbiorze elementów o podanej wadze i wartości, należy wybrać taki podzbiór by suma wartości była możliwie jak największa, a suma wag była nie większa od danej pojemności plecaka.

Problem plecakowy często przedstawia się jako problem złodzieja rabującego sklep – znalazł on N towarów; j–ty przedmiot jest wart $c_{j}$ oraz waży $w_{j}$ . Złodziej dąży do zabrania ze sobą jak najwartościowszego łupu, przy czym nie może zabrać więcej niż B kilogramów. Nie może też zabierać ułamkowej części przedmiotów (byłoby to możliwe w ciągłym problemie plecakowym).

Podobny problem pojawia się często w kombinatoryce, teorii złożoności obliczeniowej, kryptografii oraz matematyce stosowanej.

Decyzyjna wersja przedstawionego zagadnienia to pytanie "czy wartość co najmniej Cmoże być osiągnięta bez przekraczania wagi W?"

Definicja

Definicja formalna: mamy do dyspozycji plecak o maksymalnej pojemności $B$ oraz zbiór $N$ elementów $\{x_1, x_j, ..., x_N\}$ , przy czym każdy element ma określoną wartość $c_{j}$ oraz wielkość $w_{j}$ .

Dyskretny problem plecakowy (ang. 0-1 knapsack problem)

formalnie problem może być zdefiniowany:

zmaksymalizuj $\sum_{j=1}^N c_j x_j.$

przy założeniach: $\sum_{j=1}^N w_j x_j \le B, \quad \quad x_j = 0\;\mbox{lub}\;1, \quad j=1,\dots,n.$

Problem plecakowy, w którym liczba elementów danego typu jest ograniczona przez podaną wartość (ang. bounded knapsack problem).

Formalnie:

zmaksymalizuj $\sum_{j=1}^N c_j x_j.$

przy założeniach: $\sum_{j=1}^N w_j x_j \le B, \quad \quad 0 \le x_j \le b_j, \quad j=1,\dots,n.$

Można rozważać także przypadek w którym nie ma wartości ograniczającej liczbę elementów danego typu (ang. unbounded knapsack problem).

W ciągłym problemie plecakowym można brać ułamkowe części przedmiotów.

W przypadku, gdy problem jest rozważany przy założeniach, że

jest problemem decyzyjnym
jest dyskretny
dla każdego elementu waga równa się wartości $w_j=c_j$

utożsamiany jest z problemem: czy dla danego zbioru liczb całkowitych istnieje taki jego podzbiór, że suma jego liczb wynosi dokładnie W? Zagadnienie to nazywane jest problemem sumy podzbioru.

Problem plecakowy może być rozwiązany przy użyciu programowania dynamicznego, ale rozwiązanie wielomianowe nie jest znane. Problem plecakowy oraz sumy podzbioru są problemami NP trudnymi, co było powodem użycia sumy podzbioru jako podstawy w niektórych systemach kryptografii asymetrycznej takich jak Merkle-Hellman. Algorytmy takie używały grup, nie liczb całkowitych. Merkle-Hellman oraz kilka podobnych algorytmów zostało w późniejszym czasie złamanych, ponieważ szczególny problem sumy podzbioru użyty w tych algorytmach były rozwiązywalne w czasie wielomianowym^.

Decyzyjna wersja problemu plecakowego opisana wyżej jest problemem NP zupełnym i jest jednym z 21 NP zupełnych problemów Karpa.

Realizacje algorytmu

Przegląd zupełny

Przegląd zupełny (bruteforce, metoda siłowa) – metoda nieefektywna obliczeniowo (ale optymalna, gdyż znajduje rozwiązanie najlepsze); w jego przypadku złożoność obliczeniowa algorytmu wyniesie $\Theta(2^n)$ , co zdecydowanie zawyży czas działania dla dużych n. Złożoność wynosi $\Theta(2^n)$ ponieważ jest tyle możliwych ciągów zero jedynkowych na n polach. Złożoność można również obliczyć ze wzoru dwumianowego Newtona (dwumian Newtona) podstawiając za a i b jedynki.

poniedziałek, 24 marca 2014

Przybliżona wartość miejsca zerowego - metoda połowienia przedziałów

Obliczanie pola obszaru ograniczonego wykresem funkcji

Metoda całkowanie numerycznego zajmuje się obliczaniem pola obszaru ograniczonego wykresem funkcji. Wyróżniamy metody:
a) prostokątów
b) trapezów

wtorek, 18 marca 2014

Wyznaczanie różnych wartości za pomocą działań algebraicznych

Metoda Newtona (zwana również metodą Newtona-Raphsona lub metodą stycznych) – iteracyjny algorytm wyznaczania przybliżonej wartości pierwiastka funkcji.

Metoda Newtona jest połączeniem idei iteracji i lokalnej aproksymacji liniowej. W tej metodzie iteracyjnej x_n+1 jest określone jako odcięta punktu przecięcia z osią x stycznej do krzywej y=f(x) w punkcie (x_n,f(x_n)).

Przybliżanie krzywej y=f(x) styczną do niej w punkcie (x₀,f(x₀)) jest równoważne zastąpieniu funkcji dwoma początkowymi składnikami jej szeregu Taylora w punkcie x=x₀. Odpowiednie przybliżanie dla funkcji wielu zmiennych ma również ważne zastosowania.

Do wyznaczenia x_n+1 służy równanie

Metodę Newtona określa następujący wzór iteracyjny:

gdzie

Iteracje można przerwać, gdy |h_n| stało się mniejsze od dopuszczalnego błędu pierwiastka (trzeba tu uwzględnić również błędy zaokrągleń i inne błędy popełniane w obliczaniu h_n).

Różnym od kreślenia stycznej sposobem lokalnej aproksymacji krzywej jest wybór dwóch sąsiednich punktów na niej i przybliżanie jej sieczną łączącą te punkty