Algorithm classification: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
Строка 165: Строка 165:
 
## {{level|Ray tracing: Rendering realistic images}}
 
## {{level|Ray tracing: Rendering realistic images}}
 
## {{level|Global illumination: Regarding direct illumination and reflection from other objects}}
 
## {{level|Global illumination: Regarding direct illumination and reflection from other objects}}
−
# <div id="Криптографические алгоритмы">'''Криптографические алгоритмы'''</div>
+
# <div id="Криптографические алгоритмы">'''Cryptographic algorithms'''</div>
−
# <div id="Нейронные сети">'''Нейронные сети'''</div>
+
# <div id="Нейронные сети">'''Neural networks'''</div>
−
# <div id="Алгоритмы оптимизации">'''Алгоритмы оптимизации'''</div>
+
# <div id="Алгоритмы оптимизации">'''Optimization algorithms'''</div>
−
## {{level|Линейное программирование}}
+
## {{level|Linear programming}}
−
## {{level|Симплекс-метод}}
+
## {{level|Simplex algorithm}}
−
## {{level|Метод ветвей и границ (последовательный и параллельный варианты)}}
+
## {{level|Branch and bound method (serial and parallel variants)}}
−
## {{level|Генетические алгоритмы}}
+
## {{level|Genetic algorithms}}
−
## {{level|Муравьиные алгоритмы}}
+
## {{level|Ant colony algorithms}}
−
## {{level|Комбинированные алгоритмы}}
+
## {{level|Hybrid algorithms}}
 
## {{level|Нахождение экстремума функции}}
 
## {{level|Нахождение экстремума функции}}
 
# <div id="Алгоритмы теории игр">'''Алгоритмы теории игр'''</div>
 
# <div id="Алгоритмы теории игр">'''Алгоритмы теории игр'''</div>

