Daftar algoritme

Berikut adalah daftar algoritme.

Lihat juga daftar struktur data, daftar topik umum algoritme, dan daftar istilah yang berhubungan dengan algoritme dan struktur data.

Algoritme kombinatorial

Algoritme kombinatorial umum

  • Algoritme pencari-siklus Floyd: iterasi untuk mencari siklus dalam barisan/sekuens
  • (uniformly distributed) Pseudorandom number generators:
    • Blum Blum Shub
    • Mersenne twister
  • Robinson-Schensted algorithm: korespondensi dan pasangan yang bijetif dari Young tableaux yang standar

Algoritme graf

  • Algoritme Bellman-Ford: menghitung jarak terpendek pada graf berbobot, di mana sisi bisa memiliki bobot negatif
  • Algoritme Dijkstra: menghitung jarak terpendek pada graf berbobot, tanpa sisi berbobot negatif.
  • Algoritme Floyd-Warshall: menghitung solusi jarak terpendek untuk semua pasang titik pada sebuah graf berarah dan berbobot
  • Algoritme Kruskal: mencari pohon rentang minimum pada sebuah graf
  • Algoritme Prim: mencari pohon rentang minimum pada sebuah graf
  • Algoritme Boruvka: mencari pohon rentang minimum pada sebuah graf
  • Algoritme Ford-Fulkerson: menghitung aliran maksimal di dalam graf
  • Algoritme Edmonds-Karp: implementasi dari Ford-Fulkerson
  • Nonblocking Minimal Spanning Switch say, for a telephone exchange
  • Spring based algorithm: algoritme untuk penggambaran draf
  • Topological sort
  • Algoritme Hungaria: algorithm for finding a perfect matching

Algoritme pencarian

  • Pencarian linear: mencari sebuah item pada sebuah list tak berurut
  • Algoritme seleksi: mencari item ke-k pada sebuah list
  • Pencarian biner: menemukan sebuah item pada sebuah list terurut
  • Pohon Pencarian Biner
  • Pencarian Breadth-first: menelusuri sebuah graf tingkatan demi tingkatan
  • Pencarian Depth-first: menelusuri sebuah graf cabang demi cabang
  • Pencarian Best-first: menelusuri sebuah graf dengan urutan sesuai kepentingan dengan menggunakan antrian prioritas
  • Pencarian pohon A*: kasus khusus dari pencarian best-first
  • Pencarian Prediktif: pencarian mirip biner dengan faktor pada magnitudo dari syarat pencarian terhadap nilai atas dan bawah dalam pencarian. Kadang-kadang disebut pencarian kamus atau pencarian interpolasi.
  • Tabel Hash: mencari sebuah item dalam sebuah kumpulan tak berurut dalam waktu O(1).

Algoritme string

Pencarian

Pencocokan string

Algoritme penyusunan

  • Binary tree sort
  • Bogosort
  • Bubble sort: untik setiap pasangan, tukar item tersebut
  • Bucket sort
  • Comb sort
  • Cocktail sort
  • Counting sort
  • Gnome sort
  • Heapsort: mengubah list menjadi heap, lalu pindah yang terbesar kepada daftar.
  • Insertion sort: menentukan dimana item tertentu termasuk dalam list yang ter-urut, dan menyisipkan padanya
  • Merge sort: pisah daftar menjadi pasangan dua-dua, urutkan lalu digabung dengan satu pasangan lainnya, kembali diurutkan, dan diulang hingga menjadi daftar utuh
  • Pancake sorting
  • Pigeonhole sort
  • Quicksort: pisah daftar menjadi dua daftar, yang satu lebih rendah yang satu lebih besar, dan urut terpisah.
  • Radix sort: sorts strings letter by letter
  • Selection sort: pick the smallest of the remaining elements, add it to the end of the sorted list
  • Shell sort: an attempt to improve insertion sort
  • Smoothsort
  • Stupid sort
  • Topological sort

Kompresi data

