Подниз

Из Википедије, слободне енциклопедије

У математици, подниз неког низа је нови низ који се добија од почетног брисањем неких елемената низа, без промене релативног редоследа преосталих елемената.

Формално, претпоставимо да је X скуп, и да је (ak)kK низ у X, где је K = {1, 2, 3, ..., n} ако је (ak) коначан низ, а K = N ако је (ak) бесконачан низ. Тада је подниз од (ak) низ облика  (a_{n_r}) где је (nr) строго растући низ у скупу индекса K.

Пример[уреди]

На пример,

 < B, C, D, G >

је подниз од

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

са одговарајућим низом индекса < 3, 7, 9, 11 >.

Ако су дата два низа X и Y, за низ G се каже да је заједнички подниз од X и Y, ако је G подниз и од X и од Y. На примр, ако је

 X = < A, C, B, D, E, G, C, E, D, B, G > и
 Y = < B, E, G, C, F, E, U, B, K >

онда би заједнички подниз од X и Y могао да буде

 G = < B, E, E >

Ово не би био њихов најдужи заједнички подниз, јер је G дужине 3, а постоји заједнички подниз < B, E, E, B >, дужине 4. Најдужи заједнички подниз од X и Y је < B, E, G, C, E, B >.

Примене[уреди]

Поднизови имају примене у рачунарству, посебно у области биоинформатике, где се користе за упоређивање, анализирање и складиштење ДНК ланаца.

Узмимо два ланца ДНК, на пример:

ORG1 = ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA
ORG2 = CGTTCGGCTATCGTACGTTCTATTCTATGATTTCTAA

Поднизови се користе да одреде колико су слични ланци ДНК, коришћењем ДНК база: аденина, гуанина, цитозина и тимина.

Подниска и подниз[уреди]

У рачунарству, ниска се обично користи као синоним за низ, али је важно имати у виду да подниска и подниз нису синоними. Подниске су узастопни делови ниске, док поднизови не морају да узимају искључиво узастопне елементе низа. Ово значи да је подниска ниске увек подниз ниске, али обратно не мора да важи[1].

Извори[уреди]

  1. ^ Gusfield 1999, стране 4

Литература[уреди]

  • Овај чланак садржи у себи материјале из чланка подниз са сајта PlanetMath, који је лиценциран под ГЛСД.
  • Gusfield, Dan (1999) [1997]. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. USA: Cambridge University Press. стр. 4. ISBN 0-521-58519-8.