{"id":4669,"date":"2012-04-08T13:05:44","date_gmt":"2012-04-08T11:05:44","guid":{"rendered":"http:\/\/djalil.chafai.net\/blog\/?p=4669"},"modified":"2012-04-29T15:09:33","modified_gmt":"2012-04-29T13:09:33","slug":"algorithms","status":"publish","type":"post","link":"https:\/\/djalil.chafai.net\/blog\/2012\/04\/08\/algorithms\/","title":{"rendered":"Algorithms"},"content":{"rendered":"<p style=\"text-align: center;\"><a href=\"http:\/\/en.wikipedia.org\/wiki\/Mu%E1%B8%A5ammad_ibn_M%C5%ABs%C4%81_al-Khw%C4%81rizm%C4%AB\"><img loading=\"lazy\" class=\"size-medium wp-image-4690 aligncenter\" title=\"\u0627\u0644\u0643\u062a\u0627\u0628 \u0627\u0644\u0645\u062e\u062a\u0635\u0631 \u0641\u064a \u062d\u0633\u0627\u0628 \u0627\u0644\u062c\u0628\u0631 \u0648\u0627\u0644\u0645\u0642\u0627\u0628\u0644\u0629\" src=\"\/blog\/wp-content\/uploads\/2012\/04\/Kitab_hisab_al-gabr_wa-l-muqabala-189x300.jpg\" alt=\"\u0627\u0644\u0643\u062a\u0627\u0628 \u0627\u0644\u0645\u062e\u062a\u0635\u0631 \u0641\u064a \u062d\u0633\u0627\u0628 \u0627\u0644\u062c\u0628\u0631 \u0648\u0627\u0644\u0645\u0642\u0627\u0628\u0644\u0629\" width=\"189\" height=\"300\" srcset=\"https:\/\/djalil.chafai.net\/blog\/wp-content\/uploads\/2012\/04\/Kitab_hisab_al-gabr_wa-l-muqabala-189x300.jpg 189w, https:\/\/djalil.chafai.net\/blog\/wp-content\/uploads\/2012\/04\/Kitab_hisab_al-gabr_wa-l-muqabala.jpg 240w\" sizes=\"(max-width: 189px) 100vw, 189px\" \/><\/a><\/p>\n<p style=\"text-align: justify;\">The success of computers is largely due to the existence of efficient algorithms for solving numerical and combinatorial problems. These algorithms are used billion of times per second. Many users (even among scientists) do not know them. One may find a <a href=\"http:\/\/en.wikipedia.org\/wiki\/List_of_algorithms\">list of algorithms on Wikipedia<\/a>. Depending on your tastes, you may distinguish some favorite ones, for their simplicity, elegance, or versatility. Here are some few of my favorite algorithms and paradigms:<\/p>\n<ul>\n<li><a href=\"http:\/\/en.wikipedia.org\/wiki\/Gram-schmidt\">Gram-Schmidt algorithm<\/a>, <a href=\"http:\/\/en.wikipedia.org\/wiki\/QR_algorithm\">QR algorithm<\/a>, <a href=\"http:\/\/en.wikipedia.org\/wiki\/LU_decomposition\">LU algorithms<\/a><\/li>\n<li><a href=\"http:\/\/en.wikipedia.org\/wiki\/Gauss_elimination\">Gauss elimination<\/a>, <a href=\"http:\/\/en.wikipedia.org\/wiki\/Grobner_basis\">Euclidean algorithm and Gr\u00f6bner bases<\/a><\/li>\n<li><a href=\"http:\/\/en.wikipedia.org\/wiki\/Simplex_algorithm\">Simplex algorithm<\/a>, <a href=\"http:\/\/en.wikipedia.org\/wiki\/Hungarian_algorithm\">Hungarian algorithm<\/a>, <a href=\"http:\/\/en.wikipedia.org\/wiki\/Linear_programming\">linear programming<\/a>, <a href=\"http:\/\/en.wikipedia.org\/wiki\/Hungarian_algorithm\">semi-definite programming<\/a><\/li>\n<li><a href=\"http:\/\/en.wikipedia.org\/wiki\/Gradient_descent\">Gradient descent<\/a>, <a href=\"http:\/\/en.wikipedia.org\/wiki\/Binary_search_algorithm\">binary search<\/a>, <a href=\"http:\/\/en.wikipedia.org\/wiki\/Newton%27s_method\">Newton algorithm<\/a><\/li>\n<li><a href=\"http:\/\/en.wikipedia.org\/wiki\/Robbins-Monro_algorithm\">Robbins-Monro and Kiefer-Wolfowitz stochastic approximation<\/a><\/li>\n<li><a href=\"http:\/\/en.wikipedia.org\/wiki\/Expectation%E2%80%93maximization_algorithm\">Expectation-Maximization<\/a>, <a href=\"http:\/\/en.wikipedia.org\/wiki\/Matching_pursuit\">Matching pursuit<\/a>, <a href=\"http:\/\/en.wikipedia.org\/wiki\/Classification_and_regression_tree\">Classification And Regression Tree<\/a><\/li>\n<li><a href=\"http:\/\/en.wikipedia.org\/wiki\/Fast_fourier_transform\">Fast Fourier Transform algorithm<\/a>, <a href=\"http:\/\/en.wikipedia.org\/wiki\/Fast_wavelet_transform\">Fast Wavelet Transform algorithm<\/a>, <a href=\"http:\/\/en.wikipedia.org\/wiki\/Kalman_filter\">Kalman filter<\/a><\/li>\n<li><a href=\"http:\/\/en.wikipedia.org\/wiki\/Euler_method\">Euler algorithms<\/a>, <a href=\"http:\/\/en.wikipedia.org\/wiki\/Finite_elements\">finite elements algorithms<\/a>, <a href=\"http:\/\/en.wikipedia.org\/wiki\/Finite_volume_method\">finite volume algorithms<\/a><\/li>\n<li><a href=\"http:\/\/en.wikipedia.org\/wiki\/Quick_sort\">Quick sort<\/a>, <a href=\"http:\/\/en.wikipedia.org\/wiki\/Dijkstra%27s_algorithm\">Dijkstra algorithm<\/a>, <a href=\"http:\/\/en.wikipedia.org\/wiki\/Md5\">Message-Digest algorithm<\/a>, <a href=\"http:\/\/en.wikipedia.org\/wiki\/Secure_hash_algorithm\">Secure Hash Algorithm<\/a><\/li>\n<li><a href=\"http:\/\/en.wikipedia.org\/wiki\/Huffman_algorithm\">Huffman coding<\/a>, <a href=\"http:\/\/fr.wikipedia.org\/wiki\/Lempel-Ziv-Welch\">Lempel-Ziv-Welch coding<\/a><\/li>\n<li><a href=\"http:\/\/en.wikipedia.org\/wiki\/Hamming_code\">Hamming coding<\/a>, <a href=\"http:\/\/en.wikipedia.org\/wiki\/Reed%E2%80%93Muller_code\">Reed-Muller coding<\/a>, <a href=\"http:\/\/en.wikipedia.org\/wiki\/LDPC_code\">Gallager coding<\/a><\/li>\n<li><a href=\"http:\/\/en.wikipedia.org\/wiki\/RSA_%28algorithm%29\">Rivest-Shamir-Adleman algorithm<\/a>, <a href=\"http:\/\/en.wikipedia.org\/wiki\/Digital_Signature_Algorithm\">Digital Signature Algorithm<\/a><\/li>\n<li><a href=\"http:\/\/en.wikipedia.org\/wiki\/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm\">Knuth-Morris-Pratt<\/a>, <a href=\"http:\/\/en.wikipedia.org\/wiki\/Rabin%E2%80%93Karp_algorithm\">Rabin-Karp<\/a>, and <a href=\"http:\/\/en.wikipedia.org\/wiki\/Category:String_matching_algorithms\">string matching algorithms<\/a><\/li>\n<li><a href=\"http:\/\/en.wikipedia.org\/wiki\/Miller%E2%80%93Rabin_primality_test\">Miller-Rabin algorithm<\/a>, <a href=\"http:\/\/en.wikipedia.org\/wiki\/Schonhage-Strassen_algorithm\">Schonhage-Strassen algorithm<\/a><\/li>\n<li><a href=\"http:\/\/en.wikipedia.org\/wiki\/Fisher-Yates\">Fisher-Yates-Knuth shuffle<\/a>, <a href=\"http:\/\/en.wikipedia.org\/wiki\/Mersenne_twister\">Mersenne twister<\/a>, <a href=\"http:\/\/en.wikipedia.org\/wiki\/Ziggurat_algorithm\">Marsaglia ziggurat<\/a><\/li>\n<li><a href=\"http:\/\/en.wikipedia.org\/wiki\/Metropolis-Hastings\">Metropolis-Hastings<\/a>, <a href=\"http:\/\/en.wikipedia.org\/wiki\/Coupling_from_the_past\">Propp-Wilson coupling from the past<\/a>, <a href=\"http:\/\/en.wikipedia.org\/wiki\/Simulated_annealing\">simulated annealing<\/a><\/li>\n<\/ul>\n<ul>\n<li><a href=\"http:\/\/en.wikipedia.org\/wiki\/Monte_Carlo_method\">Monte-Carlo methods<\/a><\/li>\n<li><a href=\"http:\/\/en.wikipedia.org\/wiki\/Dynamic_programming\">Dynamic programing paradigm<\/a><\/li>\n<li><a href=\"http:\/\/en.wikipedia.org\/wiki\/Genetic_algorithm\">Genetic algorithms paradigm<\/a><\/li>\n<li><a href=\"http:\/\/en.wikipedia.org\/wiki\/Branch_and_bound\">Branch and bound paradigm<\/a><\/li>\n<li><a href=\"http:\/\/en.wikipedia.org\/wiki\/Greedy_algorithm\">Greedy algorithms paradigm<\/a><\/li>\n<li><a href=\"http:\/\/en.wikipedia.org\/wiki\/Divide_and_conquer_algorithm\">Divide and conquer paradigm<\/a><\/li>\n<\/ul>\n<p style=\"text-align: justify;\">Ironically, the most used algorithms (if we measure say in <a href=\"http:\/\/en.wikipedia.org\/wiki\/Watt\">Megawatt<\/a>) concern coding, compression, cryptography, linked with what is often identified as \"pure mathematics\" (finite fields algebra, discrete linear algebra, discrete harmonic analysis). This does not mean that numerical algorithms, identified as \"applied mathematics\", are not used!  To me, what matters is the depth and beauty of concepts and the efficiency and versatility of implementations.<\/p>\n<ul>\n<li>Iterative and non-iterative<\/li>\n<li>Exact and approximate<\/li>\n<li>Stochastic and deterministic<\/li>\n<li>Integer and numerical<\/li>\n<li>Euclid and Archimedes<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>The success of computers is largely due to the existence of efficient algorithms for solving numerical and combinatorial problems. These algorithms are used billion of&#8230;<\/p>\n<div class=\"more-link-wrapper\"><a class=\"more-link\" href=\"https:\/\/djalil.chafai.net\/blog\/2012\/04\/08\/algorithms\/\">Continue reading<span class=\"screen-reader-text\">Algorithms<\/span><\/a><\/div>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"iawp_total_views":60},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/4669"}],"collection":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/comments?post=4669"}],"version-history":[{"count":90,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/4669\/revisions"}],"predecessor-version":[{"id":4700,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/4669\/revisions\/4700"}],"wp:attachment":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/media?parent=4669"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/categories?post=4669"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/tags?post=4669"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}