Kompresi data tanpa kehilangan

  • Burrows-Wheeler transform: preprocessing useful for improving lossless compression
  • DEFLATE: lossless data compression
  • Delta encoding: aid to compression of data in which sequential data occurs frequently
  • Incremental encoding: delta encoding applied to sequences of strings
  • LZW: singkatan dari (Lempel-Ziv-Welch)
  • LZ77 (algorithm): LZ77 and LZ78 are the names for the two lossless data compression algorithms
  • LZMA: singkatan dari Lempel-Ziv-Markov chain-Algorithm
  • LZO: pemadatan data yang cepat
  • PPM compression algorithm
  • Shannon-Fano coding
  • Truncated binary encoding
  • Run-length encoding: pemadatan data yang menggunakan deretan huruf yang berulang.
  • SEQUITUR algorithm: lossless compression by incremental grammar inference on a string
  • EZW (Embedded Zerotree Wavelet)
  • Entropy encoding: coding scheme that assigns codes to symbols so as to match code lengths with the probabilities of the symbols
    • Huffman coding: simple lossless compression taking advantage of relative character frequencies
      • Adaptive Huffman coding: adaptive coding technique based on Huffman coding
    • Arithmetic coding: advanced entropy coding
    • Range encoding: data compression method that is believed to approach the compression ratio of arithmetic coding
  • Entropy coding with known entropy characteristics
    • Unary coding: code that represents a number n with n ones followed by a zero
    • Elias delta|gamma|omega coding: universal code encoding the positive integers
    • Fibonacci coding: universal code which encodes positive integers into binary code words
    • Golomb coding: form of entropy coding that is optimal for alphabets following geometric distributions
    • Rice coding: form of entropy coding that is optimal for alphabets following geometric distributions

Kompresi data berkehilangan

  • Linear predictive coding: lossy compression by representing the spectral envelope of a digital signal of speech in compressed form
  • A-law algorithm: standard companding algorithm
  • Mu-law algorithm: standard analog signal compression or companding algorithm
  • Fractal compression: method used to compress images using fractals
  • Transform coding: type of data compression for "natural" data like audio signals or photographic images
  • Vector quantization: technique often used in lossy data compression
  • Wavelet compression: form of data compression well suited for image compression (sometimes also video compression and audio compression)

Computational geometry

  • Gift wrapping algorithm: determining the convex hull of a set of points
  • Graham scan determining the convex hull of a set of points in the plane
  • Point in polygon: tests whether a given point lies within a given polygon

Grafik komputer

  • Bresenham's line algorithm: plots points of a 2-dimensional array to form a straight line between 2 specified points (uses decision variables)
  • DDA line algorithm: plots points of a 2-dimensional array to form a straight line between 2 specified points (uses floating-point math)
  • Flood fill: fills a connected region of a multi-dimensional array with a specified symbol
  • Painter's algorithm: detects visible parts of a 3-dimensional scenery
  • Ray tracing: realistic image rendering

Algoritme Kriptografi

Lihat juga Topik dalam kriptografi

  • Enkripsi simetris dengan kata kunci:
  • Enkripsi asimetris dengan kunci publik atau tanda tangan digital:
    • DSA
    • ElGamal
    • RSA
    • Diffie-Hellman key exchange
    • NTRUEncrypt
  • Cryptographic Message digest functions:
    • MD5 – Sekarang ini sudah terdapat algoritme yang mampu memalsukan jumlah MD5.[1]
    • RIPEMD-160
    • SHA-1
    • HMAC: keyed-hash message authentication
  • Perhitungan nomor acak tentu yang aman untuk persandian (Cryptographically secure pseudo-random number generator)
    • Blum Blum Shub - berdasarkan faktorisasi prima.
    • Yarrow algorithm
    • Fortuna, allegedly an improvement on Yarrow
  • Other
    • Diffie-Hellman: key exchange

Algoritme Distributed systems

  • Lamport ordering: a partial ordering of events based on the happened-before relation
  • Snapshot algorithm: a snapshot is the process of recording the global state of a system
  • Vector ordering: a total ordering of events

Algoritme Numerik

See also main article numerical analysis and list of numerical analysis topics

  • Algoritme De Boor: computes splines.
  • Algoritme de Casteljau: melakukan perhitungan kurva Bézier
  • False position method: approximates roots of a function
  • Eliminasi Gauss-Jordan: menyelesaikan sistem persamaan linear
  • Algoritme Gauss-Legendre: computes the digits of pi
  • Gauss-Newton algorithm: find minimum of function of several variables
  • Penambahan Kahan: menambahkan bilangan-bilangan titik mengambang dengan ketelitian lebih
  • Levenberg-Marquardt algorithm: find minimum of function of several variables
  • MISER algorithm: Monte Carlo simulation, numerical integration
  • Newton's method: finds zeros of functions with calculus
  • Bracketing Methods:
  • Pembulatan: membulatkan bilangan pecah
  • Secant method: approximates roots of a function
  • Shifting nth-root algorithm: digit by digit root extraction
  • Akar persegi: menghitungkan akar persegi dengan ketelitian terbatas
  • Strassen algorithm

