Definicje - egzaminwer2, WAT, III SEM, OPTYAMALIZACJA, PO - egzamin, PO - egzamin


Zbiór 0x01 graphic
nazywamy wypukłym, jeżeli dla każdych dwóch punktów 0x01 graphic
punkt 0x01 graphic
należy do 0x01 graphic
dla każdego 0x01 graphic

Hiperpłaszczyzną 0x01 graphic
w przestrzeni En nazywamy zbiór: 0x01 graphic
gdzie (a|x) - iloczyn skalarny wektorów a,x

Hiperpłaszczyznę 0x01 graphic
nazywamy podpierającą zbiór 0x01 graphic
w punkcie x0, gdy zachodzi 0x01 graphic
oraz 0x01 graphic
albo 0x01 graphic

Zbiór 0x01 graphic
nazywamy ograniczonym od dołu (od góry), jeśli istnieje taki punkt 0x01 graphic
, że 0x01 graphic
(0x01 graphic
)

Zbiór 0x01 graphic
nazywamy ograniczonym, jeżeli jest ograniczony od dołu i od góry.

Wierzchołkiem zbioru wypukłego 0x01 graphic
nazywamy taki punkt 0x01 graphic
, dla którego nie istnieją dwa różne punkty 0x01 graphic
, takie że 0x01 graphic
dla każdego 0x01 graphic

Stożkiem S w przestrzeni En nazywamy taki zbiór punktów x, że dla każdego 0x01 graphic
punkt 0x01 graphic
, czyli 0x01 graphic

Zbiorem wielościennym nazywamy zbiór 0x01 graphic
postaci: 0x01 graphic
przy czym istnieje takie i, że 0x01 graphic

Wielościanem nazywamy zbiór wielościenny ograniczony.

Funkcja rzeczywista f określona na wypukłym zbiorze 0x01 graphic
nazywa się wypukłą, jeśli dla każdego 0x01 graphic
oraz każdego 0x01 graphic
spełniona jest nierówność: 0x01 graphic
Jeśli natomiast spełniona jest nierówność 0x01 graphic
to funkcję nazywamy wklęsłą.

Ponadto, jeśli w pierwszym równaniu dla każdego 0x01 graphic
i każdych 0x01 graphic
zachodzi nierówność ostra, to funkcję f nazywamy ściśle wypukłą.

Analogicznie, jeśli w drugim równaniu dla każdego 0x01 graphic
i każdych 0x01 graphic
zachodzi nierówność ostra, to funkcję f nazywamy ściśle wklęsłą.

Rozwiązaniem bazowym układu równań Ax=d odpowiadającym bazie B nazywamy rozwiązanie x tego układu postaci: 0x01 graphic
gdzie xB - wektor składowych wektora x odpowiadających kolumnom bazy B; xR - pozostałe składowe

Zmiennymi bazowymi rozwiązania bazowego x nazywamy te składowe wektora x, które odpowiadają wektorom bazy B. Pozostałe składowe tego wektora nazywamy zmiennymi wtórnymi.

Rozwiązanie bazowe x odpowiadające bazie B spełniającej warunki: 0x01 graphic
czyli 0x01 graphic
nazywamy dualnie dopuszczalnym.

Rozwiązanie dualnie dopuszczalne staje się prymalnie dopuszczalnym, gdy

x>=0 (tzn. xB=B-1d>=0, xR=0)

Problem decyzyjny 0x01 graphic
jest zadany, jeśli zadany jest zbiór parametrów tego problemu (bez nadanych wartości) oraz pytanie, na które odpowiedź brzmi „tak” lub „nie”

Rozmiarem N(z) konkretnego problemu decyzyjnego 0x01 graphic
nazywamy długość łańcucha danych x(z), czyli N(z)=|x(z)|

Złożonością obliczeniową algorytmu α nazywamy funkcję postaci 0x01 graphic
gdzie t(z, α,n) - liczba elementarnych operacji (kroków DTM) potrzebna do rozwiązania problemu 0x01 graphic
o rozmiarze N(z)=n za pomocą algorytmu α.

