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 (ak)kK niz u X, gde je K = {1, 2, 3, ..., n} ako je (ak) konačan niz, a K = N ako je (ak) beskonačan niz. Tada je podniz od (ak) niz oblika gde je (nr) strogo rastući niz u skupu indeksa K.

Primer uredi

Na primer,

 

je podniz od

 ,

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

  i
 

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

 

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 uredi

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:

ORG1 = ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA
ORG2 = CGTTCGGCTATCGTACGTTCTATTCTATGATTTCTAA

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

Podniska i podniz uredi

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[1].

Izvori uredi

  1. ^ Gusfield 1999, str. 4.

Literatura uredi

  • 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.