Podniz

U matematici, podniz nekog niza je novi niz koji se dobija od početnog brisanjem nekih elemenata niza, bez promene relativnog redosleda preostalih elemenata.

Formalno, pretpostavimo da je X skup, i da je (a_k)_{k ∈ K} niz u X, gde je K = {1, 2, 3, ..., n} ako je (a_k) konačan niz, a K = N ako je (a_k) beskonačan niz. Tada je podniz od (a_k) niz oblika $(a_{n_{r}})$ gde je (n_r) strogo rastući niz u skupu indeksa K.

Primer

Na primer,

$<B,C,D,G>$

je podniz od

$<A,C,B,D,E,G,C,E,D,B,G>$,

sa odgovarajućim nizom indeksa < 3, 7, 9, 11 >.

Ako su data dva niza X i Y, za niz G se kaže da je zajednički podniz od X i Y, ako je G podniz i od X i od Y. Na primr, ako je

$X=<A,C,B,D,E,G,C,E,D,B,G>$ i

$Y=<B,E,G,C,F,E,U,B,K>$

onda bi zajednički podniz od X i Y mogao da bude

$G=<B,E,E>$

Ovo ne bi bio njihov najduži zajednički podniz, jer je G dužine 3, a postoji zajednički podniz < B, E, E, B >, dužine 4. Najduži zajednički podniz od X i Y je < B, E, G, C, E, B >.

Primene

Podnizovi imaju primene u računarstvu, posebno u oblasti bioinformatike, gde se koriste za upoređivanje, analiziranje i skladištenje DNK lanaca.

Uzmimo dva lanca DNK, na primer:

ORG₁ = ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA
ORG₂ = CGTTCGGCTATCGTACGTTCTATTCTATGATTTCTAA

Podnizovi se koriste da odrede koliko su slični lanci DNK, korišćenjem DNK baza: adenina, guanina, citozina i timina.

Podniska i podniz

U računarstvu, niska se obično koristi kao sinonim za niz, ali je važno imati u vidu da podniska i podniz nisu sinonimi. Podniske su uzastopni delovi niske, dok podnizovi ne moraju da uzimaju isključivo uzastopne elemente niza. Ovo znači da je podniska niske uvek podniz niske, ali obratno ne mora da važi.

Literatura

• Ovaj članak sadrži u sebi materijale iz članka podniz sa sajta PlanetMath, koji je licenciran pod GLSD.
• Gusfield, Dan (1999) [1997]. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. USA: Cambridge University Press. str. 4. ISBN 978-0-521-58519-4.