Mówimy, że algorytm α ma złożoność obliczeniową wielomianową, jeśli istnieje stała c>0 oraz wielomian p(n), taki że: 0x01 graphic
co zapiszemy 0x01 graphic
. W innych przypadkach mówimy, że algorytm α ma złożoność wykładniczą.

Złożonością obliczeniową problemu 0x01 graphic
nazywamy złożoność najlepszego możliwego algorytmu rozwiązującego ten problem

Klasą P nazywamy klasę problemów decyzyjnych, których złożoność obliczeniowa jest wielomianowa

Mówimy, że problem decyzyjny 0x01 graphic
należy do klasy NP, jeśli istnieje wielomian p(n) zależny od rozmiaru tego problemu oraz algorytm α (algorytm weryfikacji potwierdzenia) takie, że dla każdego konkretnego problemu 0x01 graphic
z odpowiedzią „tak” i łańcucha danych x(z) istnieje łańcuch (potwierdzenie odpowiedzi „tak”) c(x) symboli alfabetu wyjściowego Σ, dla którego:

- |c(x)|=<p(N(z)),

- algorytm α po otrzymaniu na wejściu sekwencji x(z) # c(x(z)) (# koniec danych, początek potwierdzania) dochodzi do odpowiedzi „tak” po nie więcej niż p(N(z)) krokach

