Inscriere cercetatori

Premii Ad Astra

premii Ad Astra

Asociația Ad Astra a anunțat câștigătorii Premiilor Ad Astra 2022: Proiectul și-a propus identificarea și popularizarea modelelor de succes, a rezultatelor excepționale ale cercetătorilor români din țară și din afara ei.

Asociatia Ad Astra a cercetatorilor romani lanseaza BAZA DE DATE A CERCETATORILOR ROMANI DIN DIASPORA. Scopul acestei baze de date este aceea de a stimula colaborarea dintre cercetatorii romani de peste hotare dar si cu cercetatorii din Romania. Cercetatorii care doresc sa fie nominalizati in aceasta baza de date sunt rugati sa trimita un email la

Identifying almost-sorted permutations from TCP buffer dynamics

Domenii publicaţii > Ştiinţe informatice + Tipuri publicaţii > Articol în revistã ştiinţificã

Autori: Gabriel Istrate

Editorial: Scientific Annals of Computer Science (special issue dedicated to professor Sergiu Rudeanu's 80th birthday), XXV (1), p.133-154, 2015.


Associate to each sequence A of integers (intending to model packet IDs in a TCP/IP stream) a sequence of positive integers of the same length M(A). The i’th entry of M(A) is the size (at time i) of the smallest buffer needed to hold out-of-order packets, where space is accounted for unreceived packets as well. Call two sequences A, B equivalent (written A =_{FB} B) if M(A) = M(B).

For a sequence of integers A define SUS(A) to be the shuffled-up-sequences reordering measure, defined as the smallest possible number of classes in a partition of the original sequence into increasing subsequences.

We prove the following result: any two permutations A, B of the same length with SUS(A), SUS(B) <= 3 such that A =_ {FB} B are identical. The result is no longer valid if we replace the upper bound 3 by 4.

We also consider a similar problem for permutations with repeats. In this case the uniqueness of the preimage is no longer true, but we obtain a characterization of all the preimages of a given sequence, which in particular allows us to count them in polynomial time.

The results were motivated by explaining the behavior and engineering Restored, a receiver-oriented model of traffic we introduced
and experimentally validated in earlier work.

Cuvinte cheie: SUS, permutations