Thành viên:Hoàng Cầm/Thuật ngữ cấu trúc dữ liệu và giải thuật

Thuật ngữ cấu trúc dữ liệu và giải thuật

Trong NIST Dictionary of Algorithms and Data Structures (NIST -National Institute of Standards and Technology có định nghĩa cho khá nhiều (nhưng chưa đủ) các thuật ngữ cấu trúc dữ liệu và giải thuật. Bài này liệt kê ra các thuật ngữ bằng tiếng Anh để tiện tra cứu.

A

• absolute performance guarantee
• abstract data type  : Kiểu dữ kiệu trừu tượng.
• (a,b)-tree: Cây (a,b)
• accepting state
• Ackermann's function: Hàm Ackermann
• active data structure: Cấu trúc dự liệu chủ động
• acyclic directed graph: Đồ thị không chu trình có hướng
• acyclic graph: Đồ thị không chu trình
• adaptive heap sort: Sắp xếp đống cải tiến.
• adaptive Huffman encoding:Mã Huffman cải tiến.
• adaptive k-d tree:Cây k-d thích ứng.
• adaptive sort:Sắp xếp thích ứng.
• address-calculation sort:Sắp xếp địa chỉ-thống kê
• adjacency-list representation:Biểu diễn danh sách kề
• adjacency-matrix representation:Biểu diễn ma trận kề
• adjacent:kề.
• admissible vertex:vec-tơ có thể bổ xung
• ADT: kiểu dữ liệu trừu tượng.
• adversary:đối lập
• algorithm:giải thuật.
• algorithm B:Giải thuật B.
• algorithm BSTW:Giải thuật BSTW (giải thuật nén dữ liệu do Bentley, Sleator, Tarjan và Wei thiết kế vào năm 1986.
• algorithm FGKGiải thuật FGK (the most notable are FGK (Faller-Gallager-Knuth cho mã Huffman cải tiến)
• algorithmic efficiency:Hiệu quả giải thuật.
• algorithmically solvable:Khả năng giải thuật
• algorithm V: Giải thuật V (Giải thuật mã Huffman cải tiến bởi Vitter.
• all pairs shortest path:Bài toán đường đi ngắn nhất giữa tất cả các cặp đỉnh.
• alphabet: bảng chữ cái.
• Alpha Skip Search algorithm
• alternating path:Đường đi đơn định.
• alternating Turing machine:máy Turing đơn định
• alternation:Đơn định
• American flag sort:
• amortized cost
• ancestor:tổ tiên.
• and:phép toán logic AND.
• ANSI:ANSI (American National Standards Institute or ANSI (đọc "an-see")
• antichain:đối dây xích: antichain in a partially ordered set
• antisymmetric relation:quan hệ phản đối xứng
• AP:Cấp số cộng.
• Apostolico-Crochemore
• Apostolico-Giancarlo algorithm
• approximate string matching:Tìm xâu gần đúng.
• approximation algorithm:Giải thuật gần đúng.
• arborescence:
• arcNgôn ngữ lập trình Arc.
• arithmetic coding:Mã số học.
• array:Mảng.
• array index:Chỉ số mảng.
• array merging:Trộn mảng.
• array search:Tìm kiếm trên mảng.
• articulation point:Điểm khớp.
• assignment problem:Bài toán phân công
• association list:Danh sách kết hợp
• associative:kết hợp
• associative array:Mảng kết hợp.
• asymptotically tight bound: đánh giá tiệm cận tight?
• asymptotic bound: đánh giá tiệm cận
• asymptotic lower bound: đánh giá tiệm cận dưới
• asymptotic space complexity:đánh giá tiệm cận độ phức tạp không gian.
• asymptotic time complexity:đánh giá tiệm cận độ phức tạp thời gian.
• asymptotic upper bound:đánh giá tiệm cận trên.
• augmenting path:đường đi tăng
• automaton:Automat.
• average case:Trường hợp trung bình.
• average-case cost:Giá của tương hợp trung bình.
• AVL tree:Cây AVL(G.M. Adelson-Velsky and E.M. Landis)
• axiomatic semantics:Ý nghĩa tiên đề.

B

• backtracking:bài toán cái túi.
• bag:Cái túi.
• balance:Cân bằng.
• balanced binary search tree:Cây nhị phân tìm kiếm cân bằng.
• balanced binary tree:Cây nhị phân cân bằng.
• balanced k-way merge sort: Sắp xếp trộn k đường cân bằng.
• balanced merge sort:Sắp xếp trộn cân bằng.
• balanced multiway merge:Sắp xếp trộn nhiều đường.
• balanced multiway tree:Cây cân bằng nhều đường.
• balanced quicksort: Sắp xếp nhanh cân bằng.
• balanced tree: Cây cân bằng.
• balanced two-way merge sort:Sắp xếp trộn hai đường cân bằng.
• BANG file: tệp BANG?
• Batcher sort:Sắp xếp theo khối (Batcher ~ Bitonic sort?)
• Baum Welch algorithm:Giải thuật Baum Welch.
• [[BB alpha tree|BB α tree]:]Cây BB alpha.
• BDD: Biểu đồ quyết định nhị phân.
• BD-tree:Cây BD.
• Bellman-Ford algorithm:Giải thuật Bellman-Ford.
• Benford's law:luật Benford.
• best case: trường hợp tốt nhất.
• best-case cost:giá của trường hợp tốt nhất.
• best-first search:tìm kiếm ưu tiên ? tốt nhất.
• biconnected component:thành phần liên thông.
• biconnected graph:đò thị liên thông.
• bidirectional bubble sort:sắp xếp nổi bọt hai chiều.
• big-O notation:ký hiệu O lớn.
• binary function:hàm nhị phân.
• binary GCD algorithm:giải thuật tìm ƯCLN nhị phân.
• binary heap:đống nhị phân.
• binary insertion sort: sắp xếp chèn nhị phân.
• binary knapsack problem:
• binary priority queue:hàng đợi có ưu tiên nhị phân.
• binary relation:quan hệ hai ngôi.
• binary search:tìm kiếm nhị phân.
• binary search tree:cây tìm kiếm nhị phân.
• binary tree:cây nhị phân.
• binary tree representation of trees:cây nhị phân biểu diễn của cây.
• bingo sort:sắp xếp bingo.
• binomial heap:đống nhị thức.
• binomial tree:cây nhị thức.
• bin packing problem:Bài toán sắp xếp túi.
• bin sort:Sắp xếp thùng (~Bucket sort)
• bintree:
• bipartite graph:đồ thị hai phía.
• bipartite matching:
• bisector:chia đôi.
• bitonic sort:sắp xếp khối (sắp xếp theo bít)
• bit vector:vec-tơ bit.
• Bk tree:Cây Bk.
• block:khối
• block addressing index:khối chỉ số tăng
• blocking flow:nền của khối
• block search:tìm kiếm khối
• Bloom filterlọc Bloom
• blossom
• bogosort:Sắp xếp bogo ~stupid sort, bozo sort, blort sort, monkey sort, random sort and drunk man sort
• boogol
• boolean:Boole
• boolean expressionbiểu thức Boole
• boolean function:Hàm Boole
• border:khung? lề
• 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 (algorithm)
• 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
• Damerau-Levenshtein distance
• 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
• Thuật toán Dijkstra
• 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 algorithm
• divide and marriage before conquest
• division method
• Data 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