Optimization algorithms

  • Simplex algorithm: An algorithm for solving the linear programming problem
  • Branch and bound
  • Simulated annealing
  • Genetic algorithms
  • Particle swarm
  • Tabu search
  • Local search

Digital signal processing

  • CORDIC: Fast trigonometric function computation technique.
  • Fast Fourier transform: determines the frequencies contained in a (segment of a) signal
    • Cooley-Tukey FFT algorithm
  • Rainflow-counting algorithm: Reduces a complex stress history to a count of elementary stress-reversals for use in fatigue analysis
  • Osem: algorithm for processing of medical images
  • Goertzel algorithm Can be used for DTMF digit decoding.
  • [[Discrete Fourier transform[2]** Rader's FFT algorithm
    • Bluestein's FFT algorithm

Number theoretic algorithms

  • Discrete logarithm:
    • Baby-step giant-step
    • Pollard's rho algorithm for logarithms
    • Pohlig-Hellman algorithm
    • Index calculus algorithm
  • Euclidean algorithm: computes the greatest common divisor
  • Faktorisasi prima: pemecahan bilangan bulat menjadi faktor prima.
    • Trial division
    • Faktorisasi kurva eliptik Lenstra
    • Pollard's rho algorithm
    • Pollard's p-1 algorithm
    • Congruence of squares
    • Quadratic sieve
    • Special number field sieve
    • General number field sieve
    • Jones's period proxy algorithm
  • Algoritme perkalian: cara perkalian dua bilangan yang cepat.
  • Ujian bilangan prima: menentukan apakah suatu bilangan adalah bilangan prima.
    • AKS primality test
    • Miller-Rabin primality test
    • Sieve of Eratosthenes
    • Sieve of Atkin

Numerical algebra

  • Buchberger's algorithm: finds a Gröbner basis
  • Eigenvalue algorithm
  • Exponentiating by squaring: quickly computes powers of numbers and matrices
  • Gram-Schmidt process: orthogonalizes a set of vectors
  • Knuth-Bendix completion algorithm: for rewriting rule systems
  • Multivariate division algorithm: for polynomials in several indeterminates

Parsing

  • Recursive descent parser: A top-down parser suitable for LL(k) grammars
  • LL parser: A relatively simple linear time parsing algorithm for a limited class of context-free grammars
  • LR parser: A more complex linear time parsing algorithm for a larger class of context-free grammars. Variants:
    • Operator-precedence parser
    • SLR (Simple LR) parser
    • LALR (Look-ahead LR) parser
    • Canonical LR parser
  • Packrat parser: A linear time parsing algorithm supporting some context-free grammars and parsing expression grammars
  • CYK algorithm: An O(n3) algorithm for parsing any context-free grammar
  • Earley's algorithm: Another O(n3) algorithm for parsing any context-free grammar

Teknik perangkat lunak

  • Algorithms for Recovery and Isolation Exploiting Semantics: recovery
  • Unicode Collation Algorithm
  • CHS conversion: Converting between disk addressing systems
  • Cyclic redundancy check: calculation of a check word
  • Parity: Simple/fast error detection technique. Is a number even or odd?
  • Diff: compare two sequences. An example of Dynamic programming (dynamic refers to the property that the optimal solution can be constructed by combining optimal solutions to sub-problems e.g. quicksort).

Algoritme kuantum

Application of quantum computation to various categories of problems and algorithms

  • Grover's algorithm: provides quadratic speedup for many search problems
  • Shor's algorithm: provides exponential speedup for factorizing a number
  • Deutsch-Jozsa algorithm: criterion of balance for Boolean function

Algoritme medis

  • Medical algorithm
  • Texas Medication Algorithm Project

Lainnya

  • Astronomical algorithms
  • Banker's algorithm
  • Algoritme Baum-Welch
  • Doomsday algorithm: day of the week
  • Levenberg-Marquardt nonlinear least squares fitting algorithm
  • Marzullo's algorithm: distributed clock synchronization
  • Page replacement algorithms
  • Risch algorithm
  • Schreier-Sims algorithm
  • Todd-Coxeter algorithm
  • Viterbi algorithm
  • Penukaran XOR: menukar nilainya dua variabel tanpa menggunakan variabel sementara
  • Algoritme merge
  • Algoritme penggantian halaman

Referensi

  1. ^ Presentasi pemalsuan jumlah MD5
  2. ^ frequency domain ICA