Problem decyzyjny 0x01 graphic
1 jest wielomianowo transformowalny do 0x01 graphic
2, jeśli dla dowolnego łańcucha x danych problemu 0x01 graphic
1 można w wielomianowym czasie (wielomian zależy od |x(z)|) zbudować łańcuch y danych problemu 0x01 graphic
2, taki, że: x(z) będzie łańcuchem danych konkretnego problemu 0x01 graphic
z odpowiedzią „tak” wtedy i tylko wtedy, gdy y(z') będzie łańcuchem danych konkretnego problemu 0x01 graphic
z odpowiedzią „tak”; oznaczmy to następująco: 0x01 graphic

Problem 0x01 graphic
nazywamy NP.- zupełnym , jeśli każdy problem 0x01 graphic
transformuje się wielomianowo do 0x01 graphic
tzn. 0x01 graphic
'0x01 graphic
0x01 graphic

Macierz B kwadratową, nieosobliwą o elementach całkowitych nazywamy unimodularną, gdy D= |det B| =1 gdzie det B - oznacza wyznacznik macierzy B

Całkowitoliczbową macierz A=(aij)mxn nazywamy całkowicie unimodularną, gdy każda jej podmacierz kwadratowa, nieosobliwa jest unimodularna

Podziałem P zbioru S nazywamy zbiór podzbiorów 0x01 graphic
zbioru S, takich że: 0x01 graphic
, 0x01 graphic
∅ dla j ≠ k

Oszacowaniem od góry wartości z(x*(j)) nazywamy wartość 0x01 graphic
, taką, że 0x01 graphic

Oszacowaniem od dołu wartości z(x*(j)) nazywamy wartość 0x01 graphic
, taką, że 0x01 graphic

Wektor zmiennych o ustalonych na drodze Dk wartościach 0x01 graphic
0x01 graphic
j∈Wk nazywamy rozwiązaniem częściowym (w wierzchołku Sk)

Wektor xd(k)=(0x01 graphic
), j∈Fk, 0x01 graphic
∈{0,1} nazywamy dopełnieniem rozwiązania częściowego (w wierzchołku Sk)

Dopełnienie xd(k) nazywamy dopuszczalnym jeśli łącznie z rozwiązaniem częściowym xc(k) tworzy wektor x∈S; w przeciwnym przypadku nazywamy niedopuszczalnym.

Parę (x*, y*) nazywamy punktem siodłowym funkcji F(x,y) w zbiorze AxB, jeżeli dla każdego x∈A0x01 graphic
En oraz każdego y∈B0x01 graphic
Em zachodzi: F(x*, y)≤ F(x*, y*)≤ F(x, y*)

Niech zbiór 0x01 graphic
zadania 0x01 graphic
będzie zbiorem domkniętym w En. Niech 0x01 graphic
będą funkcjami ciągłymi. Mówimy, że ciąg (0x01 graphic
) nazywa się ciągiem zewnętrznych funkcji kary, jeśli:

1. 0x01 graphic
=0 dla każdego x∈0x01 graphic
oraz k=0,1,2...

2. 0x01 graphic
>0 dla każdego x∉0x01 graphic
oraz k=0,1,2...

3. 0x01 graphic
>0x01 graphic
dla każdego x∉0x01 graphic
oraz k=0,1,2...

4. 0x01 graphic
dla każdego x∉0x01 graphic

Niech zbiór 0x01 graphic
zadania 0x01 graphic
będzie zbiorem domkniętym. Niech Fk będzie funkcją określoną na wnętrzu 0x01 graphic
zbioru 0x01 graphic
dla k=0,1,2,...Ciąg funkcji (Fk) nazywamy ciągiem wewnętrznych funkcji kar jeśli:

1. Fk(x)>Fk+1(x)>0 dla każdego x∈0x01 graphic
, k=0,1,2...

2. 0x01 graphic
dla każdego x∈0x01 graphic
,

3. 0x01 graphic
dla każdego ciągu (xl), xl0x01 graphic
takiego, że 0x01 graphic
, k=0,1,2,... gdzie 0x01 graphic
0x01 graphic
0x01 graphic
, 0x01 graphic
0x01 graphic
- brzeg zbioru 0x01 graphic

Kierunek (wektor) sEn nazywamy dopuszczalnym w punkcie x0x01 graphic
, że względu na zbiór 0x01 graphic
, jeśli istnieje taka liczba τ>0, że dla dowolnego t∈[0, τ] punkt postaci x'=x+ts należy do zbioru 0x01 graphic

Mówimy, że ograniczenia zadania 0x01 graphic
regularne, gdy zachodzi: dla każdego x∈0x01 graphic
0x01 graphic

Kierunek dopuszczalny sEn w punkcie x0x01 graphic
nazywamy poprawiającym (kierunkiem poprawy) ze względu na funkcję celu f(•), jeśli f(x+ts)<f(x) dla t∈(0, τ], τ>0 co w przypadku różniczkowalnej funkcji f(•) jest równoważne warunkowi: (0x01 graphic
należy do 0x01 graphic
dla t∈(0, τ], τ>0



Wyszukiwarka

Podobne podstrony:
Definicje - egzamin, WAT, III SEM, OPTYAMALIZACJA, PO - egzamin, PO - egzamin
!!!Chudy, WAT, III SEM, OPTYAMALIZACJA, PO - egzamin, PO - egzamin
PO, WAT, III SEM, OPTYAMALIZACJA, PO - egzamin, PO - egzamin
podstawy optymalizacji egzamin rozwiazania, WAT, III SEM, OPTYAMALIZACJA
Zadania I2Y3S1, WAT, III SEM, GK
ZAGADNIENIA NA EGZAMIN Z MECHANIKI TECHNICZNEJ II DLA SEMESTRU III, sem III, +Mechanika Techniczna I
EGZAMIN, far, II rok III sem, biochemia, egzamin
EGZAMIN patofizjologia, far, II rok III sem, patofizjologia, wykłady egzamin
9 Wykład Patofizjologia 1, far, II rok III sem, patofizjologia, wykłady egzamin
10 Wykład Patofizjologia, far, II rok III sem, patofizjologia, wykłady egzamin
2 Wykład Patofizjologia, far, II rok III sem, patofizjologia, wykłady egzamin
Egzamin z biochemii-, far, II rok III sem, biochemia, egzamin
12-Wykład-Patofizjologia, far, II rok III sem, patofizjologia, wykłady egzamin
3 Wykład Patofizjologia, far, II rok III sem, patofizjologia, wykłady egzamin
12 Wykład Patofizjologia, far, II rok III sem, patofizjologia, wykłady egzamin

więcej podobnych podstron