Версия 18:44, 9 апреля 2016

  1. Vector operations
    1. Pairwise summation
      1. Summing an array by pairwise summation
      2. Finding partial sums of an array by pairwise summation
    2. Uniform norm of a vector: Real version, serial-parallel variant
    3. Dot product: Real version, serial-parallel variant
    4. Serial-parallel summation method
  2. Matrix-vector operations
    1. Dense matrix-vector multiplication
  3. Matrix operations
    1. Dense matrix multiplication
  4. Matrix decompositions
    1. Triangular decompositions
      1. Gaussian elimination (finding the LU decomposition)
        1. Gaussian elimination without pivoting
          1. LU decomposition via Gaussian elimination
          2. Compact scheme for Gaussian elimination and its modifications
            1. Compact scheme for Gaussian elimination: Dense matrix
            2. Compact scheme for Gaussian elimination and its modifications: Tridiagonal matrix
              1. Compact scheme for Gaussian elimination: Tridiagonal matrix, serial variant
              2. Stone doubling algorithm for the LU decomposition of a tridiagonal matrix
              3. Serial-parallel algorithm for the LU decomposition of a tridiagonal matrix
        2. Gaussian elimination with pivoting
          1. Gaussian elimination with column pivoting
          2. Gaussian elimination with row pivoting
          3. Gaussian elimination with diagonal pivoting
          4. Gaussian elimination with complete pivoting
      2. Cholesky method (finding the symmetric triangular decomposition)
        1. Cholesky decomposition (square root method): Basic pointwise real variant, dense symmetric positive definite matrix
      3. Available triangular decompositions for matrices of special form
    2. Unitary-triangular decompositions
      1. Givens method (rotation method) for the QR-decomposition of a matrix
      2. Householder method (reflection method) for the QR-decomposition of a matrix
    3. Unitary Hessenberg decompositions
      1. Householder method (reflection method) for reducing a matrix to Hessenberg (bidiagonal) form
      2. Givens method (rotation method) for reducing a matrix to Hessenberg (bidiagonal) form
    4. Unitary-diagonal decompositions
      1. Eigenvalue decomposition (finding eigenvalues and eigenvectors)
      2. Singular value decomposition (finding singular values and singular vectors)
  5. Solving systems of linear algebraic equations (SLAEs)
    1. Direct methods for solving SLAEs
      1. Уровень алгоритма Linpack benchmark
      2. Methods for solving SLAEs of special forms
        1. Methods for solving triangular SLAEs
          1. Forward substitution (real version)
          2. Backward substitution (real version)
          3. Methods for solving bidiagonal SLAEs
            1. Forward and backward substitution for bidiagonal SLAEs
            2. Stone doubling algorithm for solving bidiagonal SLAEs
            3. Serial-parallel variant of the backward substitution
        2. Methods for solving tridiagonal SLAEs
          1. Methods based on the conventional LU decomposition
            1. Thomas algorithm
              1. Thomas algorithm, pointwise version
              2. Repeated Thomas algorithm, pointwise version
            2. Stone doubling algorithm
            3. Serial-parallel method for solving tridiagonal SLAEs based on the LU decomposition and backward substitutions
          2. Other methods
            1. Reduction method
              1. Complete reduction method
              2. Reduction method repeated for a new right-hand side
            2. Two-sided Thomas algorithm
              1. Two-sided Thomas algorithm, pointwise version
              2. Repeated two-sided Thomas algorithm, pointwise version
            3. Cyclic reduction
              1. Complete cyclic reduction
              2. Cyclic reduction repeated for a new right-hand side
            4. Bordering method
        3. Methods for solving block triangular SLAEs
          1. Block forward substitution (real version)
          2. Block backward substitution (real version))
          3. Methods for solving block bidiagonal SLAEs
            1. Forward and backward substitution for block bidiagonal SLAEs
            2. Stone doubling algorithm for solving block bidiagonal SLAEs
            3. Serial-parallel variant of the block backward substitution for solving block bidiagonal SLAEs
        4. Methods for solving block tridiagonal SLAEs
          1. Methods based on the conventional LU decomposition
            1. Block Thomas algorithm
            2. Serial-parallel method for solving block SLAEs based on the LU decomposition and backward substitutions
          2. Other methods
            1. Two-sided Thomas algorithm, block variant
            2. Block cyclic reduction
            3. Block bordering method
      3. Solving SLAEs with coefficient matrices of special form whose inverses are known
    2. Iterative methods for solving SLAEs
      1. Уровень алгоритма High Performance Conjugate Gradient (HPCG) benchmark
  6. Solving eigenvalue problems
    1. Eigenvalue decomposition (finding eigenvalues and eigenvectors)
      1. QR algorithm
      2. Givens method (rotation method) for solving the symmetric eigenvalue problem
    2. Singular value decomposition (finding singular values and singular vectors)
  7. Computer performance tests
    1. Уровень алгоритма High Performance Conjugate Gradient (HPCG) benchmark
    2. Уровень алгоритма Linpack benchmark
  8. Fourier transform
    1. Fast Fourier transform for powers of two
  9. Algebra of polynomials
    1. Horner's rule: Real version, serial variant
  10. Numerical quadrature
    1. Cubature rules
    2. Numerical quadrature (cubature) rules on an interval (for a multidimensional cube)
      1. Numerical quadrature (cubature) rules on an interval (for a multidimensional cube)#Mathematical description
      2. Numerical quadrature (cubature) rules on an interval (for a multidimensional cube)#Mathematical description
      3. Numerical quadrature (cubature) rules on an interval (for a multidimensional cube)#Mathematical description
      4. Numerical quadrature (cubature) rules on an interval (for a multidimensional cube)#Mathematical description
  11. Graph algorithms
    1. Traversing a graph
      1. Breadth-first search (BFS)
      2. Depth-first search (DFS)
    2. Single source shortest path (SSSP)
      1. Breadth-first search (BFS) (for unweighted graphs)
      2. Dijkstra's algorithm
      3. Bellman-Ford algorithm
      4. Δ-stepping algorithm
    3. All pairs shortest path (APSP)
      1. Johnson's algorithm
      2. Floyd-Warshall algorithm
    4. Transitive closure of a directed graph
      1. Purdom's algorithm
    5. Longest shortest path
    6. Construction of the minimum spanning tree (MST)
      1. Boruvka's akgorithm
      2. Kruskal's algorithm
      3. Prim's algorithm
      4. GHS algorithm
    7. Search for isomorphic subgraphs
      1. Ullman's algorithm
      2. VF2 algorithm
    8. Graph connectivity
      1. Shiloach-Vishkin algorithm for finding the connected components
      2. Disjoint set union
      3. Tarjan's strongly connected components algorithm
      4. DCSC algorithm for finding the strongly connected components
      5. Tarjan's biconnected components algorithm
      6. Tarjan-Vishkin biconnected components algorithm
      7. Tarjan's algorithm for finding the bridges of a graph
      8. Vertex connectivity of a graph
      9. Gabow's edge connectivity algorithm
    9. Finding maximal flow in a transportation network
      1. Ford–Fulkerson algorithm
      2. Preflow-Push algorithm
    10. Finding minimal-cost flow in a transportation network
    11. Assignment problem
      1. Hungarian algorithm
      2. Auction algorithm
      3. Hopcroft–Karp algorithm
    12. Betweenness centrality algorithm
  12. Search algorithms
    1. Binary search: Finding the position of a target value within a sorted array, [math]O(log(n))[/math]
  13. Sorting algorithms
    1. Binary tree sort
    2. Bubble sort
    3. Merge sort (serial and parallel variants)
  14. Computational geometry
    1. Finding the diameter of a point set
    2. Finding the convex hull of a point set
    3. Delaunay triangulation
    4. Voronoi diagram
    5. Point-in-polygon problem
    6. Convex polygon intersection - complexity [math]O(n_1 + n_2)[/math]
    7. Star-shaped polygon intersection - complexity [math]O(n_1 * n_2)[/math]
  15. Computer graphics
    1. Line drawing algorithms: Approximating a line segment on discrete graphical media
    2. Determining visible parts of a three-dimensional scene
    3. Ray tracing: Rendering realistic images
    4. Global illumination: Regarding direct illumination and reflection from other objects
  16. Cryptographic algorithms
  17. Neural networks
  18. Optimization algorithms
    1. Linear programming
    2. Simplex algorithm
    3. Branch and bound method (serial and parallel variants)
    4. Genetic algorithms
    5. Ant colony algorithms
    6. Hybrid algorithms
    7. Нахождение экстремума функции
  19. Алгоритмы теории игр
  20. Алгоритмы моделирования квантовых систем
    1. Алгоритмы моделирования квантовых вычислений
      1. Уровень алгоритма Однокубитное преобразование вектора-состояния
      2. Уровень алгоритма Двухкубитное преобразование вектора-состояния
      3. Моделирование квантового преобразования Фурье
  21. Алгоритмы решения уравнений математической физики
    1. Уровень алгоритма Уравнение Пуассона, решение дискретным преобразованием Фурье
  22. Другие алгоритмы
Источник — https://algowiki-project.org/w/ru/index.php?title=Algorithm_classification&oldid=3440