Список терминов, относящихся к алгоритмам и структурам данных

Материал из Википедии — свободной энциклопедии

Эта статья или раздел нуждается в переработке. Пожалуйста, улучшите её в соответствии с правилами написания статей.

The Словарь алгоритмов и структур данных (англ.) — это справочник, который поддерживается Национальным институтом стандартов и технологии США. В нём определяется большое количество терминов, относящихся к алгоритмам и структурам данных. Для алгоритмов и структур данных, не указанных здесь, смотрите список алгоритмов и список структур данных.

Содержание:	Top - 0–9 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

[править] A

• absolute performance guarantee
• Абстрактный тип данных (АТД, Abstract data type, ADT)
• (a,b)-дерево
• accepting state
• Функция Аккерманна (Ackermann's function)
• active data structure
• acyclic directed graph
• Ациклический граф (acyclic graph)
• adaptive heap sort
• adaptive Huffman encoding
• adaptive k-d tree
• adaptive sort
• address-calculation sort
• Представление соседства в виде списка (adjacency-list representation)
• Представление соседства в виде матрицы (adjacency-matrix representation)
• Соседний узел графа (adjacent)
• admissible vertex
• ADT
• Противник (криптография) (adversary)
• Алгоритм (algorithm)
• algorithm B
• algorithm BSTW
• algorithm FGK
• algorithmically solvable
• algorithm V
• all pairs shortest path
• Алфавит (alphabet)
• Alpha Skip Search algorithm
• alternating path
• Переменная машина Тьюринга (alternating Turing machine)
• alternation
• American flag sort
• amortized cost
• Предок (информатика) (ancestor)
• Логическое И (logical conjunction)
• Американский Институт Национальных Стандартов (ANSI)
• antichain
• Антисимметричное соотношение (antisymmetric relation)
• Ассошиэйтед Пресс (AP)
• Apostolico-Crochemore
• Apostolico-Giancarlo algorithm
• approximate string matching
• Аппроксимационный алгоритм (approximation algorithm)
• arborescence
• Дуга (arc)
• Арифметическое кодирование (arithmetic coding)
• Массив (array)
• Индекс массива (array index)
• Слияние массивов (array merging)
• Поиск по массиву (array search)
• Точка разрыва графа (articulation point)
• Проблема назначения (assignment problem)
• Ассоциативный список (association list)
• Ассоциативный (associative)
• Ассоциативный массив (associative array)
• asymptotically tight bound
• asymptotic bound
• asymptotic lower bound
• asymptotic space complexity
• Асимптотическая временная сложность (asymptotic time complexity)
• asymptotic upper bound
• Увеличенный путь в графе (augmenting path)
• automaton
• Средний случай (average case)
• Стоимость среднего случая (average-case cost)
• АВЛ-дерево (AVL tree)
• Аксиоматическая семантика (axiomatic semantics)

[править] B

• backtracking
• bag
• balance
• balanced binary search tree
• balanced binary tree
• balanced k-way merge sort
• balanced merge sort
• balanced multiway merge
• balanced multiway tree
• balanced quicksort
• balanced tree
• balanced two-way merge sort
• BANG file
• Batcher sort
• Baum Welch algorithm
• BB α tree
• BDD
• BD-tree
• Bellman-Ford algorithm
• Benford's law
• best case
• best-case cost
• best-first search
• biconnected component
• biconnected graph
• bidirectional bubble sort
• big-O notation
• binary function
• binary GCD algorithm
• binary heap
• binary insertion sort
• binary knapsack problem
• binary priority queue
• binary relation
• binary search
• binary search tree
• binary tree
• binary tree representation of trees
• bingo sort
• binomial heap
• binomial tree
• bin packing problem
• bin sort
• bintree
• bipartite graph
• bipartite matching
• bisector
• bitonic sort
• bit vector
• Bk tree
• block
• block addressing index
• blocking flow
• block search
• Bloom filter
• blossom
• bogosort
• boogol
• boolean
• boolean expression
• boolean function
• border
• bottleneck traveling salesman
• bottom-up tree automaton
• boundary-based representation
• bounded error probability in polynomial time
• bounded queue
• bounded stack
• Boyer-Moore
• Boyer-Moore-Horspool
• bozo sort
• B+ tree
• BPP
• Bradford's law
• branch and bound
• branching
• breadth-first search
• Bresenham's algorithm
• brick sort
• bridge
• British Museum algorithm
• brute force
• brute force string search
• brute force string search with mismatches
• BSP-tree
• B*-tree
• B-tree
• bubble sort
• bucket
• bucket array
• bucketing method
• bucket sort
• bucket trie
• buddy system
• buddy tree
• build-heap
• Burrows-Wheeler transform
• busy beaver
• BV-tree
• BWT
• Byzantine generals

[править] C

• cactus stack
• Calculus of Communicating Systems
• calendar queue
• candidate consistency testing
• candidate verification
• canonical complexity class
• capacitated facility location
• capacity
• capacity constraint
• cartesian tree
• cascade merge sort
• caverphone
• Cayley-Purser
• CCS
• C curve
• cell probe model
• cell tree
• cellular automaton
• centroid
• certificate
• chain
• chaining
• child
• Chinese postman problem
• Chinese remainder theorem
• Christofides algorithm
• Christofides heuristic
• chromatic index
• chromatic number
• Church-Turing thesis
• circuit
• circuit complexity
• circuit value problem
• circular list
• circular queue
• clique
• clique problem
• clustering
• clustering free
• coalesced hashing
• coarsening
• cocktail shaker sort
• codeword
• coding tree
• collective recursion
• collision
• collision resolution scheme
• Colussi
• combination
• comb sort
• Communicating Sequential Processes
• commutative
• compact DAWG
• compact trie
• comparison sort
• competitive analysis
• competitive ratio
• complement
• complete binary tree
• complete graph
• completely connected graph
• complete tree
• complexity
• complexity class
• computable
• concave function
• concurrent flow
• concurrent read, concurrent write
• concurrent read, exclusive write
• configuration
• confluently persistent data structure
• conjunction
• connected components
• connected graph
• co-NP
• constant function
• continuous knapsack problem
• Cook reduction
• Cook's theorem
• counting sort
• covering
• CRC
• CRCW
• Crew (algorithm)
• critical path problem
• CSP
• CTL
• cuckoo hashing
• cut
• cutting plane
• cutting stock problem
• cutting theorem
• cut vertex
• cycle
• cyclic redundancy check

[править] D

• D-adjacent
• DAG
• DAG shortest paths
• data structure
• DAWG
• decidable
• decidable language
• decimation
• decision problem
• decision tree
• decomposable searching problem
• degree
• dense graph
• depoissonization
• depth
• depth-first search
• deque
• derangement
• descendant
• deterministic
• deterministic algorithm
• deterministic finite automata string search
• deterministic finite automaton
• deterministic finite state machine
• deterministic finite tree automaton
• deterministic pushdown automaton
• deterministic tree automaton
• Deutsch-Jozsa algorithm
• DFA
• DFS
• DFS forest
• DFTA
• diagonalization
• diameter
• dichotomic search
• dictionary
• diet (see discrete interval encoding tree below)
• difference
• digital search tree
• digital tree
• digraph
• Dijkstra's algorithm
• diminishing increment sort
• dining philosophers
• direct chaining hashing
• directed acyclic graph
• directed acyclic word graph
• directed graph
• discrete interval encoding tree
• discrete p-center
• disjoint set
• disjunction
• distributional complexity
• distribution sort
• divide and conquer
• divide and marriage before conquest
• division method
• domain
• don't care
• Doomsday rule
• double-direction bubble sort
• double-ended priority queue
• double hashing
• double left rotation
• double metaphone
• double right rotation
• doubly-chained tree
• doubly-ended queue
• doubly linked list
• DPDA
• Dragon curve
• dual
• dual linear program
• Dutch national flag
• dyadic tree
• dynamic
• dynamic array
• dynamic hashing
• dynamic programming
• dynamization transformation

[править] E

• edge
• edge coloring
• edge connectivity
• edge crossing
• edge-weighted graph
• edit distance
• edit operation
• edit script
• efficiency
• 8 queens
• elastic-bucket trie
• element uniqueness
• end-of-string
• enfilade
• ERCW
• EREW
• Euclidean algorithm
• Euclidean distance
• Euclidean Steiner tree
• Euclidean traveling salesman problem
• Euclid's algorithm
• Euler cycle
• Eulerian graph
• Eulerian path
• exact string matching
• EXCELL
• exchange sort
• exclusive or
• exclusive read, concurrent write
• exclusive read, exclusive write
• exhaustive search
• existential state
• expandable hashing
• expander graph
• exponential
• extended binary tree
• extended Euclid's algorithm
• extended k-d tree
• extendible hashing
• external index
• external memory algorithm
• external memory data structure
• external merge
• external merge sort
• external node
• external quicksort
• external radix sort
• external sort
• extrapolation search
• extremal
• extreme point

[править] F

• facility location
• factor
• factorial
• fast fourier transform
• fathoming
• feasible region
• feasible solution
• feedback edge set
• feedback vertex set
• Ferguson-Forcade algorithm
• FFT
• Fibonacci number
• Fibonacci search
• Fibonacci tree
• Fibonacci heap
• FIFO
• filial-heir chain
• Find
• find kth least element
• finitary tree
• finite Fourier transform
• finite state automaton
• finite state machine
• finite state machine minimization
• finite state transducer
• first child-next sibling binary tree
• first come, first served
• first-in, first-out
• fixed-grid method
• flash sort
• flow
• flow conservation
• flow function
• flow network
• Floyd-Warshall algorithm
• Ford-Bellman
• Ford-Fulkerson method
• forest
• forest editing problem
• formal language
• formal methods
• formal verification
• forward index
• fractal
• fractional knapsack problem
• fractional solution
• free edge
• free list
• free tree
• free vertex
• frequency count heuristic
• full array
• full binary tree
• full inverted index
• fully dynamic graph problem
• fully persistent data structure
• fully polynomial approximation scheme
• function (programming)
• function (mathematics)
• functional data structure

[править] G

• Galil-Giancarlo
• Galil-Seiferas
• gamma function
• GBD-tree
• GCD
• geometric optimization problem
• global optimum
• gnome sort
• goobi
• graph
• graph coloring
• graph concentration
• graph drawing
• graph isomorphism
• graph partition
• Gray code
• greatest common divisor
• greedy algorithm
• greedy heuristic
• grid drawing
• grid file
• Grover's algorithm

[править] H

• Hamiltonian cycle
• Hamiltonian path
• Hamming distance
• hash function
• hash heap
• hash table
• hash table delete
• Hausdorff distance
• hB-tree
• head
• heap
• heapify
• heap property
• heapsort
• heaviest common subsequence
• height
• height-balanced binary search tree
• height-balanced tree
• Herter-Heighway Dragon
• heuristic
• hidden Markov model
• highest common factor
• Hilbert curve
• histogram sort
• HMM
• homeomorphic
• horizontal visibility map
• Horner's rule
• Horspool
• Huffman encoding
• Hungarian algorithm
• hybrid algorithm
• hyperedge
• hypergraph

[править] I

• ID
• ideal merge
• implication
• implies
• in-branching
• inclusion-exclusion principle
• inclusive or
• incompressible string
• in-degree
• independent set
• index file
• information theoretic bound
• in-order traversal
• in-place sort
• insertion sort
• instantaneous description
• integer linear program
• integer multi-commodity flow
• integer polyhedron
• interactive proof system
• interior-based representation
• internal node
• internal sort
• interpolation search
• interpolation-sequential search
• interpolation sort
• intersection
• interval tree
• intractable
• introsort
• introspective sort
• inverse Ackermann function
• inverted file index
• inverted index
• irreflexive
• isomorphic
• iteration

[править] J

• Jaro-Winkler
• Johnson's algorithm
• Johnson-Trotter
• J sort
• jump list
• jump search

[править] K

• Karmarkar's algorithm
• Karnaugh map
• Karp-Rabin
• Karp reduction
• k-ary heap
• k-ary Huffman encoding
• k-ary tree
• k-clustering
• k-coloring
• k-connected graph
• k-d-B-tree
• k-dimensional
• K-dominant match
• k-d tree
• key
• KMP
• KmpSkip Search
• knapsack problem
• knight's tour
• Knuth-Morris-Pratt algorithm
• Königsberg bridges problem
• Kolmogorov complexity
• Kraft's inequality
• Kripke structure
• Kruskal's algorithm
• kth order Fibonacci numbers
• kth shortest path
• kth smallest element
• KV diagram
• k-way merge
• k-way merge sort
• k-way tree

[править] L

• labeled graph
• language
• last-in, first-out
• Las Vegas algorithm
• lattice
• layered graph
• LCM
• LCS
• leaf
• least common multiple
• leftist tree
• left rotation
• Lempel-Ziv-Welch
• level-order traversal
• Levenshtein distance
• lexicographical order
• LIFO
• linear
• linear congruential generator
• linear hash
• linear insertion sort
• linear order
• linear probing
• linear probing sort
• linear product
• linear program
• linear quadtree
• linear search
• link
• linked list
• list
• list contraction
• little-o notation
• Lm distance
• load factor
• local alignment
• local optimum
• logarithm, logarithmic scale
• longest common subsequence
• longest common substring
• Lotka's law
• lower bound
• lower triangular matrix
• lowest common ancestor
• l-reduction
• lucky sort
• LZW

[править] M

• Malhotra-Kumar-Maheshwari blocking flow
• Manhattan distance
• many-one reduction
• Markov chain
• Marlena
• marriage problem
• Master theorem
• matched edge
• matched vertex
• matching
• matrix
• matrix-chain multiplication problem
• max-heap property
• maximal independent set
• maximally connected component
• Maximal Shift
• maximum bipartite matching
• maximum-flow problem
• MAX-SNP
• MBB
• Mealy machine
• mean
• median
• meld
• memoization
• merge
• merge sort
• meromorphic function
• metaheuristic
• metaphone
• midrange
• Miller-Rabin
• min-heap property
• minimal perfect hashing
• minimum bounding box
• minimum cut
• minimum path cover
• minimum spanning tree (Минимальное покрывающее дерево)
• minimum vertex cut
• mixed integer linear program
• mode
• model checking
• model of computation
• moderately exponential
• MODIFIND
• monotone priority queue
• monotonically decreasing
• monotonically increasing
• Monte Carlo algorithm
• Moore machine
• Morris-Pratt
• move
• move-to-front heuristic
• move-to-root heuristic
• MST
• multi-commodity flow
• multigraph
• multilayer grid file
• multiplication method
• multiprefix
• multiprocessor model
• multiset
• multi suffix tree
• multiway decision
• multiway merge
• multiway search tree
• multiway tree
• Munkres' assignment algorithm

[править] N

• naive string search
• nand
• n-ary function
• NC
• NC many-one reducibility
• nearest neighbor
• negation
• network flow
• network flow problem
• next state
• NFA
• NFTA
• NIST
• node
• nonbalanced merge
• nonbalanced merge sort
• nondeterministic
• nondeterministic algorithm
• nondeterministic finite automaton
• nondeterministic finite state machine
• nondeterministic finite tree automaton
• nondeterministic polynomial time
• nondeterministic tree automaton
• nondeterministic Turing machine
• nonterminal node
• nor
• not
• Not So Naive
• NP
• NP-complete
• NP-complete language
• NP-hard
• n queens
• nullary function
• null tree
• NYSIIS
• NULL

[править] O

• OBDD
• objective function
• occurrence
• octree
• off-line algorithm
• offset
• omega
• omicron
• one-based indexing
• one-dimensional
• online algorithm
• open addressing
• optimal
• optimal cost
• optimal hashing
• optimal merge
• optimal mismatch
• optimal polygon triangulation problem
• optimal polyphase merge
• optimal polyphase merge sort
• optimal solution
• optimal triangulation problem
• optimal value
• optimization problem
• or
• oracle set
• oracle tape
• oracle Turing machine
• order
• ordered array
• ordered binary decision diagram
• ordered linked list
• ordered tree
• order preserving hash
• order preserving minimal perfect hashing
• oriented acyclic graph
• oriented graph
• oriented tree
• orthogonal drawing
• orthogonal lists
• orthogonally convex rectilinear polygon
• oscillating merge sort
• out-branching
• out-degree
• overlapping subproblems

[править] P

• Проблема зависания
• packing
• padding argument
• pagoda
• pairing heap
• PAM
• parallel computation thesis
• parallel prefix computation
• parallel random-access machine
• parametric searching
• parent
• partial function
• partially decidable problem
• partially dynamic graph problem
• partially ordered set
• partially persistent data structure
• partial order
• partial recursive function
• partition
• passive data structure
• patience sorting
• path
• path cover
• path system problem
• Patricia tree
• pattern
• pattern element
• P-complete
• PCP
• PDA
• Peano curve
• Pearson's hash
• perfect binary tree
• perfect hashing
• perfect k-ary tree
• perfect matching
• perfect shuffle
• performance guarantee
• performance ratio
• permutation
• persistent data structure
• phonetic coding
• pile
• pipelined divide and conquer
• planar graph
• planarization
• planar straight-line graph
• PLOP-hashing
• point access method
• pointer jumping
• pointer machine
• poissonization
• polychotomy
• polyhedron
• polylogarithmic
• polynomial
• polynomial approximation scheme
• polynomial hierarchy
• polynomial time
• polynomial-time Church-Turing thesis
• polynomial-time reduction
• polyphase merge
• polyphase merge sort
• polytope
• poset
• postfix traversal
• Post machine
• postman's sort
• postorder traversal
• Post's correspondence problem
• potential function
• PRAM
• predicate
• prefix
• prefix code
• prefix computation
• prefix sums
• prefix traversal
• preorder traversal
• primary clustering
• primitive recursive
• Prim's algorithm
• principle of optimality
• priority queue
• prisoner's dilemma
• PRNG
• probabilistic algorithm
• probabilistically checkable proof
• probabilistic Turing machine
• probe sequence
• procedure
• process algebra
• proper
• proper binary tree
• proper coloring
• proper subset
• property list
• prune and search
• pseudo-random number generator
• PTAS
• pth order Fibonacci numbers
• P-tree
• purely functional language
• pushdown automaton
• pushdown transducer
• p-way merge sort

[править] Q

• qm sort
• q sort
• quadratic probing
• quadtree
• quadtree complexity theorem
• quad trie
• quantum computation
• queue
• quick search
• quicksort

[править] R

• Rabin-Karp
• radix quicksort
• radix sort
• ragged matrix
• Raita
• random access machine
• randomization
• randomized algorithm
• randomized binary search tree
• randomized complexity
• randomized polynomial time
• randomized rounding
• randomized search tree
• Randomized-Select
• random number generator
• random sampling
• range
• range sort
• rank
• Ratcliff/Obershelp pattern recognition
• RBST
• reachable
• rebalance
• recognizer
• rectangular matrix
• rectilinear
• rectilinear Steiner tree
• recurrence equations
• recurrence relation
• recursion
• recursion termination
• recursion tree
• recursive
• recursive data structure
• recursive doubling
• recursive language
• recursively enumerable language
• recursively solvable
• red-black tree
• reduced basis
• reduced digraph
• reduced ordered binary decision diagram
• reduction
• reflexive relation
• regular decomposition
• rehashing
• relation
• relational structure
• relative performance guarantee
• relaxation
• relaxed balance
• rescalable
• restricted universe sort
• result cache
• Reverse Colussi
• Reverse Factor
• R-file
• Rice's method
• right rotation
• right-threaded tree
• RNG
• ROBDD
• root
• root balance
• rooted tree
• rotate left
• rotate right
• rotation
• rough graph
• RP
• R±tree
• R*-tree
• R-tree
• run time

[править] S

• saguaro stack
• saturated edge
• SBB tree
• scan
• scapegoat tree
• search
• search tree
• search tree property
• secant search
• secondary clustering
• memory segment
• Select
• select and partition
• selection problem
• selection sort
• select kth element
• select mode
• self-loop
• self-organizing heuristic
• self-organizing list
• self-organizing sequential search
• semidefinite programming
• separate chaining hashing
• separation theorem
• sequential search
• set
• set cover
• set packing
• shadow heap
• shadow merge
• shadow merge insert
• shaker sort
• Shannon-Fano coding
• shared memory
• Shell sort
• Shift-Or
• Shor's algorithm
• shortcutting
• shortest common supersequence
• shortest common superstring
• shortest path
• shortest spanning tree
• shuffle
• shuffle sort
• sibling
• Sierpinski curve
• Sierpinski triangle
• sieve of Eratosthenes
• sift up
• signature
• Simon's algorithm
• simple merge
• simple path
• simple uniform hashing
• simplex communication
• simulated annealing
• simulation theorem
• single-destination shortest-path problem
• single-pair shortest-path problem
• single program multiple data
• single-source shortest-path problem
• singly linked list
• singularity analysis
• sink
• sinking sort
• skd-tree
• skew symmetry
• skip list
• skip search
• slope selection
• Smith algorithm
• Smith-Waterman algorithm
• smoothsort
• solvable
• sort
• sorted array
• sorted list
• sort in place
• sort merge
• soundex
• source
• space-constructible function
• spanning tree
• sparse graph
• sparse matrix
• sparsification
• sparsity
• spatial access method
• spectral test
• splay tree
• SPMD
• square matrix
• square root
• SST
• stable
• stack
• stack tree
• star-shaped polygon
• start state
• state
• state machine
• state transition
• static
• static Huffman encoding
• s-t cut
• st-digraph
• Steiner minimum tree
• Steiner point
• Steiner ratio
• Steiner tree
• Steiner vertex
• Steinhaus-Johnson-Trotter
• Stirling's approximation
• Stirling's formula
• stooge sort
• straight-line drawing
• strand sort
• strictly decreasing
• strictly increasing
• strictly lower triangular matrix
• strictly upper triangular matrix
• string
• string editing problem
• string matching
• string matching on ordered alphabets
• string matching with errors
• string matching with mismatches
• string searching
• strip packing
• strongly connected component
• strongly connected graph
• strongly NP-hard
• subadditive ergodic theorem
• subgraph
• subgraph isomorphism
• sublinear time algorithm
• subsequence
• subset
• substring
• subtree
• suffix
• suffix array
• suffix automaton
• suffix tree
• superimposed code
• superset
• supersink
• supersource
• symmetric relation
• symmetrically linked list
• symmetric binary B-tree
• symmetric set difference
• symmetry breaking

[править] T

• tail
• tail recursion
• target
• temporal logic
• terminal
• terminal node
• ternary search tree
• text
• text searching
• theta
• threaded binary tree
• threaded tree
• three-dimensional
• three-way merge sort
• three-way radix quicksort
• time-constructible function
• time/space complexity
• top-down radix sort
• top-down tree automaton
• topological order
• topological sort
• topology tree
• total function
• totally decidable language
• totally decidable problem
• totally undecidable problem
• total order
• tour
• tournament
• towers of Hanoi
• tractable
• transducer
• transition
• transition function
• transitive relation
• transitive closure
• transitive reduction
• transpose sequential search
• traveling salesman
• treap
• tree
• tree automaton
• tree contraction
• tree editing problem
• tree sort
• tree traversal
• triangle inequality
• triconnected graph
• trie
• trinary function
• tripartition
• TSP
• TST
• Turbo-BM
• Turbo Reverse Factor
• Turing machine
• Turing reduction
• Turing transducer
• twin grid file
• two-dimensional
• two-level grid file
• 2-3-4 tree
• 2-3 tree
• Two Way algorithm
• two-way linked list
• two-way merge sort

[править] U

• UKP
• unary function
• unbounded knapsack problem
• uncomputable function
• uncomputable problem
• undecidable
• undecidable language
• undecidable problem
• undirected graph
• uniform circuit complexity
• uniform circuit family
• uniform hashing
• uniform matrix
• union
• union of automata
• universal hashing
• universal state
• universal Turing machine
• universe
• UnShuffle sort
• unsolvable problem
• unsorted list
• upper triangular matrix

[править] V

• Van Emde Boas priority queue
• vehicle routing problem
• Veitch diagram
• Venn diagram
• vertex
• vertex coloring
• vertex connectivity
• vertex cover
• vertical visibility map
• virtual hashing
• visibility map
• visible
• Viterbi algorithm
• VRP

[править] W

• walk
• weak-heap
• weak-heap sort
• weight-balanced tree
• weighted, directed graph
• weighted graph
• window
• witness
• work
• work-depth model
• work-efficient
• work-preserving
• worst case
• worst-case cost
• worst-case minimum access

[править] X

• xor

[править] Y

• Yule distribution

[править] Z

• Zeller's congruence
• 0-ary function
• 0-based indexing
• 0/1 knapsack problem
• Zhu-Takaoka
• Zipfian distribution
• Zipf's law
• zipper
• ZPP