Przeszukiwanie losowe

English translation: random/randomized search

GLOSSARY ENTRY (DERIVED FROM QUESTION BELOW)
Polish term or phrase:Przeszukiwanie losowe
English translation:random/randomized search
Entered by: Katarzyna Wolnicka

14:39 Apr 25, 2018
Polish to English translations [Non-PRO]
Tech/Engineering - Games / Video Games / Gaming / Casino / Computer games development
Polish term or phrase: Przeszukiwanie losowe
Praca dyplomowa dotyczy metod przeszukiwania losowego w projektowaniu gier komputerowych.
Pytanie dotyczy ogólnego terminu "Przeszukiwanie losowe"

Zbliżony termin "binary search tree" - przeszukiwanie drzewa gry

"W kolejnym punkcie pierwszego rozdziału pojawia się wyjaśnienie pojęcia przeszukiwanie losowe, opis wybranych algorytmów oraz wybrane techniki wspomagające przeszukiwania drzewa gry"
Katarzyna Wolnicka
Poland
Local time: 10:52
random/randomized search
Explanation:
In computer science and probability theory, a random binary tree is a binary tree selected at random from some probability distribution on binary trees. Two different distributions are commonly used: binary trees formed by inserting nodes one at a time according to a random permutation, and binary trees chosen from a uniform discrete distribution in which all distinct trees are equally likely. It is also possible to form other distributions, for instance by repeated splitting. Adding and removing nodes directly in a random binary tree will in general disrupt its random structure, but the treap and related randomized binary search tree data structures use the principle of binary trees formed from a random permutation in order to maintain a balanced binary search tree dynamically as nodes are inserted and deleted.

Treaps and randomized binary search trees

In applications of binary search tree data structures, it is rare for the values in the tree to be inserted without deletion in a random order, limiting the direct applications of random binary trees. However, algorithm designers have devised data structures that allow insertions and deletions to be performed in a binary search tree, at each step maintaining as an invariant the property that the shape of the tree is a random variable with the same distribution as a random binary search tree.

If a given set of ordered numbers is assigned numeric priorities (distinct numbers unrelated to their values), these priorities may be used to construct a Cartesian tree for the numbers, a binary tree that has as its inorder traversal sequence the sorted sequence of the numbers and that is heap-ordered by priorities. Although more efficient construction algorithms are known, it is helpful to think of a Cartesian tree as being constructed by inserting the given numbers into a binary search tree in priority order. Thus, by choosing the priorities either to be a set of independent random real numbers in the unit interval, or by choosing them to be a random permutation of the numbers from 1 to n (where n is the number of nodes in the tree), and by maintaining the heap ordering property using tree rotations after any insertion or deletion of a node, it is possible to maintain a data structure that behaves like a random binary search tree. Such a data structure is known as a treap or a randomized binary search tree

https://en.wikipedia.org/wiki/Random_binary_tree
Selected response from:

Frank Szmulowicz, Ph. D.
United States
Local time: 05:52
Grading comment
Thank you very much for a prompt answer. It saved my day.
4 KudoZ points were awarded for this answer



Summary of answers provided
3random/randomized search
Frank Szmulowicz, Ph. D.


  

Answers


22 mins   confidence: Answerer confidence 3/5Answerer confidence 3/5
random/randomized search


Explanation:
In computer science and probability theory, a random binary tree is a binary tree selected at random from some probability distribution on binary trees. Two different distributions are commonly used: binary trees formed by inserting nodes one at a time according to a random permutation, and binary trees chosen from a uniform discrete distribution in which all distinct trees are equally likely. It is also possible to form other distributions, for instance by repeated splitting. Adding and removing nodes directly in a random binary tree will in general disrupt its random structure, but the treap and related randomized binary search tree data structures use the principle of binary trees formed from a random permutation in order to maintain a balanced binary search tree dynamically as nodes are inserted and deleted.

Treaps and randomized binary search trees

In applications of binary search tree data structures, it is rare for the values in the tree to be inserted without deletion in a random order, limiting the direct applications of random binary trees. However, algorithm designers have devised data structures that allow insertions and deletions to be performed in a binary search tree, at each step maintaining as an invariant the property that the shape of the tree is a random variable with the same distribution as a random binary search tree.

If a given set of ordered numbers is assigned numeric priorities (distinct numbers unrelated to their values), these priorities may be used to construct a Cartesian tree for the numbers, a binary tree that has as its inorder traversal sequence the sorted sequence of the numbers and that is heap-ordered by priorities. Although more efficient construction algorithms are known, it is helpful to think of a Cartesian tree as being constructed by inserting the given numbers into a binary search tree in priority order. Thus, by choosing the priorities either to be a set of independent random real numbers in the unit interval, or by choosing them to be a random permutation of the numbers from 1 to n (where n is the number of nodes in the tree), and by maintaining the heap ordering property using tree rotations after any insertion or deletion of a node, it is possible to maintain a data structure that behaves like a random binary search tree. Such a data structure is known as a treap or a randomized binary search tree

https://en.wikipedia.org/wiki/Random_binary_tree


Frank Szmulowicz, Ph. D.
United States
Local time: 05:52
Native speaker of: Native in EnglishEnglish, Native in PolishPolish
PRO pts in category: 4
Grading comment
Thank you very much for a prompt answer. It saved my day.
Login to enter a peer comment (or grade)



Login or register (free and only takes a few minutes) to participate in this question.

You will also have access to many other tools and opportunities designed for those who have language-related jobs (or are passionate about them). Participation is free and the site has a strict confidentiality policy.

KudoZ™ translation help

The KudoZ network provides a framework for translators and others to assist each other with translations or explanations of terms and short phrases.


See also:
Term search
  • All of ProZ.com
  • Term search
  • Jobs
  • Forums
  • Multiple search