Zaawansowane programowanie - treść problemów

• Problem I − MIN SUPERSET PDP
  

Instancja: Multizbiór liczb całkowitych dodatnich D = {d₁, ..., d_k}.
Rozwiązanie: Zbiór liczb całkowitych nieujemnych P = {p₁, ..., p_m} taki, że D ⊆ {|p_i − p_j|: 1 ≤ i < j ≤ m} i m jest minimalne.

• Problem II − MAX SUBSET PDP
  

Instancja: Multizbiór liczb całkowitych dodatnich D = {d₁, ..., d_k}.
Rozwiązanie: Zbiór liczb całkowitych nieujemnych P = {p₁, ..., p_m} taki, że {|p_i − p_j|: 1 ≤ i < j ≤ m} ⊆ D i m jest maksymalne.

• Problem III − MAX MATCH PDP
  

Instancja: Multizbiór liczb całkowitych dodatnich D = {d₁, ..., d_k} z k = .
Rozwiązanie: Zbiór liczb całkowitych nieujemnych P = {p₁, ..., p_m} taki, że {|p_i − p_j|: 1 ≤ i < j ≤ m} = D' i liczba pokrywających się elementów w D i D' jest maksymalna.

• Problem IV − MIN ERROR MAP
  

Instancja: Binarna macierz M_mxn hybrydyzacji m fragmentów do n próbek.
Rozwiązanie: Uporządkowanie kolumn macierzy M takie, że liczba pól, których wartość należy zmienić, aby macierz osiągnęła własność consecutive 1s w wierszach jest minimalna.

• Problem V − MAX COLS MAP
  

Instancja: Binarna macierz M_mxn hybrydyzacji m fragmentów do n próbek.
Rozwiązanie: Uporządkowanie kolumn macierzy M takie, że liczba kolumn, które należy usunąć, aby macierz osiągnęła własność consecutive 1s w wierszach jest minimalna.

• Problem VI − MIN ERROR ALIGNMENT
  

Instancja: Znakowa macierz M_mxn zawierająca m sekwencji nukleotydowych o długości n.
Rozwiązanie: Dopasowanie globalne m sekwencji takie, że długość dopasowania nie przekracza 2n i liczba kolumn dopasowania, w których występują różne znaki (nie licząc spacji) jest minimalna.

• Problem VII − MIN LENGTH ALIGNMENT
  

Instancja: Znakowa macierz M_mxn zawierająca m sekwencji nukleotydowych o długości n.
Rozwiązanie: Dopasowanie globalne m sekwencji takie, że w żadnej kolumnie dopasowania nie ma konfliktu znaków (nie licząc spacji) i długość dopasowania jest minimalna.