Medze efektivnosti paralelných výpočtových systémov
Chtěli byste být mozkem v baňce?
XXX let SOFSEMu
Proč počítáme a co počítáme?
The complexity of lexicographic sorting and searching
An asymptotically optimal sorting algorithm that uses component comparisons to lexicographically sort the set of -tuples is presented. This sorting algorithm builds the static data structure - the so called optimal lexicographic search tree - in which it is possible to perform member searching for an unknown -tuple in at most comparisons. The number of comparisons used by this search algorithm is optimal.
On the conjecture relating minimax and minimean complexity norms
Using counterexample it has been shown that an algorithm which is minimax optimal and over all minimax optimal algorithms is minimean optimal and has a uniform behaviour need not to be minimean optimal.
On the lower bound for minimum comparison selection
Page 1