Algorytmy i struktury danych
B)
Zad 1. Przygotować program tworząc a następnie czytający, pliki tekstowe zawierające 10,100, 1000, 10 000, 100 000, 1 000 000 liczb zmiennoprzecinkowych.
Liczby mają być obliczane przez generator liczb losowych, a ich wartości mieścić się w zakresie [a, b0).
Porcje liczb zapisać do oddzielnych plików.
Zad 2. Ustalić czas wyklonania programu dla każdego z wyżej opisanych rozmiarów plików danych w postaci tabeli o następującej zawartości:
rozmiary danych | czas_tworzenia_danych | czas_pisania_do_pliku | czas_czytania_z_pliku
#include "sort.h"
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
#include <string>
#include <sstream>
#include <iomaninp>
#define zmierz_czas (X, wektor_czas) { czas = clock();
x;
czas = clock() - czas;
cout << "/t" << czas << "ms";
wektor_czasu = push_back(czas);
};
#define CZAS_tab(szer, czas) { plik <<" | |;
plik.width(szer);
plik << czas;
};
#define stworz_wektor (rozmiar) { v_db.resize (rozmiar); \
t_dbl = new double [rozmiar]; \
v_str.resize(rozmiar); \
v_int.resize (rozmiar); \
};
for (int i=0; i< rozmiar; ++i) v_dbl[i] = double_rand(0.0, 1.0);}
for (int i=0; i< rozmiar; ++i) t_dbl[i] = double_rand(0.0, 1.0);}
for (int i=0; i< rozmiar; ++i) v_str[i] = string_rand(15);}
for (int i=0; i< rozmiar; ++i) v_int[i] = int_rand(0, 100);}
#define stworz_nazwe (x, rozmiar, co , kiedy) { napis.str(" ");
napis << x << "_" << rozmiar << "_" << co"_" << kiedy".txt";
nazwa_pliku = napis.str();}
#define zapisz (rodzaj_sortowania, s, kiedy) {
stworz_nazwe (rodzaj_sterowania, n[k], "vec_double", kiedy); \
zapisz_wektor <double> (nazwa pliku.c_str(), v_dbl, s);\
stworz_nazwe (rodzaj_sterowania, n[k], "tab_double", kiedy); \
zapisz_tabl (nazwa pliku.c_str(), t_dbl, s);\
stworz_nazwe (rodzaj_sterowania, n[k], "vec_string", kiedy); \
zapisz_wektor <string> (nazwa pliku.c_str(), v_str, s);\
stworz_nazwe (rodzaj_sterowania, n[k], "vec_int", kiedy); \
zapisz_wektor <int> (nazwa pliku.c_str(), v_int, s); }
using namespace std.
double double_rtand (double fMin, double fMax) {
double f = (double) rand()/ RA?N?D_MAX;
return fMin + f * (fMax-fMin); }
int int_rand (int min, int max) {
return rand() % (max - min + 1) + min;
string string_rand (int rozmiar {
static const char alfabet [] = "abcdefghijklmnoprstuwxyz";
char * ret = new char [rozmiar + 1];
for (int i =0; i< rozmiar; ++i){
ret[i] = alfabet [ rand()%(sizeof(alfabet)-1)];}
ret [rozmiar] = NULL
return ret; }
Modułowa organizacja programu : pliki nagłówkowe + pliki ze źródłami
KISS: Keep It Simple Software
-projekt musi być prosty
-kod ma być czytelny
Stosować standardy kodowania:
dla plików źródłowych
przy nadawania nazw
wypracować styl i . konsekwentnie go stosować
Kompilator:
korzystać z kompilatora
zawsze doprowadzać do czystej kompilacji - żadnych ostrzeżeń
rozumieć ostrzężenia
Optymalizacja :
bez potrzeby nie optyamlizować
skupić się na złożoności obliczeniowej O()
// Przekopuj zdany plik do wektora łańcuchowego
#include <string>
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int main() {
vector<string> wektor; //wektor łańcuchów
iftream in("wektor.cpp"); // plik do przeczytania
string line;
while (getline(in, line))
wektor.push_back(line); //Dopisz linie na końcu wektora
//wydrukuj dodając numer wiersza
for(int i = 0; i < wektor.size() ; i++) // v.size() ilość elementów wektora
cout << i << ":" << wektor[i] << endl;
}
Zadania:
1. Poprawić swój program z poprzednich zajęć zgodnie z zasadami dobrego stylu:
a) wprowadzić moduły
b) Zlikwidować literały
c) Zlikwidować powtórzenia
d) Wprowadzić operacje rzutowania
2. Przygotować program czytający porcję 10, 100, 1 000, 10 000, 100 000, 1 000 000 linii z danego pliku do zmiennej klasy vector, a następnie wpisujący te porcje danych do różnych plików.
3. Przeprowadzić pomiar czasu wykonania zdania 2 w zależności od rozmiaru danych. Wyniki przedstawić w tabelce analogicznej do tej z zdania 1.
E)
Zmienna referencyjna (referencja):
-alias, czyli inna nazwa zmiennej
-alternatywa dla wskaźników przy przetwarzaniu zmiennych złożonych w funkcji rodzaju stałego wskaźnika do ziennej powiazanie jest na stałe
Tworzenie referencji (NOWE ZNACZENIE &):
int pies;
int ?& zswierze = pies; // to nie operator adresu, ale identyfikator typu
Oboie nazwy : zwierze i pies odnoszą się do tej samej zmiennej, tego samego fragmetntu pamięci. Powiązanie obu zmiennych jest trwałe.
Deklarując referencje trzeba ją zainicjować.
Klasyczną praktyką C++ jest przekazywanie do funkcji obiektów przez referencyjne.
Kiedy tylko można formalne parametry referencyjne należy deklarować jako stałe const, aby zabezpieczyć ssię przed nieporządną zmianą zawartości zmiennej.
Ostrożnie ze zwracaniem referencji. Unikać zwracania referencji do obszaru pamięci, który jest zwalniany po wykonaniu danej funkcji.
Metoda dziel i zwyciężaj
Divide-and-Conquer
-Divide the problem into a number of subproblems the are smaller instances of the same problem.
-Conquer the subproblems by solving them recursively. If the subproblem sizes are small enough, however, just solve the bubproblems in a straightforward manner
-Combine the solutions to the subproblems into the solution for the orginal problem.
MERGE-SORT(A, p, r)
1. if p<r
2. q=⎣(p+r)/2⎦
3. MERGE-SORT (A,p,q)
4. MERGE-SORT (A,q+1, r)
5. MERGE(A,p,q,r)
MERGE(A,p,qr)
1. n_1 = q - p + 1
2. n_2 = r - q
3. let L [1..n_1 + 1] and R[1..n_2 + 1] be new arrays
4. for i = 1 to n_1
5. L[i] = A [p + i - 1]
6. for j = 1 to n_2
7. R[j[ = A[q + j]
8. L[n_1 + 1] =∞
9. R[n_2 + 1] =∞
10. i = 1
11. j = 1
12. for k = p to r
13. if L[i] =< R[j]
14. A[k] = L[i]
15. i = i + 1
16. else A[k] = R[j]
17. j = j + 1
Using as a model, illustrate the operation odf merge sort on the array A = <3, 41, 52, 26, 38, 57, 9, 49>
Metoda dziel i zwyciężaj
dziel:
podziel tablicę A[p..r] na dwie podtablice A[p..q-1] i A[q+1..r] w taki sposób, aby każdy element tablicy A[p..q-1] był mniejszy lub równy A[q], który to jest mniejszy lub równy od dowolnego elementy w podtablicy A[q+1..r]
Zwyciężaj: rekurencyjnie zastosuj metodę podziału do podtablic
Kombinuj: tutaj już nie trzeba łączyć specjalnie
QUICKSORT(A, p, r)
1. if p < r
2. q = PARTITION(A,p,r)
3. QUICKSORT(A, p, q-1)
4. QUICKSORT(A, q+1,r)
PARTITION(A,p,r)
1. x = A[r]
2. i = p - 1
3. for j = p to r - 1
4. if A[j] =< x
5. i = i + 1
6. exchange A[i] with A[j]
7. exchange A[i+1] with A[r]
8. return i + 1
Zad
Zaimplementować procedury sortowania dług algorytmu Merge Sort i Quick Sort.
Wyznaczyć średnie efektywności tych procedur sortowania w operacjach na wektorze liczb zmiennoprzecinkowych
I) KOLEJKA
kolejka priorytetowa to struktura danych zawierająca elementy z kluczami, która pozwala na przeprowadzenie dwóch podstawowych operacji:
-wystawiania nowego elementu
oraz
-usuwania elementu o największej wartości klucza
class PriorityQueue{
private:
int * pq;
int n;
public:
PriorityQueue(int);
~PriorityQueue();
int empty() const;
void print() const;
void insert (int);
int get_max();
Dołączanie nowej wartości do kopca MAX
dołącz kolejny elementy tablicy jako liść do kopca
dopóki (element > ojciec (element) i element nie jest korzeniem)
zmień element z ojcem (element)
fixUP(A,L)
i=L
while (i>1 and A[parent(i)] < A[i])
zamien A[parent(i)] z A[i]
i=parent(i)
Zbuduj kopiec dla tablicy A:
A={5,3,17,10,84,19,6,22,9}
}
Zad I
Zaimplementować kolejkę priorytową na kopcu liczb int w dwóch wersjach: zwykłej tablicy i tablicy uporządkowanej kopcowo.
To znaczy:
a) zaprojektować odpowiednie klasy
b) zaimplementować metody klas
c) przygotować w main(testy sprawdzające poprawność obsługi kolejki priorytetowej
d) sprawdzić wydajność obu rozwiązań dla kolejki o rozmiarze N=100000
class PQ_HEAP {
private:
int *heap;
int n;
public:
PQ_HEAP(int );
~PQ_HEAP();
int empty () const;
void insert(int); /// poprawiona o fixUP()
void fixUP(int);
void print() const;
void DrukujKopiec() const;
void fixDown(int)
int get_max(); // poprawione o fixDOWN();
}
Kolejka priorytetowa - to struktura danych zawierająca elementy z kluczami, która pozwala na przeprowadzenie dwóch podstawowych operacji:
-wystawiania nowego elementu
oraz
-usuwanie wania elementu o największej wartości klucza
fixDOWN(i)
//naprawianie drzewa uporządkowanego kopcowo
//wszędzie za wyjątkiem korzenia
dpoóki(left(i) <= n)
j=left(i)
jeśli konflikt to zmień klucz węzła i z synem o większym kluczu
i = numer "wykorzystanego" syna
Max = ustaw ostatni liść w root zminiejsz wymiar kopca
fixDOWN(1) //naprawiaj kopiec od góry do dołu
Parent (i)
return [i/2]
Left (i)
return [2i]
Right (i)
return [2i + 1]
MaxHeap:
A[PARENT(i)} => A[i]
MAX_HEAPIFY(A,i)
l= LEFT (i)
r = RIGHT (i)
if (l =< A.heapsize && A[l] > A[i])
largest = l;
else
largest = i;
if (r =< A.heap_size && A[r] > A[largest])
largest = r;
if (largest ≠ i)
exchange A[i] with A[largest]
if (largest ≠ i)
exchange A[i] with A[largest]
MAX_HEAPIFY (A, largest)
J) Heapsort
Kolejka priorytetowa - to struktura danych zawierająca elementy z kluczami, która pozwala na przeprowadzenie dwóch podstawowych operacji:
-wystawiania nowego elementu
oraz
-usuwanie wania elementu o największej wartości klucza
dane + funkcje je obsługujące
class PriorityQueue{
private:
int * pq;
int n;
public:
PriorityQueue (int);
~PriorityQueue();
int empty() const;
void print() const;
void insert (int);
int get_max ();
}
class PQ_HEAP{
private:
int * heap;
int n;
public:
PQ_HEAP(int);
~PQ_HEAP();
int empty() const;
void insert (int); //poprawiona o fixUP()
void fixUP(int);
void print() const;
void DrukujKopiec() const;
void fixDown(int);
int get_max (); // poprawione o fixDOWN();
}
#ifndef KOPIEC_H
#define KOPIEC_H
void heapsort(std::string *tab, int);
class HEAP{
private:
std::string *kopiec;
int n;
void fixUp(int);
void fixDown(int);
int parent(int i) { return (i-1)/2;}
int left(int i) { return (2*i+1);}
public:
PQ_HEAP(int);
~PQ_HEAP();
int empty() ;
void insert (std::string);
void print() ;
std::string getMax (); /
}
#endif
Możliwości deklaracji zmiennej będącej tablicą tablic znakowych
char** Tablica_Łańcuchów_C_O_Dynamicznie_Przydzielanej_Pamięci;
char* Tablica_20_Łańcuchów_C[20];
char** Tablica_Łańcuchów_STL_O_Dynamicznie_Przydzielanej_Pamięci;
char* Tablica_20_Łańcuchów_STL[20];
vector<string> Wektor_STL_Łańcuchów_STL_O_Dynamicznie_Przydzialanej_Pamięci;
private:
std::string *kopiec;
->
HEAP::HEAP (int maxN)
{kopiec= new std::string[maxN]; n=0;}
Zadanie
-Zaimplementować HeapSort() wykorzystując ideę kolejki priorytetowej na kopcu.
Sort mają być łańcuchy.
-Zaimplementować funkcję operujące na funkcjach - wykorzystać wskaźniki do funkcji sortujących zamiast nużącego powtarzania tego samego kodu.
Rozważyć możliwość sortowania:
a) tablicy łańcuchów C
b) tablicy łańcuchów STL
c) wektora łańcuchów
Nazwy funkcji jako parametry funkcji
Takie same parametry, taki sam wynik, ale różne nazwy funkcji operującej.
void BubleSort (vector<string> &);
void InsertSort (vector<string> &);
void SelectSort (vector<string> &);
void MergeSort (vector<string> &);
void QuickSort (vector<string> &);
Konstrukcja wekora nazw funkcji:
typedef void (*wskaznik_do_sortu) (vector<string> &); // typ na wskaźnik do funkcji o parametrze vector<string>
void sortuj (wskaznik_do_sortu funkcja_sortu, vector<string> & wektor); // wskaźnik do funkcji, parametr przekazawany do funkcji
wskaznik_do_sortuj sorty[]={BubbleSort, SelectSort, InsertSort, MergeSort, QuickSort};
l) Lista. Zbiory dynamiczne
a) Zbiór statyczny a zbiór dynamiczny
*S,n
Zbiór S statycznie jako tablica:
1. wskażnik do początku tablicy *S
2. rozmiar tablicy n
*S
Zbiór dynamiczny:
1. elementy o zafiksowanej strukturze "wewnętrznej pamięci co dalej"
2. wskaźnik *S do pierwszego elementu
b) Operations on dynamic sets
Operations on a dynamic set can be group[ed into two categories: queries, which simply return information about the set, and modifying operations, which change the set. Here is a list of typical operations. any specific application will usually require only a few of these to be implemented.
SEARCH(S, k) - A query that, given a set S and a key value k, returns a pointer x to an element in S such that x, key = k, or NIL if no such element beloongs to S.
INSERT(S, x) - A modifying operation that arguments the set S with the element pointed to by x. We usually assume that any attributes in element x needed by the set implementation have already been initialized.
DELET(S, x) - A modifying operation that, given a pointer x to an element in the set S, removes x from S. (Note that this operation takes a pointer to an element x, not a key value.)
MINIMUM(S) - A query on a totally ordered set S that returns a pointer to the element of S with the smallest key.
MAXIMUM(S) - A query on a totally ordered set S that returns a pointer to the element of S with the largest key.
SUCCESSOR(S, x) - A query that, given an element x whose key is from a totally ordered set S, returns a pointer to the next largest element in S, or NIL if x is the maximum element.
PREDECESSOR(S, x) - A query that, given an element x whose key is from a totally ordered set S, returns a pointer to the next smaller element in S, or NIL if x is the minimum element.
c) Stos:
abstrakcyjny typ danych zawierający dwie podstawowe operacje: umieszczenie na stosie nowego elementu: insert -> push
zdejmowanie ze stosu elementu ostatnio umieszczonego: delete -> pop
Implementacja tablicowa stosu
STACK-EMPTY(S)
if S.top == 0
return TRUE
else return FALSE
PUSH(S,x)
S.top = S.top + 1
S[S.top] = x
POP(S)
if STACK-EMPTY(S)
error "underflow"
else S.top = S.top - 1
return S[S.top + 1]
d) Kolejka: QUEUE
abstrakcyjny typ danych zawierający dwie podstawowe operacje:
dokładnie nowego elementu na koniec kolejki: insert -> enqueue
obsługiwanie pierwszego elementu kolejki: delete -> dequeue
Implementacja tablicowa kolejki
ENQUEUE(Q, x)
Q[Q.tail] =x
if Q.tail == Q.length
Q.tail = 1
else Q.tail = Q.tail + 1
DEQUEUE(Q, x)
x = Q[Q.head]
if Q.head == Q.length
Q.head = 1
else Q.head = Q.head + 1
return x
e) Lista:
Zbiór danych uporządkowanych liniowo, przy czym porządek jest określony poprzez wskaźniki.
LIST-SEARCH(L, k)
x = L.head
while x ≠ NIL and x.key ≠ k
x = x.next
return x
LIST-INSERT(L, x)
x.next = L.head
if L. head ≠ NIL
L.head.prv = x
L.head = x
x.prev = NIL
LIST-DELETE(L, x)
if x.prev ≠ NIL
x.prev.next = x.next
else L.head = x.next
if x.next ≠ NIL
x.next.prev = x.prev
Lista jednokierunkowa
head -> key -> key -> NULL
kod C++ odpowiadający definicji listy jednokierunkowej.
struct node {
int key;
node * next;
};
typedef node * link;
link a = new node;
Korzystając z list pamiętać o rezerwowaniu pamięci
W C++ struktura jest klasą o wszystkich polach publicznych. Można / trzeba ją zainicjować.
struct node {
int key;
node * next;
node (int x, node * t) // konstruktor
{ key = x; next =t;}
};
typedef node * link;
link a = new node(x,t);
Tworzymy listę przechowującą n kolejnych liczb całkowitych
Konstruktor tworzy kolejny eleent tak, by wskazywał na początek listy.
efekt: lista cykliczna (zamknięta w kole)
link start = new node (1,start); // start to wskaźnik na obszar
//pamięci dla węzła, który przechowuje wartość 1 i wskazuje na siebie
link x = start; //x to wskaźnik na węzeł start
for(i=2; i<=n; i++) {
x -> next = new node (i, start);
x = x -> next;
}
cout << "\n wybijamy co m-tego \n";
while (x != x -> next) {
for (i=1; i<m; i++) x =x -> next
x -> next = x -> next-> next;
Problem Flawiusza
Zbuduj listę cykliczną o długości n, której każdy węzeł wskazuje na osobę stojącą po lewej stronie. Kasuj cyklicznie co ,-tego sąsiada. Podaj numer zwycięskiego węzła.
STOS_INT liczba();
class STOS_INT{
private:
struct node
{ int key;
node * next;
node (int x, node * t)
{key = x
next = t;}
};
typedef node *link;
link head;
public:
STOS_INT(int) ; {head=NULL;};
~STOS_INT() ;
int empty() const; {return head == NULL;}l
void push (int item); {head = new node(item, head); };
int pop();
void print() const;
};
Zadanie:
-Wykorzystać listę cykliczną do rozwiązania problemu Flawiusza
-Opracować sumowanie i odejmowanie liczb dodatnich o dowolnej długości. Skorzystać ze stosu liczb całkowitych do reprezentacji długich liczb. Stos zaimplementować na liście jednokierunkowej.
z) Drzewo przeszukiwań binarnych (BST)
najgorszy wpadek O (login)
drzewo z jedną gałęzią o długości n - najgorszym przypadku (O(n)
lewe poddrzewo węzła x : klucz[y] =< kulcz[x]
prawe poddrzewo węzła x : klucz [x] =< klucz [y]
SZUKAJ (x, k) // O(n)
if (x =NULL) lub (k = klucz[x])
return x
if k < klucz [x]
return SZUKAJ (lewy [x], k)
else return SZUKAJ (prawy[x[, k)
SZUKAJ (x,k)
while (x <> NULL)i(k<> klucz [x])
if k< klucz [x]
x = lewy [x]
else x = prawy [x]
return x
MINIMUM(x)
while (lewy [x] <> NULL)
x =lewy [x]
return x
MAKSIMUM(x)
while (prawy [x] <> NULL)
x =prawy [x]
return x
struct node {
int data;
node * left;
node * right;
}
struct node {
char op; //*, +, -
int niem?;
node * left, * right;
}
-> Odwiedzenie wierzchołka p wiąże się z:
a) if (p -> left ! = 0 && p -> data - p -> data<2)
p -> left -> data += 2;
b) if (p -> left ==0)
p -> right = 0
Szukaj (x,k)
if (x = NULL) lub (k = klucz[x])
return x;
if k < klucz [x]
return Szukaj(lewy[x], k)
else return Szukaj(prawy[x], k)
Szukaj (x,k)
while (x <> NULL) i (k <> klucz [x])
cout.self (ios::fixed, ios:: floatfield)
//////////////////////////////////
Books:
1. http://bioinformaticsinstitute.ru/sites/default/files/an_introduction_to_bioinformatics_algorithms_-_jones_pevzner.pdf
2. https://labs.xjtudlc.com/labs/wldmt/reading%20list/books/Algorithms%20and%20optimization/Introduction%20to%20Algorithms.pdf
1. Cyfry znaczące (te cyfry, ktore wiemy, że są dobre)
2. Precyzja i dokładność
3. Błędy (np. błędy metod numerycznych)
NETLIB (kolekcja bibliotek), NAG, LAPAC
Matematyczne komercyjne rozwiązania:
-Macsynia
-Maple
-Mathematica
-Mathcad
Klasyfikacja problemów numerycznych - GAMS
Przypomnij: wzór Taylor'a i szereg Taylor'a
(a_11 - λ) x_1 + a_12x_2 = 0
a_21x_1 + (a_22 - λ) x_2 = 0
APROKSYMACJA I INTERPOLACJA
INTERPOLACJA (szukamy funkcji, która przechodzi przez dane punkty układu współrzędnych)
APROKSYMACJA (szukamy funkcji która nie przechodzi przez dane punkty, ale żeby była możliwie jak najbliżej)
- RÓWNANIA RÓZNICZKOWE (bd. potem robić w MAthematice)
-CAŁKOWANIE NUMERYCZNE (stosujemy kwadratury)
-OPTYMALIZACJA (funkcja minimum itd.)
Błędy w obliczeniach z zaokrąglaniem
wzory Wieta
ax^2 + bx + c = 0
a (x - x_1)(x - x_2) = 0
a (x^2 - (x_1 + x_2) x + x_1x_2) = 0
ax_1x_2 = c
|z| = (x^2 + y^2)^1/2 = x(1 + (y/x)^2)^1/2
SUMOWANIE/SZEREGÓW-PROBLEMY
DOKŁADNOŚĆ SUMOWANIA - nie ważne jak wiele szeregów zsumujemy, ważne jak dokładnie
e^-x = 1 - x + x^2/2! - x^3/3! + x^4/4! -x^5/5! + ...
Wzór na resztę z sumowania:
R_n = (f^(n+1)(ξ)h^(n+1))/(n+1)!
ξ ε[x_0, x_(0+h)]
Są błędy obciećia i błedy zaokrągleń
Kolejny przykład
e^-x = 1 - x + x^2/2! - x^3/3! + x^4/4! -x^5/5! + ...
https://docs.aws.amazon.com/lambda/latest/dg/python-programming-model-handler-types.html
ε = 10^-8
error = ε * 1 + ε *x + ε x^2/2! + εx^3/3! + εx^4/4! + εx^5/5! + ... = ε e^x
e^-x = e^-x ∓ εe^x = e^-x (1 ∓ ε e^2x)
e^-x = 1/e6x = 1/(1 + x/1! + x^2/2! + x^3/3! + ...)
1/(e^x ∓ ε e^x) = (e^-x)/(1 ∓ ε)
Niezależnie od tego czy sumujemy e^x czy e^-x błąd zaokrągleń jest ten sam.
Szereg jest zbieżny, jeżeli ciąg sum jest zbieżny
lim (n-> ∞) S_n - S(n-1) =0
Instalacje programów
Miktex, Texstudio
postscript -> najlepsze rysunki
Zad 1.
Rozważ sekwencję liczb x_i = a_0 + 0.1 r_i, (i=1,...,N), gdzie r_i jest liczbą losową w przedziale (-0,5, 0,5). Znajdż średnią z tych liczb przy użyciu wyrażenia:
a_1 = (∑_(i=1)^N)x_i/N
a_2 = a_0 + ((∑_(i=1)^N)(x_i-a_0)/N)
Oszacuj błąd zaokrąglennia w każdym przypadku. Użyj a_0 = 1.345 i N = 10^6 i porównaj wyniki z dokładnymi wartościami, komputer. Używa podwójną precyzję do zgromadzenia sumy.
INTERPOLACJA
Funkcja - relacja między dwoma zbiorami.
Nieznaną funkcję przybliżamy inną funkcją
y_1 = y(x_i)
(i = 1,2, ... , n)
APROKSYMACJA
y = Ax
f_i = f(x_1)
Matlab
Wielomiany są wyznaczane jako wektory:
[1 2 3 4 5] => y = u^4 + 2u^3 + 3u^2 + 4u + 5
Funkcja Rounge'go
1/(1+25x^2)
RÓŻNICZKOWANIE NUMERYCZNE
-RÓŻNICZKOWANIE NUMERYCZNE SKOŃCZONE
Rozwinięcie Taylora
f(x + h) = f(x) + hf'(x) + h^2/2!f''(x) + h^3/3! f'''(x) + ....
Jeśli zagęszczamy siatkę, to błąd pochodnej maleje h^2
dy/dx = f(x,y)
y(0) = y_0
y(x+h) = y(x) + hf(x,y(x))
y_(n+1) = y_n + f(x_n, y(x_n))
y_n = y(x_n)
ALGORYTMY REKURENCYJNE
Projekt algorytm rekurencyjne:
1. Podziel problem na dwie połówki
2. Rekurencyjnie rozwiąż każdą z nich oddzielnie
3. Połącz uzyskane wyniki w rozwiązanie problemu
Algorytm rekurencyjny wywołuje sam siebie (el. mniejszy).
Metody oszacowania wydajności algorytmu rekurencyjnego
a)przez indukcję
1. zgadnąć rozwiązanie
2. udowodnić indukcyjnie poprawność rozwiązania
b)z wykorzystaniem drzewa rekurencji: drzewo sumowania
c)w oparciu o twierdzenie o rekurencji uniwersalnej
T(n) = aT(n/b) + f(n)
-> Przeszukiewanie binarne : Wyszukaj x w uporządkowanej tablicy A, n-elementowej
A[1] =< A[2] =< ... =< A[n]
x?
A[i[= x
i?
1. devide sprawdź jak się x do wartości w połowie tab x< A[n/2] if(x<A[n/2])
2. conquar BinSearch (A[0], A[n/2])
else BinSearch (A[n/2 +1] ... A[n])
3. combine -> ⦰
T(n) = C -> T(n/2) = C -> T(n/4) = C .... ----- T(1) T(n) C*ln_2 = O(lg_n)
Potęgowanie liczby
Input: x, n
Output: x^n
Naivue: x^n = x*x...x*x
1. divide (x^(n/2))^2
2. conquer
x^n =
{x^(n/2) * x^(n/2) dla n parzystego
{x^((n-1)/2) * ((n-1)/2) x dla n nieparzystego
3. combine
T(n) = C *O(1) * lg_2n = O(lg n)
Algorytmy Sortowania: merge, quick
Merge-Sort (A, p,r)
if p<r
q = [(p+r)/2]
MERGE-SORT (A, p, q)
MERGE-SORT (A, q+1,r)
MERGE (A, p,q,r)
Rozw
A[1, ..., n]
1. Divide policz q =(n+1)/2
2. Conquer
MS(1, q)
MS (g+1, n)
3. Combine. Merge
for k = 1to n
if(i>n/2)
B[k] = A[j]
j++
if(j>n)
B[k] = A[i]
i++
if A[i] < A[j]
B[k] = A[i]
i++
else B[k] = A[j]
j++
T(n) = 2*T(n/2) + O(n) = O(nlogn) + O(n) = O(nlogn)
QuickSort (A, p, r)
1. if p< r
q = partion (A, p, r)
quicksort (A, p, q-1)
quicksort (A, q+1, r)
pivot
while dopóki i<j
++i, j++
A[1] < pivot OK
(A[2]) < pivot) NIE
A[n[ => pivot OK
(A[n-1] => pivot) NIE
swap (A[2], A[n-1])
int Partion (A[1, ..., n], p)
pivot = A[p]
swan (A[n[, pivot)
while (i<j)
repeat
++1
until (i==j; A[i] =< pivot)
repeat
--j
until (i=j; A[j] => pivot)
if (i<j)
swap (A[i], A[j])
swap(A[i], A[n])
return i
QS(A, 1,n)
A = programowanie
pivot = 'p'
i=0 j=n i=1 'e' << p
j = n-1 'i' >>'p'
j = n-2 'n' >>'p'
j = n-3 'a' >>'p'
j = n-4 'w' >>'p'
i=2 'r' << p
i=3 'o' << p
j = n-5 'o' >>'p'
j = n-6 'm' >>'p'
j = n-7 'a' >>'p'
j = n-8 'r' >>'p'
i=4 'g' << p
j = . n-9 i=j
T(n) = O(n) + T(k) + T(n-k) O(n^2)
O(nlogn)
k=n/2
wrrpoamoeanig
F(n)=
{0 n=0
{1 n=1
{F(n-2) + F(n-1) n>1
T(n) = T(n-1) + T(n-2) +1 = T(n-2) + T(n-3) + 1+ T(n-2) + 1 = 2 + 2*T(n-2) + T(n-3) >= 2+ 2*T(n-2) = 2(1+ T(n-2))
T(n) => 2 (1 + 2*(1+ T(n-4)) => 2^2(1 + T(n-4)) .... => 2^(n/2) (1 + T(1) (nieparzyste -> parzyste T(0)))
T(n) => 2^(n/2) = O(2^n) bo (2)^(1/2)<2
Aby obliczyć efektywność algorytmu rekurencyjnego musimy narysować drzewo rekurencyjne
Problem Fibonacciego
T(n) = T(n-1) + T(n-2) + 1
T(n) => (2)^(n/2) = O(2^n)
Dowód indukcyjny
Baza
T(1) = 1 (2)^(1/2)
T(2) = 1 (2)^(2/2) = 2
T(3) = 1 (2)^(3/2) = 2,8284
Założenie indukcyjne
k<n . T(k=>(2)^(k/2)
Teza
n: T(n)=> (2)^(n/2)
Dowód
T(n) = T(n-1) + T(n-2) + 1
>= 2^((n-1)/2) + 2^((n-2)/2) + 1
= (2^((n-1)/2)) (1 + (1/(2^(1/2)) + (1/(2^((n-1)/2))
>= (2^((n-1)/2)) (2^(1/2)) = (2^((n-1)/2)) => (2^(n/2))
(F_n F_(n-1)) (1 1) ^(n-1)
=
(F_(n-1) F_(n-2)) (1 0)
Dowód
(F_3 F_1) (2 1)
L = =
(F_2 F_1) (1 1)
(1 1)^2 (1 1) (1 1) (2 1)
P = = = .
(1 0) (1 0) (1 0) (1 1)
Zał. ind
k< n
(F_k F_(k-1)) (1 1)^(k-1)
=
(F_(k-1) F_(k-2)) (1 0)
Teza
(F_n F_(n-1)) (1 1)^(n-1)
=
(F_(n-1) F_(n-2)) (1 0)
(1 1)^(n-1) (1 1)^(n-2) (1 1)
P = =
(1 0) (1 0) (1 0)
Problem klocków na wieży Hanoi
T(n) = T(n-1) +1 + T(n-1) = 2T(n-1) +1 = 2^n -1
POPRAWNOŚC ALGORYTMU
1. Problem kasjera
C_pol = (50gr, 20gr, 10gr, 5gr, 2gr, 1gr)
77gr = 50gr, 20gr, 5gr, 2gr
I = (1, 1, 0, 1, 1, 0) = 4 monety
C_centy dolarowe = ( 25 cent, 20 cent, 10 cent, 5cent, 1 cent)
77cent = 3x 25 cent, 2x1cent
II = (3, 0, 0, 0, 2) = 5 moment
d -ilość dostępnych monet
BETTER CHANGE (M, c, d)
1. ... r <- M
2. ... for k<-1 to d
3. ... l_k <- r/c_k
4. ... r <- r- c_k * i_k
5. return (i_1, i_2, ...)
Ten algorytm jest niepoprawny bo jak chcemy 40 centów to on podsyła nam (25, 10, 5) a nie 2x20 centów.
Algorytm poprawny to "algorytm mięśniaka" - BRUTE FORCE CHANGE
zmłożoność (M^d)
MAPOWANIE RESTRYKCYJNE DNA
Multizbiór
Niech X to zbiór punktów na prostej: X = {x_1, x_2, ..., x_n}
Δx - multizbiorem zbioru X nazywamy zbiór wszystkich możliwych odległości pomiędzy dowolnymi punktami zbioru X, czyli
Δx = {|x_i - x_j|: x_i, x_j ∈ x}
np
x = {0, 2, 4, 7, 10}
0 2 4 7 10
0 x 2 4 7 10
2 x 2 5 8
4 x 3 6
7 x 3
10 x
Δx = {2, 2, 3, 3, 4, 5, 6, 7, 8, 10}
(5) 5*4
= ---- = 10
(2) 2
W tą stronę to nie problem. Problem jest kiedy mamy multizbior, a szukamy zbioru.
A = {a}
V ⊕ A = {V+a, a ∈ A}
ΔA = Δ(V ⊕ A)
Załóżmy, że mamy zbiory X i Y, takie że ΔX = ΔY to X i Y nazywamy homometrycznymi
np.
A = {0, 1, 3, 8, 9, 11, 12, 13, 15}
B = {0, 1, 3, 4, 5, 7, 12, 13, 15}
Def
U, V -> dowolne zbiory liczby całkowite
U ⊕ V = { U + V, u ∈ U, v ∈ V}
U ⊝ V = { U - V, u ∈ U, v ∈ V}
Δ(U ⊕ V) = Δ(U ⊝ V)
np.
U={6,7,9}
V = {-6, 2,6}
U ⊕ V = { 0,8, 12,1, 9, 13, 3, 11,15} = A
kolejny przykład
L = {2,3,5,7,8, 10}
(n)
|L| = = (n(n-1))/2 = 6
n = 4
x_1 = 0, x_2, x_3, x_4 = maxL
Liczenie wydajności
(M-2)
= ((M-2)(M-3)...(M-n))/(n-2)! <= M^(n-2) = O(M^n)
(n-2)
(|L|-2) (n)^(n-2)
= ((((n2)-2)...((n2)-n))/(n-2)! <= = n^(2(n-2)) = O(n^2n)
(n-2) (2)
|L| = (n(n-1))/2 = O(n^2)
partial digest
L ={2,3,5,7,8,10}
X = {0,10}
L={2,3,5,7,8}
L: y=8
Δ(y,x) = Δ(8, {0,10}) = {8,2}
x poprawiamy o ósemkę
x ={0,8,10}
zL usuwamy ósemkę
L = {3,5,7} -> dwie możliwości
LL: y=7
Δ (7 {0,8,10}) = {7,1,3} ZŁE
LR: y = 3
Δ (7 {0,8,10}) = {3,5,7} DOBRZE
L≠∅
x = {0,3,8,10}
wracamy do kroku L i zmieniamy na prawo
R: y = 2
Δ (2 {0,10}) = {2,8} DOBRZE
L = {3,5,7}
x = {0,2,10}
RL: y = 7
Δ (7 {0,2,10}) = {7,5,3} DOBRZE
x = {0,2,7,10}
RR: y = 3
Δ (3 {0,2,10}) = {3,1,7} ŹLE
DRZEWO ALGORYTMU:
Jest to algorytm rekurencyjny. Kończy się wraz z końcem zbioru.
Zad
Rozwiąż problem częściowego trawienia dla zbioru
L = {2,3,4,6,7,8,9,11,13,15}
Max )|15
x = {0,15}
y = 13
1. LL : Δ(13 {0,15}) = {13,2}
x = {0,13,15}
L = {2,3,4,6,7,8,9,11}
2. LL: STOP y =11
3. LR: y =4
Δ(4 {0,13,15}) = {4,9,11}
x = {0,4,13,15}
L = {3,6,7,8}
4. LRL: y =8
Δ(8 {0,4,13,15}) = {8,4,5,7}
Źle stop
5. LRR: y=7
Δ(7 {0,4,13,15}) = {7,3,6,8}
6. R: y =2
Δ(2 {0,15}) = {2,13} . DOBRZE
x = {0,2,15}
L = {3,4,6,7,8,9,11}
Δ(11 {0,2,15}) = {11,9,4} . DOBRZE
x = {0,2,11,15}
L = {3,6,7,8}
8. RLL: y =8
Δ(8 {0,2,11,15}) = {8,6,3,7} DOBRZE
9. RLR: y=7
Δ(7 {0,2,11,15}) = {7,5,4,6} DOBRZE
10. RR: y =4
Δ(4 {0,2,15}) = {4,2,11} ŹLE
Czas tego algorymut
T(n) = 2 + (n-1) + f(n)
T(n) = T(n-1) + f(n) = O(n^2)
MOTYWY REGULACYJNE W SEKWENCJACH DNA
zad.
Muszce owocówce dano gen powodujący chorobę i obserwowano, które geny uległy ekspresji.
TCGGGGATTTCC < - budowa sekwencji poprzędzającej gen który gwarantował przeżycie
NF_kB <- bialko przyczepiające się do w.w sekwencji i 'zachęca' polimerazę do dalszej aktywności
Szukamy motywów o długości l ( u nas 8) (l-metrów)
t: 7 sekwencji DNA
s(->) =(s_1, s_2,...,s_t) n
maximum (s) = tl = 7*8= 56 - najlepszy
minimum (s) = (t/4)l = 56/4 = 14 - najgorszy
Zad. Znaleźć l-mer w sekwencjach DNA i wyszukać zestaw ustawień s-ów, aby wynik był maksymalny
algorytm BRU?TE_FORCE_MOTIF_SEARCH
Mamy 5 sekwencji DNA
1. TGGGAAC
2. ACGGGGA
3. TCGGTAC
4. TTAGGGA
5. CCCGGAT
t=5
n=7
Szukamy 4-merów
I
s(n) = (1,1,1,1)
TGGG
ACGG
TCGG
TTAG
CCCG
A 1010
T 3100
C 1310
G 0135
TCGG
Score ((1,1,1,1) DNA) = 14
II
s(n) = (1,1,1,2)
TGGG
ACGG
TCGG
TTAG
CCGG
A 1010
T 3100
C 1300
G 0145
TCGG
Score ((1,1,1,2) DNA) = 15
itd .... aż do ...
s(n) = (2,4,3,4,3)
GGGA
GGGA
GGTA
GGGA
CGGA
A 0005
T 0010
C 1000
G 4540
GGGA
Score ((2,4,3,4,3) DNA) = 18
Odległość Hamminga
W = ATCG
TTAGGGA
xxx**xx
CCCGGAT
Dla:
TGGAAC
1 1 1 0=3
ACGGGGA
1 1 1 0=3
TCGGTAC
1 1 1 1 =4
TTAGGGA
1 1 1 0=3
CCCGGAT
1 1 0 0 = 2
wzorzec: "ATCG"
d(w(1,2,3,2,1)) = 3+3+4+3+2 = 15 -> odległość Hamminga
BRUTE_FORCE_MEDIAN_SEARCH (łańcuch medianowy)
v_1 = (AAAA)
TGGGAAC
ACGGGGA
TCGGTAC
TTAGGGA
CCCGGAT
Total_Dist((AAAA),{}) = 2+3+3+3+3 = 14
szukamy miejsca, gdzie jest najwięcej A i sumuejemy resztę które nie są A
v_2 = (AAAC)
Total_Dist((AAAC),{}) = 1+3+2+3+3 = 12
v_l = (GGGA)
Total_Dist((GGGA),{}) = 0+0+1+0+1 = 2
łańcuch konsensusu = łańcuch medianowy
max_sScore (s, DNA) = ∑_(j =1, ...,l) .M_p(s) (j) = w* = min_w Total_Dist(w, DNA)
Score (s(->), DNA) = ∑_(j =1) M_p(s) (j)
w jest łańcuchem konsensusu
d_M(w, s(->)) lt - Score (s(->), DNA)
DRZEWO BINARNE
korzeń
1-element
Motywy regulacyjne w sekwencjach DNA - dokończenie
All Leaves (L, k)
1. a<- (1, ..1)
2. while forever
3. output a
4. a <- Nextleaf (a,l,k)
5. if a = (1,1,...,1)
6. return
Nextleaf (a,L,k)
1. for i <- L to 1
2. if a_i <k
3. a_i <- a_i + 1
4. return a
5. a_i <-1
6. return a
K = {A, T, C,G}
L=3
a = ACG
NextLeaf(ACG, 3,4)
i=3
a_3(G<4)?NIE
a_3=A
i=2
a_2(C<4)?TAK
a_2=G return a = AGA
=>
NextLeaf(ACG, 3,4)
i=3
a_3(A<4)?TAK
a_3=AT return a = AGT
NextVertex (a,i,L,k)
1. if i< L
2. a_(i+1) <- 1
3. return(1, i+1)
4. else
5. for j <- to 1
6. if a_j < k
7. a_j <- a_j +1
8. return (a,j)
9. return (a, o)
k={A ,T , C, G}
l = 3
a . = ACG
NextVertex (ACG,3,3,4)
i=3 ?<3=L NIE
j=L=3
G = a_3 ?< 4 NIE
i=2
C<G TAK
a_2=G return (a,j) = (AG_,2)
NextVertex (AG_,2,3,4)
i=2<3 ? TAK
a_(i+1) = a_3 = 1 = A
return(1,3) = (AGA,3)
=>
NextVertex (AGA,3,3,4)
i=3<3 ? NIE
j=3
a_3 = A<K
a_3 = T ->(AGT,3)
return(1,3) = (AGA,3)
BruteForce MotifSearch(DNA, tn, l)
1. best score <- 0
2. for each (s_1, ... , s_t) from (1, .. , 1) to (n-l+1, ... , n-l+1)
3. if Score (s, DNA( > best score
4. best Score <- Score (s,DNA)
5. best Motif <- (s_1, ... , s_t)
6. if
ALGORYTMY ZACHŁANNE
Problem plecakowy
Problem wag i wartości
W_i
C_i
i=1,...,n
1, X_i =(0, 1, 0, ..., 1)
∑c_i x_i = MAX
∑w_i x_i < 15kg
Obliczamy cenę każdego kg w każdej paczce. Bierzemy te pierwsze najbardziej opłacalne tak, aby nie przekroczyć 15kg.
TASOWANIE
-odwrócenie -> najprostrza postać przetaasowaniu
p(odkąd, dokąd)
π = (π_1, π_2, π_3, ... , π_n)
p(i,j)
πp(i,j) = (π_1, π_2, π_3, ... ,π_(i-1), π_j ... ,π_(i+1), ,π_i, ,π_(j+1), ..., π_n)
Mamy dane dwa zbiory
π_1 = (1,2,4,3,7,5,6,8)
-> ?
π_2 = (3,4,5,2,1,8,6,7)
(zamieniamy kolejnkęod 1-6 na 6)
<- ρ_1 (1,6)
π_2 = (5,7,3,4,2,1,6,8) <- ρ_2 (1,3)
π_3 = (3,7,5,4,2,1,6,8) <- ρ_3 (2,4)
π_4 = (3,4,5,7,2,1,6,8) <- ρ_4 (4,8)
π_5 = (3,4,5,8,6,1,2,7) <- ρ_5 (4,7)
π_6 = (3,4,5,2,1,6,8,7) <- ρ_6 (6,7)
π_7 = (3,4,5,2,1,8,6,7)
ALGORYTMY ZACHŁANNE (dokończenie)
1. Algorytm najprostsze odwrócenie - poszerzanie prefiksu
123645
prefix - to co już jest na swoim miejscu 123
d(π) = 5 <= liczba permutacji
np.
0(82765143)9
b(π) = 6 => ρ(1,6)
0(15672843)9
b(π) = 5 => ρ(2,5)
0(12765843)9
b(π) = 4 => ρ(3 ,8)
0(12348567)9
b(π) = 3 => ρ(5,8)
0(12347658)9
b(π) = 2 => ρ(5,8)
0(12345678)9
b(π) = 0
b(π) = 5 (5 obróceń)
Ale można zrobić szybciej:
ρ(1,2) => ρ(2,8) => ρ(1,3) => ρ(1,4)
b(π) = 4
Algorytmy aproksymacyjne - szukają optymalnych wartości
GWARANCJA = A(π)/OPT(π) = wynik z algorytmu aproksymującego /prawdziwy wynik
A(π)/OPT(π) = 5/2 = 2,5
2,5 razy się pomyliśmy)
Przy algorytmach szukających minimum znajdziemy "większy" sposób.
MINIMALIZACJA OPT(π)=< A(π)
Przy algorytmach szukających maximum znajdziemy "mniejszy" sposób.
MAXYMALIZACJA OPT(π)=> A(π)
Dla
α = max(π) A(π)/OPT(π)
1/α = min(π) A(π)/OPT(π)
MINIMALIZACJA
α => A(π*)/OPT(π*) => 1
αOPT(π*) => A(π*)
A(π*) => OPT(π*) => 1/α * A(π*)
MAKSYMALIZACJA
1/α = min(π) A(π)/OPT(π)
A(π) => OPT(π) => α * A(π)
Zad 1 Dany jest algorytm maksymalizacyjny o gwarancji α = 4.
Dla pewnych danych D uzyskaliśmy wynik 12.
12 =< OPT(D) =< 4*12
Dysponujemy B minimlizacyjny o gwarancji α = 2. Dostaliżmy wynik 3,24. Co jest wartością prawdziwą?
3,24/2 =< OPT(D) =< 3,24
Zad 2. Poprawianie algorytmu sortowania przez odwrócenie
Def. Parę sąsiadujących elementów w permutacji π_i i π_(i+1) nazywamy uzgodnioną jeżeli π_i, π_(i+1) są kolejnymi liczbami. W przeciwnym wypadku parę π_i, π_(i+1) nazywamy punktem łamiącym.
(21345687)
13 punkt łamiący
68 punkt łamiący
Dopisujemuy 0 i 9
0(2134687)9
5 uzgodnionych
4 łamiące
0(12345678)9
b(id) = 0
oznaczenie b(π) => ilość punktów łamiących w π
Maksymalnie w jednej operacji możemy usunąć 2 punkty łamiące.
odległość
d(π) => b(π)/2
ALGORYTM
BreakPointReversalSort(π)
1. while b(π) > 0
2. Among all reversals, choose reversal , minim b(π*ρ)
3. π <- π * ρ
4. output ρ
5. return
Słaby punkt w tym algorytmie to występowanie rosnących sekwencji.
np.
456123
Taśmą w permutacji π nazywamy przedział pomiędzy kolejnymi punktami łamiącymi
0(41237658)9
Występują taśmy rosnące lub malejące.
Taśmę jednoelementową zawsze nazywamy malejącą, oprócz elementów brzegowych, które zawsze są rosnące.
Tw. Jeśli permutacja π zawiera taśmę malejącą, to istnieje odwrócenie ρ takie, które zmniejsza liczbę punktów łamiących, czyli
b(πρ) < b(π)
Z taśm malejących wybieramy tę, która zawiera najmniejszy element, np.
0(41237658)9
więc wybieramy 4, k=4
k-1 : 3, więc robimy ρ(2,4) i otrzymujemy
0(43217658)9
wybieramy 4321 i odwracamy ρ(1,4) i otrzymujemy:
0(12347658)9
Jeśli są same rosnące, wybieramy jakiś (obojętnie jaki) i go odwracamy. Najgorszy przypadek jest wtedy, gdy długość
d(π) = 2b(π)
Tw. Algorytm ImprovedBreakpointReversalSort jest algorytmem aproksymacyjny o długości 4
IBRS(π)
1. while b(π)>0
2. if π has a decreasing strip
3. Among all reversals, choose, reversal ρ minimaing b(πρ)
4. else
Choose a reversal ρ that flips an icreasing strip in π
5. π <- π * ρ
6. output ρ
7. return
Złożoność dla GreeedyMotifSearch (DNA, t,n,l)
θ(ln + tnl) =θ(n^2)
ALGORYTMY DYNAMICZNE: ODKRYWANIE PODOBIEŃSTW W SEKWENCJACH DNA
Algorytmy dynamiczne - wyznaczanie rozwiązania ogólngo poprzez złożenie rozwiązań podproblemów.
Algorytm rekurencyjne = )(2^n)
Algorytm dynamiczny = O(n)
1. Problem KASJERA
M- reszta, którą należy wydać
c(->) = (c_1, c_2, c_3, ..., c_d) -> momenty/nominaty
dla:
M=77, c(->) = (1,3,7)
OPT(M=77) = minimum z
{OPT(76) +1*1
{OPT(74) +1*3
{OPT(70) +1*7
czyli rozkładamy na mniejsze części i szukamy najlepszego
DRZEWO REKURENCYJNE
Złożoność = O(M^d) =O(Md)
2. Problem TURYSTY NA MANHATTANIE
(jak się poruszać, żeby zobaczyć najwięcej i się nie kręcić po ulicach)
Trzeba spojrzeć na problem pod względem grafu skierowanego
Źródło - punkt w grafie z którego można tylko wyjść
Zlew - punkt, którego można tylko wejść
-grafy skierowane i acykliczne, DAG porządek topologiczny)
Twierdzenie
Każdy skończony acykliczny graf skierowany ma conajmniej jeden zlew i jedno źródło.
Dowód
1. Każda ścieżka zbudowana jest z różnych wierzchołków (żaden się nie powtarza).
2. Graf jest skończony => każda ścieżka jest skończona
3. Istnieje ścieżka najdłuższa.
ALGORYTM DIJKSTRY
W(i,j) | V_1 V_2 V_3 V_4 V_5
____________________________
V_1 | 0 10 ∞ 5 ∞
V_2 | ∞ 0 1 2 ∞
V_3 | ∞ ∞ 0 ∞ 4
V_4 | ∞ 3 9 0 2
V_5 | ∞ ∞ 6 ∞ 0
Punkt startowy to pusta lista
L=∅, D -> wektor dł. aktualnej
_____________________ | V_2 | V_3 | V_4 | V_5
L=∅ D_i | 10 | ∞ | 5 | ∞
L={V_4} D_i | 8 | 14 | 5 | 7
L={V_4, V_5} D_i | 10 | 13 | 5 | 7
L={V_2, V_4, V_5} D_i | 10 | 9 | 5 | 7
wybierz najmniejszy
wybierz najmniejszy poza wcześniej wybranymi
Złożoność = O(n^3)
Nie możliwe jest znaleziemi maxa tym algorytmem
Trzeba liczyć dynamicznie.
Manhattantourist(w,w,n,m)
liczy kolejne możliwość i dopiero na koniec zna najlepszą.
WYDAJNOŚĆ : )(ilość krawędzi)
przechodzimy w postać liniową (krawędzie zawsze od mniejszego punktu do większego)
SEKWENCJE DNA
v(->): ATATAT
w(->): TATATA
nie zgadzają się pozycje
d_H(v(->), w(->)) = 6
Można zapisać inaczej
v(->): ATATAT
w(->): TATATA
Elemnty edycje:
-kasowanie
-wstawianie
-zamiana
Tablica podstawień dla aminokwasu:
-PAM (Percent Accepted Mutations) tablice Dayboff
-BLOSUM
PORÓWNUJEMY 2 SEKWENCJE
TGCATAT -> skasuj ost. T
TGCATA -> skasuj ost. A
TGCAT -> zamień C na G
TGGAT -> wstaw A na początek
ATGGAT -> zamień G na C
ATCCAT -> wstaw G na 5 pozycję
ATCCGAT
Można zrobić to szybciej to tylko przykład
Odległość edycyjna pomiędzy dwoma sekwencjami DNA nazywamy minimalną liczbę operacji edycji tj:
-wstawianie jednego symbolu
-kasowanie symbolu
-zmiana symbolu
Dopasowanie dwóch sekwencji DNA V (o n znakach) i W (o m znakach) nazywamy dwuwierszową macierz, w której pierwszy wiersz zawiera kolejne znaki V a drugi wiersz zawiera kolejne znaki W, przy czym w obu sekwencjach mogą być dowolnie rozmieszczane spacje.
np.
123 4 56 7
v(->): ATGTTAT
w(->):ATCGTAC
^- mutacja/edycja
v(->) AT^GTTAT^
w(->) ATCG^TA^C
1 insercja
2 delecja
Graf edycji
Globalne dopasowanie
-> Rozwiązanie Smith -Waterman
https://en.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorithm
ALGORYTMY DYNAMICZNE - ODKRYWANIE PODOBIEŃSTW MIĘDZY SEKWENCJAMI DNA
1. Problem najdłuższego wspólnego podciągu
Def
Podciągiem sekwencji DNA V = v_1v_2...v_n nazywamy uporządkowany ciąg jego znaków - niekoniecznie kolejnych
np.
ciąg:
n=7
v(->) = ATTGCAT
podciągi: TGAT
m=6
w(->) = GTATCG
wspólny podciąg dwóch ciągów:
TAT :
v(->) = (2,6,7)
w(->) = (2,3,4)
Twierdzenie:
d(v,w)
Z obrazków:
n=7
m=6
s=4
znajdź wspólny podciąg
=> 7+6-2*4=13-8=5
printLCS(b,v,i,j)
START(6,4
PrintLCS(b,v,6,4)
b_(6,4) = "↖"
PrintLCS(b,v,5,3) V_6 = A
b_(5,3) = "↑"
PrintLCS(b,v,4,3)
b_(4,3) = "↑"
PrintLCS(b,v,3,3)
b_(3,3) = "↖"
PrintLCS(b,v,2,2) V_3 = C
b_(2,2) = "←"
PrintLCS(b,v,2,1)
b_(2,1) = "↖"
PrintLCS(b,v,1,0)
return
print v_i, i =2
print v_2 v_2=T
podciąg: TCA
ALGORYTMY GRAFOWE SEKWENCJONOWANIE DNA I IDENTYFIKACJA BIAŁEK
graf pokrywa -> droga Hamiltona
SBH
Problem szachów
Cykl Eulera
Skończony graf spójny, w którym każdy wierzchołek jest stopnia parzystego..
V-> wierzchołki
E->krawędzie
S-> droga
W tym grafie jest cykl Eulera, bo każdy wierzchołek jest st. parzystego.
wg. algorytmu Fleury'ego
zaczynamy od 1
S=1,2,7,3,6,5,4,3,2,9,10,11,12,7,8,11,9,1
Złożoność algorytmu = O(|E|)
GRA SIR WILLIAMA HAMILTONA
Chcemy odwiedzić wszystkie wierzchołki tylko jeden raz.
PROBLME CYKLU HAMILTONA (Komiwgazera)
PROBLEM NAJKRÓTSZEJ DROGI
ALGORYTM DIJKSTRY
GRAFY I GENETYKA
GRAF INTERWAŁOWY
analiza asymptotyczna O()
1. zignoruj stałe wielkości zależne od maszyny
2. obserwuj jedynie wzrost przebiegu T(n) , gdy n->∞
Dla danej funkcji g(n) przez O(g(n)) oznaczany następujący wzór funkcji:
O(g(n))) = {f(n) : istnieją stałe c oraz n_0 takie, że O =< f(n) =<cg(n) dla wszystkich n=>n_0}
Wniosek: Notacja O() służy szacowaniu funkcji z góry
Np. Najgorszy przypadek Insertion-Sort
T(n) = ∑^n _(j=2) (j-1)c = ∑^n _(j=2) O(j) = O(n^2)
Zad 1. Przygotować program tworząc a następnie czytający, pliki tekstowe zawierające 10,100, 1000, 10 000, 100 000, 1 000 000 liczb zmiennoprzecinkowych.
Liczby mają być obliczane przez generator liczb losowych, a ich wartości mieścić się w zakresie [a, b0).
Porcje liczb zapisać do oddzielnych plików.
Zad 2. Ustalić czas wyklonania programu dla każdego z wyżej opisanych rozmiarów plików danych w postaci tabeli o następującej zawartości:
rozmiary danych | czas_tworzenia_danych | czas_pisania_do_pliku | czas_czytania_z_pliku
#include "sort.h"
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
#include <string>
#include <sstream>
#include <iomaninp>
#define zmierz_czas (X, wektor_czas) { czas = clock();
x;
czas = clock() - czas;
cout << "/t" << czas << "ms";
wektor_czasu = push_back(czas);
};
#define CZAS_tab(szer, czas) { plik <<" | |;
plik.width(szer);
plik << czas;
};
#define stworz_wektor (rozmiar) { v_db.resize (rozmiar); \
t_dbl = new double [rozmiar]; \
v_str.resize(rozmiar); \
v_int.resize (rozmiar); \
};
for (int i=0; i< rozmiar; ++i) v_dbl[i] = double_rand(0.0, 1.0);}
for (int i=0; i< rozmiar; ++i) t_dbl[i] = double_rand(0.0, 1.0);}
for (int i=0; i< rozmiar; ++i) v_str[i] = string_rand(15);}
for (int i=0; i< rozmiar; ++i) v_int[i] = int_rand(0, 100);}
#define stworz_nazwe (x, rozmiar, co , kiedy) { napis.str(" ");
napis << x << "_" << rozmiar << "_" << co"_" << kiedy".txt";
nazwa_pliku = napis.str();}
#define zapisz (rodzaj_sortowania, s, kiedy) {
stworz_nazwe (rodzaj_sterowania, n[k], "vec_double", kiedy); \
zapisz_wektor <double> (nazwa pliku.c_str(), v_dbl, s);\
stworz_nazwe (rodzaj_sterowania, n[k], "tab_double", kiedy); \
zapisz_tabl (nazwa pliku.c_str(), t_dbl, s);\
stworz_nazwe (rodzaj_sterowania, n[k], "vec_string", kiedy); \
zapisz_wektor <string> (nazwa pliku.c_str(), v_str, s);\
stworz_nazwe (rodzaj_sterowania, n[k], "vec_int", kiedy); \
zapisz_wektor <int> (nazwa pliku.c_str(), v_int, s); }
using namespace std.
double double_rtand (double fMin, double fMax) {
double f = (double) rand()/ RA?N?D_MAX;
return fMin + f * (fMax-fMin); }
int int_rand (int min, int max) {
return rand() % (max - min + 1) + min;
string string_rand (int rozmiar {
static const char alfabet [] = "abcdefghijklmnoprstuwxyz";
char * ret = new char [rozmiar + 1];
for (int i =0; i< rozmiar; ++i){
ret[i] = alfabet [ rand()%(sizeof(alfabet)-1)];}
ret [rozmiar] = NULL
return ret; }
Modułowa organizacja programu : pliki nagłówkowe + pliki ze źródłami
KISS: Keep It Simple Software
-projekt musi być prosty
-kod ma być czytelny
Stosować standardy kodowania:
dla plików źródłowych
przy nadawania nazw
wypracować styl i . konsekwentnie go stosować
Kompilator:
korzystać z kompilatora
zawsze doprowadzać do czystej kompilacji - żadnych ostrzeżeń
rozumieć ostrzężenia
Optymalizacja :
bez potrzeby nie optyamlizować
skupić się na złożoności obliczeniowej O()
// Przekopuj zdany plik do wektora łańcuchowego
#include <string>
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int main() {
vector<string> wektor; //wektor łańcuchów
iftream in("wektor.cpp"); // plik do przeczytania
string line;
while (getline(in, line))
wektor.push_back(line); //Dopisz linie na końcu wektora
//wydrukuj dodając numer wiersza
for(int i = 0; i < wektor.size() ; i++) // v.size() ilość elementów wektora
cout << i << ":" << wektor[i] << endl;
}
Zadania:
1. Poprawić swój program z poprzednich zajęć zgodnie z zasadami dobrego stylu:
a) wprowadzić moduły
b) Zlikwidować literały
c) Zlikwidować powtórzenia
d) Wprowadzić operacje rzutowania
2. Przygotować program czytający porcję 10, 100, 1 000, 10 000, 100 000, 1 000 000 linii z danego pliku do zmiennej klasy vector, a następnie wpisujący te porcje danych do różnych plików.
3. Przeprowadzić pomiar czasu wykonania zdania 2 w zależności od rozmiaru danych. Wyniki przedstawić w tabelce analogicznej do tej z zdania 1.
E)
Zmienna referencyjna (referencja):
-alias, czyli inna nazwa zmiennej
-alternatywa dla wskaźników przy przetwarzaniu zmiennych złożonych w funkcji rodzaju stałego wskaźnika do ziennej powiazanie jest na stałe
Tworzenie referencji (NOWE ZNACZENIE &):
int pies;
int ?& zswierze = pies; // to nie operator adresu, ale identyfikator typu
Oboie nazwy : zwierze i pies odnoszą się do tej samej zmiennej, tego samego fragmetntu pamięci. Powiązanie obu zmiennych jest trwałe.
Deklarując referencje trzeba ją zainicjować.
Klasyczną praktyką C++ jest przekazywanie do funkcji obiektów przez referencyjne.
Kiedy tylko można formalne parametry referencyjne należy deklarować jako stałe const, aby zabezpieczyć ssię przed nieporządną zmianą zawartości zmiennej.
Ostrożnie ze zwracaniem referencji. Unikać zwracania referencji do obszaru pamięci, który jest zwalniany po wykonaniu danej funkcji.
Metoda dziel i zwyciężaj
Divide-and-Conquer
-Divide the problem into a number of subproblems the are smaller instances of the same problem.
-Conquer the subproblems by solving them recursively. If the subproblem sizes are small enough, however, just solve the bubproblems in a straightforward manner
-Combine the solutions to the subproblems into the solution for the orginal problem.
MERGE-SORT(A, p, r)
1. if p<r
2. q=⎣(p+r)/2⎦
3. MERGE-SORT (A,p,q)
4. MERGE-SORT (A,q+1, r)
5. MERGE(A,p,q,r)
MERGE(A,p,qr)
1. n_1 = q - p + 1
2. n_2 = r - q
3. let L [1..n_1 + 1] and R[1..n_2 + 1] be new arrays
4. for i = 1 to n_1
5. L[i] = A [p + i - 1]
6. for j = 1 to n_2
7. R[j[ = A[q + j]
8. L[n_1 + 1] =∞
9. R[n_2 + 1] =∞
10. i = 1
11. j = 1
12. for k = p to r
13. if L[i] =< R[j]
14. A[k] = L[i]
15. i = i + 1
16. else A[k] = R[j]
17. j = j + 1
Using as a model, illustrate the operation odf merge sort on the array A = <3, 41, 52, 26, 38, 57, 9, 49>
Metoda dziel i zwyciężaj
dziel:
podziel tablicę A[p..r] na dwie podtablice A[p..q-1] i A[q+1..r] w taki sposób, aby każdy element tablicy A[p..q-1] był mniejszy lub równy A[q], który to jest mniejszy lub równy od dowolnego elementy w podtablicy A[q+1..r]
Zwyciężaj: rekurencyjnie zastosuj metodę podziału do podtablic
Kombinuj: tutaj już nie trzeba łączyć specjalnie
QUICKSORT(A, p, r)
1. if p < r
2. q = PARTITION(A,p,r)
3. QUICKSORT(A, p, q-1)
4. QUICKSORT(A, q+1,r)
PARTITION(A,p,r)
1. x = A[r]
2. i = p - 1
3. for j = p to r - 1
4. if A[j] =< x
5. i = i + 1
6. exchange A[i] with A[j]
7. exchange A[i+1] with A[r]
8. return i + 1
Zad
Zaimplementować procedury sortowania dług algorytmu Merge Sort i Quick Sort.
Wyznaczyć średnie efektywności tych procedur sortowania w operacjach na wektorze liczb zmiennoprzecinkowych
I) KOLEJKA
kolejka priorytetowa to struktura danych zawierająca elementy z kluczami, która pozwala na przeprowadzenie dwóch podstawowych operacji:
-wystawiania nowego elementu
oraz
-usuwania elementu o największej wartości klucza
class PriorityQueue{
private:
int * pq;
int n;
public:
PriorityQueue(int);
~PriorityQueue();
int empty() const;
void print() const;
void insert (int);
int get_max();
Dołączanie nowej wartości do kopca MAX
dołącz kolejny elementy tablicy jako liść do kopca
dopóki (element > ojciec (element) i element nie jest korzeniem)
zmień element z ojcem (element)
fixUP(A,L)
i=L
while (i>1 and A[parent(i)] < A[i])
zamien A[parent(i)] z A[i]
i=parent(i)
Zbuduj kopiec dla tablicy A:
A={5,3,17,10,84,19,6,22,9}
}
Zad I
Zaimplementować kolejkę priorytową na kopcu liczb int w dwóch wersjach: zwykłej tablicy i tablicy uporządkowanej kopcowo.
To znaczy:
a) zaprojektować odpowiednie klasy
b) zaimplementować metody klas
c) przygotować w main(testy sprawdzające poprawność obsługi kolejki priorytetowej
d) sprawdzić wydajność obu rozwiązań dla kolejki o rozmiarze N=100000
class PQ_HEAP {
private:
int *heap;
int n;
public:
PQ_HEAP(int );
~PQ_HEAP();
int empty () const;
void insert(int); /// poprawiona o fixUP()
void fixUP(int);
void print() const;
void DrukujKopiec() const;
void fixDown(int)
int get_max(); // poprawione o fixDOWN();
}
Kolejka priorytetowa - to struktura danych zawierająca elementy z kluczami, która pozwala na przeprowadzenie dwóch podstawowych operacji:
-wystawiania nowego elementu
oraz
-usuwanie wania elementu o największej wartości klucza
fixDOWN(i)
//naprawianie drzewa uporządkowanego kopcowo
//wszędzie za wyjątkiem korzenia
dpoóki(left(i) <= n)
j=left(i)
jeśli konflikt to zmień klucz węzła i z synem o większym kluczu
i = numer "wykorzystanego" syna
Max = ustaw ostatni liść w root zminiejsz wymiar kopca
fixDOWN(1) //naprawiaj kopiec od góry do dołu
Parent (i)
return [i/2]
Left (i)
return [2i]
Right (i)
return [2i + 1]
MaxHeap:
A[PARENT(i)} => A[i]
MAX_HEAPIFY(A,i)
l= LEFT (i)
r = RIGHT (i)
if (l =< A.heapsize && A[l] > A[i])
largest = l;
else
largest = i;
if (r =< A.heap_size && A[r] > A[largest])
largest = r;
if (largest ≠ i)
exchange A[i] with A[largest]
if (largest ≠ i)
exchange A[i] with A[largest]
MAX_HEAPIFY (A, largest)
J) Heapsort
Kolejka priorytetowa - to struktura danych zawierająca elementy z kluczami, która pozwala na przeprowadzenie dwóch podstawowych operacji:
-wystawiania nowego elementu
oraz
-usuwanie wania elementu o największej wartości klucza
dane + funkcje je obsługujące
class PriorityQueue{
private:
int * pq;
int n;
public:
PriorityQueue (int);
~PriorityQueue();
int empty() const;
void print() const;
void insert (int);
int get_max ();
}
class PQ_HEAP{
private:
int * heap;
int n;
public:
PQ_HEAP(int);
~PQ_HEAP();
int empty() const;
void insert (int); //poprawiona o fixUP()
void fixUP(int);
void print() const;
void DrukujKopiec() const;
void fixDown(int);
int get_max (); // poprawione o fixDOWN();
}
#ifndef KOPIEC_H
#define KOPIEC_H
void heapsort(std::string *tab, int);
class HEAP{
private:
std::string *kopiec;
int n;
void fixUp(int);
void fixDown(int);
int parent(int i) { return (i-1)/2;}
int left(int i) { return (2*i+1);}
int right(int i) { return (2*i+2);}
public:
PQ_HEAP(int);
~PQ_HEAP();
int empty() ;
void insert (std::string);
void print() ;
std::string getMax (); /
}
#endif
Możliwości deklaracji zmiennej będącej tablicą tablic znakowych
char** Tablica_Łańcuchów_C_O_Dynamicznie_Przydzielanej_Pamięci;
char* Tablica_20_Łańcuchów_C[20];
char** Tablica_Łańcuchów_STL_O_Dynamicznie_Przydzielanej_Pamięci;
char* Tablica_20_Łańcuchów_STL[20];
vector<string> Wektor_STL_Łańcuchów_STL_O_Dynamicznie_Przydzialanej_Pamięci;
private:
std::string *kopiec;
->
HEAP::HEAP (int maxN)
{kopiec= new std::string[maxN]; n=0;}
Zadanie
-Zaimplementować HeapSort() wykorzystując ideę kolejki priorytetowej na kopcu.
Sort mają być łańcuchy.
-Zaimplementować funkcję operujące na funkcjach - wykorzystać wskaźniki do funkcji sortujących zamiast nużącego powtarzania tego samego kodu.
Rozważyć możliwość sortowania:
a) tablicy łańcuchów C
b) tablicy łańcuchów STL
c) wektora łańcuchów
Nazwy funkcji jako parametry funkcji
Takie same parametry, taki sam wynik, ale różne nazwy funkcji operującej.
void BubleSort (vector<string> &);
void InsertSort (vector<string> &);
void SelectSort (vector<string> &);
void MergeSort (vector<string> &);
void QuickSort (vector<string> &);
Konstrukcja wekora nazw funkcji:
typedef void (*wskaznik_do_sortu) (vector<string> &); // typ na wskaźnik do funkcji o parametrze vector<string>
void sortuj (wskaznik_do_sortu funkcja_sortu, vector<string> & wektor); // wskaźnik do funkcji, parametr przekazawany do funkcji
wskaznik_do_sortuj sorty[]={BubbleSort, SelectSort, InsertSort, MergeSort, QuickSort};
l) Lista. Zbiory dynamiczne
a) Zbiór statyczny a zbiór dynamiczny
*S,n
Zbiór S statycznie jako tablica:
1. wskażnik do początku tablicy *S
2. rozmiar tablicy n
*S
Zbiór dynamiczny:
1. elementy o zafiksowanej strukturze "wewnętrznej pamięci co dalej"
2. wskaźnik *S do pierwszego elementu
b) Operations on dynamic sets
Operations on a dynamic set can be group[ed into two categories: queries, which simply return information about the set, and modifying operations, which change the set. Here is a list of typical operations. any specific application will usually require only a few of these to be implemented.
SEARCH(S, k) - A query that, given a set S and a key value k, returns a pointer x to an element in S such that x, key = k, or NIL if no such element beloongs to S.
INSERT(S, x) - A modifying operation that arguments the set S with the element pointed to by x. We usually assume that any attributes in element x needed by the set implementation have already been initialized.
DELET(S, x) - A modifying operation that, given a pointer x to an element in the set S, removes x from S. (Note that this operation takes a pointer to an element x, not a key value.)
MINIMUM(S) - A query on a totally ordered set S that returns a pointer to the element of S with the smallest key.
MAXIMUM(S) - A query on a totally ordered set S that returns a pointer to the element of S with the largest key.
SUCCESSOR(S, x) - A query that, given an element x whose key is from a totally ordered set S, returns a pointer to the next largest element in S, or NIL if x is the maximum element.
PREDECESSOR(S, x) - A query that, given an element x whose key is from a totally ordered set S, returns a pointer to the next smaller element in S, or NIL if x is the minimum element.
c) Stos:
abstrakcyjny typ danych zawierający dwie podstawowe operacje: umieszczenie na stosie nowego elementu: insert -> push
zdejmowanie ze stosu elementu ostatnio umieszczonego: delete -> pop
Implementacja tablicowa stosu
STACK-EMPTY(S)
if S.top == 0
return TRUE
else return FALSE
PUSH(S,x)
S.top = S.top + 1
S[S.top] = x
POP(S)
if STACK-EMPTY(S)
error "underflow"
else S.top = S.top - 1
return S[S.top + 1]
d) Kolejka: QUEUE
abstrakcyjny typ danych zawierający dwie podstawowe operacje:
dokładnie nowego elementu na koniec kolejki: insert -> enqueue
obsługiwanie pierwszego elementu kolejki: delete -> dequeue
Implementacja tablicowa kolejki
ENQUEUE(Q, x)
Q[Q.tail] =x
if Q.tail == Q.length
Q.tail = 1
else Q.tail = Q.tail + 1
DEQUEUE(Q, x)
x = Q[Q.head]
if Q.head == Q.length
Q.head = 1
else Q.head = Q.head + 1
return x
e) Lista:
Zbiór danych uporządkowanych liniowo, przy czym porządek jest określony poprzez wskaźniki.
LIST-SEARCH(L, k)
x = L.head
while x ≠ NIL and x.key ≠ k
x = x.next
return x
LIST-INSERT(L, x)
x.next = L.head
if L. head ≠ NIL
L.head.prv = x
L.head = x
x.prev = NIL
LIST-DELETE(L, x)
if x.prev ≠ NIL
x.prev.next = x.next
else L.head = x.next
if x.next ≠ NIL
x.next.prev = x.prev
Lista jednokierunkowa
head -> key -> key -> NULL
kod C++ odpowiadający definicji listy jednokierunkowej.
struct node {
int key;
node * next;
};
typedef node * link;
link a = new node;
Korzystając z list pamiętać o rezerwowaniu pamięci
W C++ struktura jest klasą o wszystkich polach publicznych. Można / trzeba ją zainicjować.
struct node {
int key;
node * next;
node (int x, node * t) // konstruktor
{ key = x; next =t;}
};
typedef node * link;
link a = new node(x,t);
Tworzymy listę przechowującą n kolejnych liczb całkowitych
Konstruktor tworzy kolejny eleent tak, by wskazywał na początek listy.
efekt: lista cykliczna (zamknięta w kole)
link start = new node (1,start); // start to wskaźnik na obszar
//pamięci dla węzła, który przechowuje wartość 1 i wskazuje na siebie
link x = start; //x to wskaźnik na węzeł start
for(i=2; i<=n; i++) {
x -> next = new node (i, start);
x = x -> next;
}
cout << "\n wybijamy co m-tego \n";
while (x != x -> next) {
for (i=1; i<m; i++) x =x -> next
x -> next = x -> next-> next;
Problem Flawiusza
Zbuduj listę cykliczną o długości n, której każdy węzeł wskazuje na osobę stojącą po lewej stronie. Kasuj cyklicznie co ,-tego sąsiada. Podaj numer zwycięskiego węzła.
STOS_INT liczba();
class STOS_INT{
private:
struct node
{ int key;
node * next;
node (int x, node * t)
{key = x
next = t;}
};
typedef node *link;
link head;
public:
STOS_INT(int) ; {head=NULL;};
~STOS_INT() ;
int empty() const; {return head == NULL;}l
void push (int item); {head = new node(item, head); };
int pop();
void print() const;
};
Zadanie:
-Wykorzystać listę cykliczną do rozwiązania problemu Flawiusza
-Opracować sumowanie i odejmowanie liczb dodatnich o dowolnej długości. Skorzystać ze stosu liczb całkowitych do reprezentacji długich liczb. Stos zaimplementować na liście jednokierunkowej.
z) Drzewo przeszukiwań binarnych (BST)
najgorszy wpadek O (login)
drzewo z jedną gałęzią o długości n - najgorszym przypadku (O(n)
lewe poddrzewo węzła x : klucz[y] =< kulcz[x]
prawe poddrzewo węzła x : klucz [x] =< klucz [y]
SZUKAJ (x, k) // O(n)
if (x =NULL) lub (k = klucz[x])
return x
if k < klucz [x]
return SZUKAJ (lewy [x], k)
else return SZUKAJ (prawy[x[, k)
SZUKAJ (x,k)
while (x <> NULL)i(k<> klucz [x])
if k< klucz [x]
x = lewy [x]
else x = prawy [x]
return x
MINIMUM(x)
while (lewy [x] <> NULL)
x =lewy [x]
return x
MAKSIMUM(x)
while (prawy [x] <> NULL)
x =prawy [x]
return x
struct node {
int data;
node * left;
node * right;
}
struct node {
char op; //*, +, -
int niem?;
node * left, * right;
}
-> Odwiedzenie wierzchołka p wiąże się z:
a) if (p -> left ! = 0 && p -> data - p -> data<2)
p -> left -> data += 2;
b) if (p -> left ==0)
p -> right = 0
Szukaj (x,k)
if (x = NULL) lub (k = klucz[x])
return x;
if k < klucz [x]
return Szukaj(lewy[x], k)
else return Szukaj(prawy[x], k)
Szukaj (x,k)
while (x <> NULL) i (k <> klucz [x])
cout.self (ios::fixed, ios:: floatfield)
//////////////////////////////////
Books:
1. http://bioinformaticsinstitute.ru/sites/default/files/an_introduction_to_bioinformatics_algorithms_-_jones_pevzner.pdf
2. https://labs.xjtudlc.com/labs/wldmt/reading%20list/books/Algorithms%20and%20optimization/Introduction%20to%20Algorithms.pdf
1. Cyfry znaczące (te cyfry, ktore wiemy, że są dobre)
2. Precyzja i dokładność
3. Błędy (np. błędy metod numerycznych)
NETLIB (kolekcja bibliotek), NAG, LAPAC
Matematyczne komercyjne rozwiązania:
-Macsynia
-Maple
-Mathematica
-Mathcad
Klasyfikacja problemów numerycznych - GAMS
Przypomnij: wzór Taylor'a i szereg Taylor'a
(a_11 - λ) x_1 + a_12x_2 = 0
a_21x_1 + (a_22 - λ) x_2 = 0
APROKSYMACJA I INTERPOLACJA
INTERPOLACJA (szukamy funkcji, która przechodzi przez dane punkty układu współrzędnych)
APROKSYMACJA (szukamy funkcji która nie przechodzi przez dane punkty, ale żeby była możliwie jak najbliżej)
- RÓWNANIA RÓZNICZKOWE (bd. potem robić w MAthematice)
-CAŁKOWANIE NUMERYCZNE (stosujemy kwadratury)
-OPTYMALIZACJA (funkcja minimum itd.)
Błędy w obliczeniach z zaokrąglaniem
wzory Wieta
ax^2 + bx + c = 0
a (x - x_1)(x - x_2) = 0
a (x^2 - (x_1 + x_2) x + x_1x_2) = 0
ax_1x_2 = c
|z| = (x^2 + y^2)^1/2 = x(1 + (y/x)^2)^1/2
SUMOWANIE/SZEREGÓW-PROBLEMY
DOKŁADNOŚĆ SUMOWANIA - nie ważne jak wiele szeregów zsumujemy, ważne jak dokładnie
e^-x = 1 - x + x^2/2! - x^3/3! + x^4/4! -x^5/5! + ...
Wzór na resztę z sumowania:
R_n = (f^(n+1)(ξ)h^(n+1))/(n+1)!
ξ ε[x_0, x_(0+h)]
Są błędy obciećia i błedy zaokrągleń
Kolejny przykład
e^-x = 1 - x + x^2/2! - x^3/3! + x^4/4! -x^5/5! + ...
https://docs.aws.amazon.com/lambda/latest/dg/python-programming-model-handler-types.html
ε = 10^-8
error = ε * 1 + ε *x + ε x^2/2! + εx^3/3! + εx^4/4! + εx^5/5! + ... = ε e^x
e^-x = e^-x ∓ εe^x = e^-x (1 ∓ ε e^2x)
e^-x = 1/e6x = 1/(1 + x/1! + x^2/2! + x^3/3! + ...)
1/(e^x ∓ ε e^x) = (e^-x)/(1 ∓ ε)
Niezależnie od tego czy sumujemy e^x czy e^-x błąd zaokrągleń jest ten sam.
Szereg jest zbieżny, jeżeli ciąg sum jest zbieżny
lim (n-> ∞) S_n - S(n-1) =0
Instalacje programów
Miktex, Texstudio
postscript -> najlepsze rysunki
Zad 1.
Rozważ sekwencję liczb x_i = a_0 + 0.1 r_i, (i=1,...,N), gdzie r_i jest liczbą losową w przedziale (-0,5, 0,5). Znajdż średnią z tych liczb przy użyciu wyrażenia:
a_1 = (∑_(i=1)^N)x_i/N
a_2 = a_0 + ((∑_(i=1)^N)(x_i-a_0)/N)
Oszacuj błąd zaokrąglennia w każdym przypadku. Użyj a_0 = 1.345 i N = 10^6 i porównaj wyniki z dokładnymi wartościami, komputer. Używa podwójną precyzję do zgromadzenia sumy.
INTERPOLACJA
Funkcja - relacja między dwoma zbiorami.
Nieznaną funkcję przybliżamy inną funkcją
y_1 = y(x_i)
(i = 1,2, ... , n)
APROKSYMACJA
y = Ax
f_i = f(x_1)
Matlab
Wielomiany są wyznaczane jako wektory:
[1 2 3 4 5] => y = u^4 + 2u^3 + 3u^2 + 4u + 5
Funkcja Rounge'go
1/(1+25x^2)
RÓŻNICZKOWANIE NUMERYCZNE
-RÓŻNICZKOWANIE NUMERYCZNE SKOŃCZONE
Rozwinięcie Taylora
f(x + h) = f(x) + hf'(x) + h^2/2!f''(x) + h^3/3! f'''(x) + ....
Jeśli zagęszczamy siatkę, to błąd pochodnej maleje h^2
dy/dx = f(x,y)
y(0) = y_0
y(x+h) = y(x) + hf(x,y(x))
y_(n+1) = y_n + f(x_n, y(x_n))
y_n = y(x_n)
ALGORYTMY REKURENCYJNE
Projekt algorytm rekurencyjne:
1. Podziel problem na dwie połówki
2. Rekurencyjnie rozwiąż każdą z nich oddzielnie
3. Połącz uzyskane wyniki w rozwiązanie problemu
Algorytm rekurencyjny wywołuje sam siebie (el. mniejszy).
Metody oszacowania wydajności algorytmu rekurencyjnego
a)przez indukcję
1. zgadnąć rozwiązanie
2. udowodnić indukcyjnie poprawność rozwiązania
b)z wykorzystaniem drzewa rekurencji: drzewo sumowania
c)w oparciu o twierdzenie o rekurencji uniwersalnej
T(n) = aT(n/b) + f(n)
-> Przeszukiewanie binarne : Wyszukaj x w uporządkowanej tablicy A, n-elementowej
A[1] =< A[2] =< ... =< A[n]
x?
A[i[= x
i?
1. devide sprawdź jak się x do wartości w połowie tab x< A[n/2] if(x<A[n/2])
2. conquar BinSearch (A[0], A[n/2])
else BinSearch (A[n/2 +1] ... A[n])
3. combine -> ⦰
T(n) = C -> T(n/2) = C -> T(n/4) = C .... ----- T(1) T(n) C*ln_2 = O(lg_n)
Potęgowanie liczby
Input: x, n
Output: x^n
Naivue: x^n = x*x...x*x
1. divide (x^(n/2))^2
2. conquer
x^n =
{x^(n/2) * x^(n/2) dla n parzystego
{x^((n-1)/2) * ((n-1)/2) x dla n nieparzystego
3. combine
T(n) = C *O(1) * lg_2n = O(lg n)
Algorytmy Sortowania: merge, quick
Merge-Sort (A, p,r)
if p<r
q = [(p+r)/2]
MERGE-SORT (A, p, q)
MERGE-SORT (A, q+1,r)
MERGE (A, p,q,r)
Rozw
A[1, ..., n]
1. Divide policz q =(n+1)/2
2. Conquer
MS(1, q)
MS (g+1, n)
3. Combine. Merge
for k = 1to n
if(i>n/2)
B[k] = A[j]
j++
if(j>n)
B[k] = A[i]
i++
if A[i] < A[j]
B[k] = A[i]
i++
else B[k] = A[j]
j++
T(n) = 2*T(n/2) + O(n) = O(nlogn) + O(n) = O(nlogn)
QuickSort (A, p, r)
1. if p< r
q = partion (A, p, r)
quicksort (A, p, q-1)
quicksort (A, q+1, r)
pivot
while dopóki i<j
++i, j++
A[1] < pivot OK
(A[2]) < pivot) NIE
A[n[ => pivot OK
(A[n-1] => pivot) NIE
swap (A[2], A[n-1])
int Partion (A[1, ..., n], p)
pivot = A[p]
swan (A[n[, pivot)
while (i<j)
repeat
++1
until (i==j; A[i] =< pivot)
repeat
--j
until (i=j; A[j] => pivot)
if (i<j)
swap (A[i], A[j])
swap(A[i], A[n])
return i
QS(A, 1,n)
A = programowanie
pivot = 'p'
i=0 j=n i=1 'e' << p
j = n-1 'i' >>'p'
j = n-2 'n' >>'p'
j = n-3 'a' >>'p'
j = n-4 'w' >>'p'
i=2 'r' << p
i=3 'o' << p
j = n-5 'o' >>'p'
j = n-6 'm' >>'p'
j = n-7 'a' >>'p'
j = n-8 'r' >>'p'
i=4 'g' << p
j = . n-9 i=j
T(n) = O(n) + T(k) + T(n-k) O(n^2)
O(nlogn)
k=n/2
wrrpoamoeanig
F(n)=
{0 n=0
{1 n=1
{F(n-2) + F(n-1) n>1
T(n) = T(n-1) + T(n-2) +1 = T(n-2) + T(n-3) + 1+ T(n-2) + 1 = 2 + 2*T(n-2) + T(n-3) >= 2+ 2*T(n-2) = 2(1+ T(n-2))
T(n) => 2 (1 + 2*(1+ T(n-4)) => 2^2(1 + T(n-4)) .... => 2^(n/2) (1 + T(1) (nieparzyste -> parzyste T(0)))
T(n) => 2^(n/2) = O(2^n) bo (2)^(1/2)<2
Aby obliczyć efektywność algorytmu rekurencyjnego musimy narysować drzewo rekurencyjne
Problem Fibonacciego
T(n) = T(n-1) + T(n-2) + 1
T(n) => (2)^(n/2) = O(2^n)
Dowód indukcyjny
Baza
T(1) = 1 (2)^(1/2)
T(2) = 1 (2)^(2/2) = 2
T(3) = 1 (2)^(3/2) = 2,8284
Założenie indukcyjne
k<n . T(k=>(2)^(k/2)
Teza
n: T(n)=> (2)^(n/2)
Dowód
T(n) = T(n-1) + T(n-2) + 1
>= 2^((n-1)/2) + 2^((n-2)/2) + 1
= (2^((n-1)/2)) (1 + (1/(2^(1/2)) + (1/(2^((n-1)/2))
>= (2^((n-1)/2)) (2^(1/2)) = (2^((n-1)/2)) => (2^(n/2))
(F_n F_(n-1)) (1 1) ^(n-1)
=
(F_(n-1) F_(n-2)) (1 0)
Dowód
(F_3 F_1) (2 1)
L = =
(F_2 F_1) (1 1)
(1 1)^2 (1 1) (1 1) (2 1)
P = = = .
(1 0) (1 0) (1 0) (1 1)
Zał. ind
k< n
(F_k F_(k-1)) (1 1)^(k-1)
=
(F_(k-1) F_(k-2)) (1 0)
Teza
(F_n F_(n-1)) (1 1)^(n-1)
=
(F_(n-1) F_(n-2)) (1 0)
(1 1)^(n-1) (1 1)^(n-2) (1 1)
P = =
(1 0) (1 0) (1 0)
Problem klocków na wieży Hanoi
T(n) = T(n-1) +1 + T(n-1) = 2T(n-1) +1 = 2^n -1
POPRAWNOŚC ALGORYTMU
1. Problem kasjera
C_pol = (50gr, 20gr, 10gr, 5gr, 2gr, 1gr)
77gr = 50gr, 20gr, 5gr, 2gr
I = (1, 1, 0, 1, 1, 0) = 4 monety
C_centy dolarowe = ( 25 cent, 20 cent, 10 cent, 5cent, 1 cent)
77cent = 3x 25 cent, 2x1cent
II = (3, 0, 0, 0, 2) = 5 moment
d -ilość dostępnych monet
BETTER CHANGE (M, c, d)
1. ... r <- M
2. ... for k<-1 to d
3. ... l_k <- r/c_k
4. ... r <- r- c_k * i_k
5. return (i_1, i_2, ...)
Ten algorytm jest niepoprawny bo jak chcemy 40 centów to on podsyła nam (25, 10, 5) a nie 2x20 centów.
Algorytm poprawny to "algorytm mięśniaka" - BRUTE FORCE CHANGE
zmłożoność (M^d)
MAPOWANIE RESTRYKCYJNE DNA
Multizbiór
Niech X to zbiór punktów na prostej: X = {x_1, x_2, ..., x_n}
Δx - multizbiorem zbioru X nazywamy zbiór wszystkich możliwych odległości pomiędzy dowolnymi punktami zbioru X, czyli
Δx = {|x_i - x_j|: x_i, x_j ∈ x}
np
x = {0, 2, 4, 7, 10}
0 2 4 7 10
0 x 2 4 7 10
2 x 2 5 8
4 x 3 6
7 x 3
10 x
Δx = {2, 2, 3, 3, 4, 5, 6, 7, 8, 10}
(5) 5*4
= ---- = 10
(2) 2
W tą stronę to nie problem. Problem jest kiedy mamy multizbior, a szukamy zbioru.
A = {a}
V ⊕ A = {V+a, a ∈ A}
ΔA = Δ(V ⊕ A)
Załóżmy, że mamy zbiory X i Y, takie że ΔX = ΔY to X i Y nazywamy homometrycznymi
np.
A = {0, 1, 3, 8, 9, 11, 12, 13, 15}
B = {0, 1, 3, 4, 5, 7, 12, 13, 15}
Def
U, V -> dowolne zbiory liczby całkowite
U ⊕ V = { U + V, u ∈ U, v ∈ V}
U ⊝ V = { U - V, u ∈ U, v ∈ V}
Δ(U ⊕ V) = Δ(U ⊝ V)
np.
U={6,7,9}
V = {-6, 2,6}
U ⊕ V = { 0,8, 12,1, 9, 13, 3, 11,15} = A
kolejny przykład
L = {2,3,5,7,8, 10}
(n)
|L| = = (n(n-1))/2 = 6
n = 4
x_1 = 0, x_2, x_3, x_4 = maxL
Liczenie wydajności
(M-2)
= ((M-2)(M-3)...(M-n))/(n-2)! <= M^(n-2) = O(M^n)
(n-2)
(|L|-2) (n)^(n-2)
= ((((n2)-2)...((n2)-n))/(n-2)! <= = n^(2(n-2)) = O(n^2n)
(n-2) (2)
partial digest
L ={2,3,5,7,8,10}
X = {0,10}
L={2,3,5,7,8}
L: y=8
Δ(y,x) = Δ(8, {0,10}) = {8,2}
x poprawiamy o ósemkę
x ={0,8,10}
zL usuwamy ósemkę
L = {3,5,7} -> dwie możliwości
LL: y=7
Δ (7 {0,8,10}) = {7,1,3} ZŁE
LR: y = 3
Δ (7 {0,8,10}) = {3,5,7} DOBRZE
L≠∅
x = {0,3,8,10}
wracamy do kroku L i zmieniamy na prawo
R: y = 2
Δ (2 {0,10}) = {2,8} DOBRZE
L = {3,5,7}
x = {0,2,10}
RL: y = 7
Δ (7 {0,2,10}) = {7,5,3} DOBRZE
x = {0,2,7,10}
RR: y = 3
Δ (3 {0,2,10}) = {3,1,7} ŹLE
DRZEWO ALGORYTMU:
Jest to algorytm rekurencyjny. Kończy się wraz z końcem zbioru.
Zad
Rozwiąż problem częściowego trawienia dla zbioru
L = {2,3,4,6,7,8,9,11,13,15}
Max )|15
x = {0,15}
y = 13
1. LL : Δ(13 {0,15}) = {13,2}
x = {0,13,15}
L = {2,3,4,6,7,8,9,11}
2. LL: STOP y =11
3. LR: y =4
Δ(4 {0,13,15}) = {4,9,11}
x = {0,4,13,15}
L = {3,6,7,8}
4. LRL: y =8
Δ(8 {0,4,13,15}) = {8,4,5,7}
Źle stop
5. LRR: y=7
Δ(7 {0,4,13,15}) = {7,3,6,8}
6. R: y =2
Δ(2 {0,15}) = {2,13} . DOBRZE
x = {0,2,15}
L = {3,4,6,7,8,9,11}
7. RL: y =11
Δ(11 {0,2,15}) = {11,9,4} . DOBRZE
x = {0,2,11,15}
L = {3,6,7,8}
8. RLL: y =8
Δ(8 {0,2,11,15}) = {8,6,3,7} DOBRZE
9. RLR: y=7
Δ(7 {0,2,11,15}) = {7,5,4,6} DOBRZE
10. RR: y =4
Δ(4 {0,2,15}) = {4,2,11} ŹLE
Czas tego algorymut
T(n) = 2 + (n-1) + f(n)
T(n) = T(n-1) + f(n) = O(n^2)
MOTYWY REGULACYJNE W SEKWENCJACH DNA
zad.
Muszce owocówce dano gen powodujący chorobę i obserwowano, które geny uległy ekspresji.
TCGGGGATTTCC < - budowa sekwencji poprzędzającej gen który gwarantował przeżycie
NF_kB <- bialko przyczepiające się do w.w sekwencji i 'zachęca' polimerazę do dalszej aktywności
Szukamy motywów o długości l ( u nas 8) (l-metrów)
t: 7 sekwencji DNA
s(->) =(s_1, s_2,...,s_t) n
maximum (s) = tl = 7*8= 56 - najlepszy
minimum (s) = (t/4)l = 56/4 = 14 - najgorszy
Zad. Znaleźć l-mer w sekwencjach DNA i wyszukać zestaw ustawień s-ów, aby wynik był maksymalny
algorytm BRU?TE_FORCE_MOTIF_SEARCH
Mamy 5 sekwencji DNA
1. TGGGAAC
2. ACGGGGA
3. TCGGTAC
4. TTAGGGA
5. CCCGGAT
t=5
n=7
Szukamy 4-merów
I
s(n) = (1,1,1,1)
TGGG
ACGG
TCGG
TTAG
CCCG
A 1010
T 3100
C 1310
G 0135
TCGG
Score ((1,1,1,1) DNA) = 14
II
s(n) = (1,1,1,2)
TGGG
ACGG
TCGG
TTAG
CCGG
A 1010
T 3100
C 1300
G 0145
TCGG
Score ((1,1,1,2) DNA) = 15
itd .... aż do ...
s(n) = (2,4,3,4,3)
GGGA
GGGA
GGTA
GGGA
CGGA
A 0005
T 0010
C 1000
G 4540
GGGA
Score ((2,4,3,4,3) DNA) = 18
Odległość Hamminga
W = ATCG
TTAGGGA
xxx**xx
CCCGGAT
Dla:
TGGAAC
1 1 1 0=3
ACGGGGA
1 1 1 0=3
TCGGTAC
1 1 1 1 =4
TTAGGGA
1 1 1 0=3
CCCGGAT
1 1 0 0 = 2
wzorzec: "ATCG"
d(w(1,2,3,2,1)) = 3+3+4+3+2 = 15 -> odległość Hamminga
BRUTE_FORCE_MEDIAN_SEARCH (łańcuch medianowy)
v_1 = (AAAA)
TGGGAAC
ACGGGGA
TCGGTAC
TTAGGGA
CCCGGAT
Total_Dist((AAAA),{}) = 2+3+3+3+3 = 14
szukamy miejsca, gdzie jest najwięcej A i sumuejemy resztę które nie są A
v_2 = (AAAC)
Total_Dist((AAAC),{}) = 1+3+2+3+3 = 12
v_l = (GGGA)
Total_Dist((GGGA),{}) = 0+0+1+0+1 = 2
łańcuch konsensusu = łańcuch medianowy
max_sScore (s, DNA) = ∑_(j =1, ...,l) .M_p(s) (j) = w* = min_w Total_Dist(w, DNA)
Score (s(->), DNA) = ∑_(j =1) M_p(s) (j)
w jest łańcuchem konsensusu
d_M(w, s(->)) lt - Score (s(->), DNA)
DRZEWO BINARNE
korzeń
1-element
Motywy regulacyjne w sekwencjach DNA - dokończenie
All Leaves (L, k)
1. a<- (1, ..1)
2. while forever
3. output a
4. a <- Nextleaf (a,l,k)
5. if a = (1,1,...,1)
6. return
Nextleaf (a,L,k)
1. for i <- L to 1
2. if a_i <k
3. a_i <- a_i + 1
4. return a
5. a_i <-1
6. return a
K = {A, T, C,G}
L=3
a = ACG
NextLeaf(ACG, 3,4)
i=3
a_3(G<4)?NIE
a_3=A
i=2
a_2(C<4)?TAK
a_2=G return a = AGA
=>
NextLeaf(ACG, 3,4)
i=3
a_3(A<4)?TAK
a_3=AT return a = AGT
NextVertex (a,i,L,k)
1. if i< L
2. a_(i+1) <- 1
3. return(1, i+1)
4. else
5. for j <- to 1
6. if a_j < k
7. a_j <- a_j +1
8. return (a,j)
9. return (a, o)
k={A ,T , C, G}
l = 3
a . = ACG
NextVertex (ACG,3,3,4)
i=3 ?<3=L NIE
j=L=3
G = a_3 ?< 4 NIE
i=2
C<G TAK
a_2=G return (a,j) = (AG_,2)
NextVertex (AG_,2,3,4)
i=2<3 ? TAK
a_(i+1) = a_3 = 1 = A
return(1,3) = (AGA,3)
=>
NextVertex (AGA,3,3,4)
i=3<3 ? NIE
j=3
a_3 = A<K
a_3 = T ->(AGT,3)
return(1,3) = (AGA,3)
BruteForce MotifSearch(DNA, tn, l)
1. best score <- 0
2. for each (s_1, ... , s_t) from (1, .. , 1) to (n-l+1, ... , n-l+1)
3. if Score (s, DNA( > best score
4. best Score <- Score (s,DNA)
5. best Motif <- (s_1, ... , s_t)
6. if
ALGORYTMY ZACHŁANNE
Problem plecakowy
Problem wag i wartości
W_i
C_i
i=1,...,n
1, X_i =(0, 1, 0, ..., 1)
∑c_i x_i = MAX
∑w_i x_i < 15kg
Obliczamy cenę każdego kg w każdej paczce. Bierzemy te pierwsze najbardziej opłacalne tak, aby nie przekroczyć 15kg.
TASOWANIE
-odwrócenie -> najprostrza postać przetaasowaniu
p(odkąd, dokąd)
π = (π_1, π_2, π_3, ... , π_n)
p(i,j)
πp(i,j) = (π_1, π_2, π_3, ... ,π_(i-1), π_j ... ,π_(i+1), ,π_i, ,π_(j+1), ..., π_n)
Mamy dane dwa zbiory
π_1 = (1,2,4,3,7,5,6,8)
-> ?
π_2 = (3,4,5,2,1,8,6,7)
(zamieniamy kolejnkęod 1-6 na 6)
<- ρ_1 (1,6)
π_2 = (5,7,3,4,2,1,6,8) <- ρ_2 (1,3)
π_3 = (3,7,5,4,2,1,6,8) <- ρ_3 (2,4)
π_4 = (3,4,5,7,2,1,6,8) <- ρ_4 (4,8)
π_5 = (3,4,5,8,6,1,2,7) <- ρ_5 (4,7)
π_6 = (3,4,5,2,1,6,8,7) <- ρ_6 (6,7)
π_7 = (3,4,5,2,1,8,6,7)
ALGORYTMY ZACHŁANNE (dokończenie)
1. Algorytm najprostsze odwrócenie - poszerzanie prefiksu
123645
prefix - to co już jest na swoim miejscu 123
potem ρ(4,5) => 123465 . prefix 1234
potem ρ(5,6) => 123456
Specyficzny przykład:
(612345) -> brak prefixu -> ρ(1,2)
(162345) -> ρ(2,3) prefix = 1
(126345) -> ρ(3,4) prefix = 2
(123645) -> ρ(4,5) prefix = 3
(123465) -> ρ(5,6) prefix = 4
(123456)potem ρ(5,6) => 123456
Specyficzny przykład:
(612345) -> brak prefixu -> ρ(1,2)
(162345) -> ρ(2,3) prefix = 1
(126345) -> ρ(3,4) prefix = 2
(123645) -> ρ(4,5) prefix = 3
(123465) -> ρ(5,6) prefix = 4
d(π) = 5 <= liczba permutacji
np.
0(82765143)9
b(π) = 6 => ρ(1,6)
0(15672843)9
b(π) = 5 => ρ(2,5)
0(12765843)9
b(π) = 4 => ρ(3 ,8)
0(12348567)9
b(π) = 3 => ρ(5,8)
0(12347658)9
b(π) = 2 => ρ(5,8)
0(12345678)9
b(π) = 0
b(π) = 5 (5 obróceń)
Ale można zrobić szybciej:
ρ(1,2) => ρ(2,8) => ρ(1,3) => ρ(1,4)
b(π) = 4
Algorytmy aproksymacyjne - szukają optymalnych wartości
GWARANCJA = A(π)/OPT(π) = wynik z algorytmu aproksymującego /prawdziwy wynik
A(π)/OPT(π) = 5/2 = 2,5
2,5 razy się pomyliśmy)
Przy algorytmach szukających minimum znajdziemy "większy" sposób.
MINIMALIZACJA OPT(π)=< A(π)
Przy algorytmach szukających maximum znajdziemy "mniejszy" sposób.
MAXYMALIZACJA OPT(π)=> A(π)
Dla
α = max(π) A(π)/OPT(π)
1/α = min(π) A(π)/OPT(π)
MINIMALIZACJA
α => A(π*)/OPT(π*) => 1
αOPT(π*) => A(π*)
A(π*) => OPT(π*) => 1/α * A(π*)
MAKSYMALIZACJA
1/α = min(π) A(π)/OPT(π)
A(π) => OPT(π) => α * A(π)
Zad 1 Dany jest algorytm maksymalizacyjny o gwarancji α = 4.
Dla pewnych danych D uzyskaliśmy wynik 12.
12 =< OPT(D) =< 4*12
Dysponujemy B minimlizacyjny o gwarancji α = 2. Dostaliżmy wynik 3,24. Co jest wartością prawdziwą?
3,24/2 =< OPT(D) =< 3,24
Zad 2. Poprawianie algorytmu sortowania przez odwrócenie
Def. Parę sąsiadujących elementów w permutacji π_i i π_(i+1) nazywamy uzgodnioną jeżeli π_i, π_(i+1) są kolejnymi liczbami. W przeciwnym wypadku parę π_i, π_(i+1) nazywamy punktem łamiącym.
(21345687)
13 punkt łamiący
68 punkt łamiący
Dopisujemuy 0 i 9
0(2134687)9
5 uzgodnionych
4 łamiące
0(12345678)9
b(id) = 0
oznaczenie b(π) => ilość punktów łamiących w π
Maksymalnie w jednej operacji możemy usunąć 2 punkty łamiące.
odległość
d(π) => b(π)/2
ALGORYTM
BreakPointReversalSort(π)
1. while b(π) > 0
2. Among all reversals, choose reversal , minim b(π*ρ)
3. π <- π * ρ
4. output ρ
5. return
Słaby punkt w tym algorytmie to występowanie rosnących sekwencji.
np.
456123
Taśmą w permutacji π nazywamy przedział pomiędzy kolejnymi punktami łamiącymi
0(41237658)9
Występują taśmy rosnące lub malejące.
Taśmę jednoelementową zawsze nazywamy malejącą, oprócz elementów brzegowych, które zawsze są rosnące.
Tw. Jeśli permutacja π zawiera taśmę malejącą, to istnieje odwrócenie ρ takie, które zmniejsza liczbę punktów łamiących, czyli
b(πρ) < b(π)
Z taśm malejących wybieramy tę, która zawiera najmniejszy element, np.
0(41237658)9
więc wybieramy 4, k=4
k-1 : 3, więc robimy ρ(2,4) i otrzymujemy
0(43217658)9
wybieramy 4321 i odwracamy ρ(1,4) i otrzymujemy:
0(12347658)9
Jeśli są same rosnące, wybieramy jakiś (obojętnie jaki) i go odwracamy. Najgorszy przypadek jest wtedy, gdy długość
d(π) = 2b(π)
Tw. Algorytm ImprovedBreakpointReversalSort jest algorytmem aproksymacyjny o długości 4
IBRS(π)
1. while b(π)>0
2. if π has a decreasing strip
3. Among all reversals, choose, reversal ρ minimaing b(πρ)
4. else
Choose a reversal ρ that flips an icreasing strip in π
5. π <- π * ρ
6. output ρ
7. return
Złożoność dla GreeedyMotifSearch (DNA, t,n,l)
θ(ln + tnl) =θ(n^2)
ALGORYTMY DYNAMICZNE: ODKRYWANIE PODOBIEŃSTW W SEKWENCJACH DNA
Algorytmy dynamiczne - wyznaczanie rozwiązania ogólngo poprzez złożenie rozwiązań podproblemów.
Algorytm rekurencyjne = )(2^n)
Algorytm dynamiczny = O(n)
1. Problem KASJERA
M- reszta, którą należy wydać
c(->) = (c_1, c_2, c_3, ..., c_d) -> momenty/nominaty
dla:
M=77, c(->) = (1,3,7)
OPT(M=77) = minimum z
{OPT(76) +1*1
{OPT(74) +1*3
{OPT(70) +1*7
czyli rozkładamy na mniejsze części i szukamy najlepszego
DRZEWO REKURENCYJNE
Złożoność = O(M^d) =O(Md)
2. Problem TURYSTY NA MANHATTANIE
(jak się poruszać, żeby zobaczyć najwięcej i się nie kręcić po ulicach)
Trzeba spojrzeć na problem pod względem grafu skierowanego
Źródło - punkt w grafie z którego można tylko wyjść
Zlew - punkt, którego można tylko wejść
-grafy skierowane i acykliczne, DAG porządek topologiczny)
Twierdzenie
Każdy skończony acykliczny graf skierowany ma conajmniej jeden zlew i jedno źródło.
Dowód
1. Każda ścieżka zbudowana jest z różnych wierzchołków (żaden się nie powtarza).
2. Graf jest skończony => każda ścieżka jest skończona
3. Istnieje ścieżka najdłuższa.
ALGORYTM DIJKSTRY
W(i,j) | V_1 V_2 V_3 V_4 V_5
____________________________
V_1 | 0 10 ∞ 5 ∞
V_2 | ∞ 0 1 2 ∞
V_3 | ∞ ∞ 0 ∞ 4
V_4 | ∞ 3 9 0 2
V_5 | ∞ ∞ 6 ∞ 0
Punkt startowy to pusta lista
L=∅, D -> wektor dł. aktualnej
_____________________ | V_2 | V_3 | V_4 | V_5
L=∅ D_i | 10 | ∞ | 5 | ∞
L={V_4} D_i | 8 | 14 | 5 | 7
L={V_4, V_5} D_i | 10 | 13 | 5 | 7
L={V_2, V_4, V_5} D_i | 10 | 9 | 5 | 7
wybierz najmniejszy
wybierz najmniejszy poza wcześniej wybranymi
Złożoność = O(n^3)
Nie możliwe jest znaleziemi maxa tym algorytmem
Trzeba liczyć dynamicznie.
Manhattantourist(w,w,n,m)
liczy kolejne możliwość i dopiero na koniec zna najlepszą.
WYDAJNOŚĆ : )(ilość krawędzi)
przechodzimy w postać liniową (krawędzie zawsze od mniejszego punktu do większego)
SEKWENCJE DNA
v(->): ATATAT
w(->): TATATA
nie zgadzają się pozycje
d_H(v(->), w(->)) = 6
Można zapisać inaczej
v(->): ATATAT
w(->): TATATA
Elemnty edycje:
-kasowanie
-wstawianie
-zamiana
Tablica podstawień dla aminokwasu:
-PAM (Percent Accepted Mutations) tablice Dayboff
-BLOSUM
PORÓWNUJEMY 2 SEKWENCJE
TGCATAT -> skasuj ost. T
TGCATA -> skasuj ost. A
TGCAT -> zamień C na G
TGGAT -> wstaw A na początek
ATGGAT -> zamień G na C
ATCCAT -> wstaw G na 5 pozycję
ATCCGAT
Można zrobić to szybciej to tylko przykład
Odległość edycyjna pomiędzy dwoma sekwencjami DNA nazywamy minimalną liczbę operacji edycji tj:
-wstawianie jednego symbolu
-kasowanie symbolu
-zmiana symbolu
Dopasowanie dwóch sekwencji DNA V (o n znakach) i W (o m znakach) nazywamy dwuwierszową macierz, w której pierwszy wiersz zawiera kolejne znaki V a drugi wiersz zawiera kolejne znaki W, przy czym w obu sekwencjach mogą być dowolnie rozmieszczane spacje.
np.
123 4 56 7
v(->): ATGTTAT
w(->):ATCGTAC
^- mutacja/edycja
v(->) AT^GTTAT^
w(->) ATCG^TA^C
1 insercja
2 delecja
Graf edycji
Globalne dopasowanie
-> Rozwiązanie Smith -Waterman
https://en.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorithm
ALGORYTMY DYNAMICZNE - ODKRYWANIE PODOBIEŃSTW MIĘDZY SEKWENCJAMI DNA
1. Problem najdłuższego wspólnego podciągu
Def
Podciągiem sekwencji DNA V = v_1v_2...v_n nazywamy uporządkowany ciąg jego znaków - niekoniecznie kolejnych
np.
ciąg:
n=7
v(->) = ATTGCAT
podciągi: TGAT
m=6
w(->) = GTATCG
wspólny podciąg dwóch ciągów:
TAT :
v(->) = (2,6,7)
w(->) = (2,3,4)
Twierdzenie:
d(v,w)
Z obrazków:
n=7
m=6
s=4
znajdź wspólny podciąg
=> 7+6-2*4=13-8=5
printLCS(b,v,i,j)
START(6,4
PrintLCS(b,v,6,4)
b_(6,4) = "↖"
PrintLCS(b,v,5,3) V_6 = A
b_(5,3) = "↑"
PrintLCS(b,v,4,3)
b_(4,3) = "↑"
PrintLCS(b,v,3,3)
b_(3,3) = "↖"
PrintLCS(b,v,2,2) V_3 = C
b_(2,2) = "←"
PrintLCS(b,v,2,1)
b_(2,1) = "↖"
PrintLCS(b,v,1,0)
return
print v_i, i =2
print v_2 v_2=T
podciąg: TCA
ALGORYTMY GRAFOWE SEKWENCJONOWANIE DNA I IDENTYFIKACJA BIAŁEK
graf pokrywa -> droga Hamiltona
SBH
Problem szachów
Cykl Eulera
Skończony graf spójny, w którym każdy wierzchołek jest stopnia parzystego..
V-> wierzchołki
E->krawędzie
S-> droga
W tym grafie jest cykl Eulera, bo każdy wierzchołek jest st. parzystego.
wg. algorytmu Fleury'ego
zaczynamy od 1
S=1,2,7,3,6,5,4,3,2,9,10,11,12,7,8,11,9,1
Złożoność algorytmu = O(|E|)
GRA SIR WILLIAMA HAMILTONA
Chcemy odwiedzić wszystkie wierzchołki tylko jeden raz.
PROBLME CYKLU HAMILTONA (Komiwgazera)
PROBLEM NAJKRÓTSZEJ DROGI
ALGORYTM DIJKSTRY
GRAFY I GENETYKA
GRAF INTERWAŁOWY
analiza asymptotyczna O()
1. zignoruj stałe wielkości zależne od maszyny
2. obserwuj jedynie wzrost przebiegu T(n) , gdy n->∞
Dla danej funkcji g(n) przez O(g(n)) oznaczany następujący wzór funkcji:
O(g(n))) = {f(n) : istnieją stałe c oraz n_0 takie, że O =< f(n) =<cg(n) dla wszystkich n=>n_0}
Wniosek: Notacja O() służy szacowaniu funkcji z góry
Np. Najgorszy przypadek Insertion-Sort
T(n) = ∑^n _(j=2) (j-1)c = ∑^n _(j=2) O(j) = O(n^2)
Komentarze
Prześlij komentarz