Algoritma inti dikerahkan

Untuk menunjukkan pentingnya algoritma (misalnya untuk mahasiswa dan profesor yang tidak melakukan teori atau bahkan dari bidang yang sama sekali berbeda) kadang-kadang berguna untuk siap memberikan daftar contoh di mana algoritma inti telah digunakan dalam komersial, pemerintahan, atau perangkat lunak / perangkat keras yang banyak digunakan.

Saya mencari contoh seperti itu yang memenuhi kriteria berikut:

1. Perangkat lunak / perangkat keras yang menggunakan algoritma harus digunakan secara luas sekarang.

2. Contohnya harus spesifik. Tolong beri referensi ke sistem tertentu dan algoritma tertentu.
   Misalnya, dalam "algoritma X berguna untuk pemrosesan gambar" istilah "pemrosesan gambar" tidak cukup spesifik; dalam "pencarian Google menggunakan algoritma grafik" istilah "algoritma grafik" tidak cukup spesifik.

3. Algoritme harus diajarkan dalam sarjana atau Ph.D. kelas dalam algoritma atau struktur data. Idealnya, algoritme tersebut dicakup dalam buku teks algoritme tipikal. Misalnya, "sistem X yang terkenal menggunakan sedikit algoritma Y" tidak baik.

Memperbarui:

Sekali lagi terima kasih atas jawaban dan tautannya! Beberapa orang berkomentar bahwa sulit untuk memenuhi kriteria karena algoritma inti begitu luas sehingga sulit untuk menunjuk ke penggunaan tertentu. Saya melihat kesulitannya. Tetapi saya pikir perlu untuk memberikan contoh spesifik karena dalam pengalaman saya mengatakan kepada orang-orang: "Lihat, algoritma itu penting karena mereka ada di mana-mana !" tidak bekerja.

Algoritma yang merupakan pendorong utama di balik suatu sistem, menurut pendapat saya, lebih mudah ditemukan dalam mata pelajaran non-algoritma karena alasan yang sama bahwa teorema dengan aplikasi langsung lebih mudah ditemukan dalam matematika terapan daripada mata pelajaran matematika murni. Jarang untuk masalah praktis untuk memiliki struktur yang tepat dari masalah abstrak dalam kuliah. Untuk menjadi argumentatif, saya tidak melihat alasan mengapa materi kursus algoritma yang modis seperti perkalian Strassen, uji primitif AKS, atau algoritma Moser-Tardos relevan untuk masalah praktis tingkat rendah dalam mengimplementasikan basis data video, kompilator pengoptimal, sistem operasi , sistem kontrol kemacetan jaringan atau sistem lainnya. Nilai dari kursus ini adalah belajar bahwa ada cara rumit untuk mengeksploitasi struktur masalah untuk menemukan solusi yang efisien. Algoritma lanjutan juga merupakan tempat seseorang bertemu dengan algoritma sederhana yang analisisnya non-sepele. Untuk alasan ini, saya tidak akan mengabaikan algoritma acak sederhana atau PageRank.

Saya pikir Anda dapat memilih perangkat lunak besar dan menemukan algoritma dasar dan lanjutan diimplementasikan di dalamnya. Sebagai studi kasus, saya telah melakukan ini untuk kernel Linux, dan menunjukkan beberapa contoh dari Chromium.

Struktur dan Algoritma Data Dasar dalam kernel Linux

Tautan ke kode sumber di github .

1. Daftar tertaut , daftar tertaut ganda , daftar tertaut bebas kunci .

2. B + Pohon dengan komentar yang memberi tahu Anda apa yang tidak dapat Anda temukan di buku teks.

   Implementasi B + Tree yang relatif sederhana. Saya telah menulisnya sebagai latihan pembelajaran untuk memahami bagaimana B + Trees bekerja. Ternyata bermanfaat juga.

   ...

   Trik digunakan yang tidak umum ditemukan di buku pelajaran. Nilai-nilai terendah adalah ke kanan, bukan ke kiri. Semua slot yang digunakan dalam sebuah node berada di sebelah kiri, semua slot yang tidak digunakan berisi nilai NUL. Sebagian besar operasi hanya loop sekali atas semua slot dan berakhir pada NUL pertama.

3. Daftar prioritas yang diurutkan digunakan untuk mutex , driver , dll.

4. Pohon merah-hitam yang digunakan untuk penjadwalan, manajemen memori virtual, untuk melacak deskriptor file dan entri direktori, dll.
5. Pohon interval

6. Pohon Radix , digunakan untuk manajemen memori , pencarian terkait NFS dan fungsionalitas terkait jaringan.

   Penggunaan umum dari pohon radix adalah untuk menyimpan pointer ke halaman struct;

7. Tumpukan prioritas , yang secara harfiah, implementasi buku teks, digunakan dalam sistem kelompok kontrol .

   Tumpukan prioritas ukuran statis hanya penyisipan sederhana yang berisi pointer, berdasarkan CLR, bab 7

8. Fungsi hash , dengan referensi ke Knuth dan kertas.

   Knuth merekomendasikan bilangan prima dalam rasio sekitar emas dengan bilangan bulat maksimum yang diwakili oleh kata mesin untuk hashing multiplikatif. Chuck Lever memverifikasi keefektifan teknik ini:

   http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf

   Bilangan prima ini dipilih sebagai bit-sparse, yaitu operasi pada mereka dapat menggunakan shift dan penambahan alih-alih multiplikasi untuk mesin di mana multiplikasi lambat.

9. Beberapa bagian kode, seperti driver ini , mengimplementasikan fungsi hash mereka sendiri.

   fungsi hash menggunakan algoritma Rotating Hash

   Knuth, D. Seni Pemrograman Komputer, Volume 3: Penyortiran dan Pencarian, Bab 6.4. Addison Wesley, 1973

10. Tabel hash digunakan untuk mengimplementasikan inode , pemeriksaan integritas sistem file , dll.

11. Array bit , yang digunakan untuk menangani flag, interupsi, dll. Dan ditampilkan dalam Knuth Vol. 4.

12. Semafor dan kunci pintal

13. Pencarian biner digunakan untuk penanganan interupsi , register pencarian cache , dll.

14. Pencarian biner dengan B-tree

15. Kedalaman pencarian pertama dan varian yang digunakan dalam konfigurasi direktori .

    Melakukan gerakan kedalaman-pertama yang dimodifikasi dari pohon namespace, mulai (dan berakhir) pada node yang ditentukan oleh start_handle. Fungsi panggilan balik dipanggil setiap kali sebuah simpul yang cocok dengan parameter tipe ditemukan. Jika fungsi panggilan balik mengembalikan nilai bukan nol, pencarian dihentikan segera dan nilai ini dikembalikan ke pemanggil.

16. Luasnya pencarian pertama digunakan untuk memeriksa kebenaran penguncian saat runtime.

17. Gabungkan sortir pada daftar tertaut digunakan untuk pengumpulan sampah , manajemen sistem file , dll.

18. Bubble sort juga diterapkan di perpustakaan driver.

19. Pencocokan string Knuth-Morris-Pratt ,

    Menerapkan algoritma pencocokan string waktu-linear karena Knuth, Morris, dan Pratt [1]. Algoritma mereka menghindari perhitungan eksplisit fungsi transisi DELTA sama sekali. Waktu pencocokannya adalah O (n), untuk n menjadi panjang (teks), hanya menggunakan fungsi bantu PI [1..m], untuk m menjadi panjang (pola), yang dihitung dari pola dalam waktu O (m). Array PI memungkinkan fungsi transisi DELTA dihitung secara efisien "on the fly" sesuai kebutuhan. Secara kasar, untuk setiap keadaan "q" = 0,1, ..., m dan karakter apa saja "a" dalam SIGMA, nilai PI ["q"] berisi informasi yang tidak bergantung pada "a" dan diperlukan untuk hitung DELTA ("q", "a") 2. Karena array PI hanya memiliki entri m, sedangkan DELTA memiliki entri O (m | SIGMA |), kami menyimpan faktor | SIGMA | dalam waktu preprocessing dengan menghitung PI daripada DELTA.

    [1] Cormen, Leiserson, Rivest, Stein Introdcution to Algorithms, 2nd Edition, MIT Press

    [2] Lihat teori otomatisasi terbatas

20. Pola Boyer-Moore cocok dengan referensi dan rekomendasi kapan memilih alternatif.

    Menerapkan algoritma pencocokan string Boyer-Moore:

    [1] Algoritma Pencarian String Cepat, RS Boyer dan Moore. Komunikasi dari Asosiasi untuk Mesin Komputer, 20 (10), 1977, hlm. 762-772. http://www.cs.utexas.edu/users/moore/publications/fstrpos.pdf

    [2] Buku Pegangan Algoritma Pencocokan String Tepat, Thierry Lecroq, 2004 http://www-igm.univ-mlv.fr/~lecroq/string/string.pdf

    Catatan: Karena Boyer-Moore (BM) melakukan pencarian untuk pencocokan dari kanan ke kiri, masih mungkin bahwa pencocokan dapat tersebar di beberapa blok, dalam hal ini algoritma ini tidak akan menemukan kebetulan.

    Jika Anda ingin memastikan hal seperti itu tidak akan terjadi, gunakan implementasi Knuth-Pratt-Morris (KMP). Kesimpulannya, pilih algoritma pencarian string yang tepat tergantung pada pengaturan Anda.

    Katakanlah Anda menggunakan infrastruktur pencarian teks untuk memfilter, NIDS atau
    tujuan terfokus keamanan serupa, lalu buka KMP. Jika tidak, jika Anda benar-benar peduli dengan kinerja, katakanlah Anda mengklasifikasikan paket untuk menerapkan kebijakan Quality of Service (QoS), dan Anda tidak keberatan tentang kemungkinan pencocokan yang tersebar di beberapa fragmen, lalu buka BM.

Struktur dan Algoritma Data di Browser Web Chromium

Tautan ke kode sumber pada kode Google . Saya hanya akan daftar beberapa. Saya sarankan menggunakan fitur pencarian untuk mencari algoritma favorit Anda atau struktur data.

1. Melebarkan pohon .

   Pohon ini juga diparameterisasi oleh kebijakan alokasi (Allocator). Kebijakan ini digunakan untuk mengalokasikan daftar di toko bebas C atau zona; lihat zone.h.

2. Diagram Voronoi digunakan dalam demo.
3. Tabbing berdasarkan algoritma Bresenham .

1. Pohon biner
2. Pohon merah-hitam

   Kesimpulan dari Julian Walker

   Pohon merah-hitam adalah binatang buas yang menarik. Mereka diyakini lebih sederhana daripada pohon AVL (pesaing langsung mereka), dan pada pandangan pertama ini tampaknya menjadi masalah karena penyisipan sangat mudah. Namun, ketika seseorang mulai bermain dengan algoritma penghapusan, pohon merah-hitam menjadi sangat rumit. Namun, penyeimbang kompleksitas tambahan ini adalah bahwa penyisipan dan penghapusan dapat diimplementasikan dengan menggunakan algoritma single-pass, top-down. Seperti halnya dengan pohon AVL, di mana hanya algoritma penyisipan yang dapat ditulis dari atas ke bawah. Penghapusan dari pohon AVL membutuhkan algoritma bottom-up.

   ...

   Pohon merah-hitam populer, karena sebagian besar struktur data dengan nama aneh. Misalnya, di Jawa dan C ++, struktur peta perpustakaan biasanya diimplementasikan dengan pohon merah-hitam. Pohon merah-hitam juga sebanding dalam kecepatannya dengan pohon AVL. Meskipun keseimbangannya tidak terlalu baik, pekerjaan yang diperlukan untuk menjaga keseimbangan biasanya lebih baik di pohon merah-hitam. Ada beberapa kesalahpahaman yang beredar, tetapi sebagian besar hype tentang pohon merah-hitam itu akurat.

3. Pohon AVL
4. Pencocokan string Rabin-Karp digunakan untuk kompresi.
5. Hitung akhiran otomat .
6. Filter Bloom diimplementasikan oleh Apple Inc.
7. Algoritma Bresenham .

Pemrograman Perpustakaan Bahasa

Saya pikir mereka layak dipertimbangkan. Perancang bahasa pemrograman menganggap sepadan dengan waktu dan upaya beberapa insinyur untuk mengimplementasikan struktur data dan algoritma ini sehingga yang lain tidak perlu melakukannya. Keberadaan perpustakaan adalah bagian dari alasan kita dapat menemukan struktur data dasar diimplementasikan kembali dalam perangkat lunak yang ditulis dalam C tetapi kurang begitu untuk aplikasi Java.

1. The C ++ STL termasuk daftar, tumpukan, antrian, peta, vektor, dan algoritma untuk menyortir, mencari dan manipulasi tumpukan .
2. API Java sangat luas dan mencakup lebih banyak.
3. The Meningkatkan C ++ library termasuk algoritma seperti Boyer-Moore dan algoritma string matching Knuth-Morris-Pratt.

Alokasi dan Algoritma Penjadwalan

Saya menemukan ini menarik karena meskipun mereka disebut heuristik, kebijakan yang Anda gunakan menentukan jenis algoritma dan struktur data yang diperlukan, jadi orang perlu tahu tentang tumpukan dan antrian.

1. Paling Baru Digunakan dapat diimplementasikan dalam berbagai cara. Sebuah implementasi berbasis daftar di kernel Linux.
2. Kemungkinan lain adalah First In First Out, Least Frequently Used, dan Round Robin.
3. Varian FIFO digunakan oleh sistem VAX / VMS.
4. Algoritme Clock oleh Richard Carr digunakan untuk penggantian bingkai halaman di Linux.
5. Prosesor Intel i860 menggunakan kebijakan penggantian acak.
6. Cache Penggantian Adaptif digunakan di beberapa pengontrol penyimpanan IBM, dan digunakan di PostgreSQL meskipun hanya sebentar karena masalah paten .
7. The Buddy algoritma alokasi memori , yang dibahas oleh Knuth di TAOCP Vol. 1 digunakan di kernel Linux, dan pengalokasi bersamaan jemalloc digunakan oleh FreeBSD dan di facebook .

Utilitas inti dalam sistem * nix

1. grep dan awk keduanya mengimplementasikan konstruksi NFA Thompson-McNaughton-Yamada dari ekspresi reguler, yang tampaknya bahkan mengalahkan implementasi Perl .
2. tsort mengimplementasikan jenis topologi.
3. fgrep mengimplementasikan algoritma pencocokan string Aho-Corasick.
4. GNU grep , mengimplementasikan algoritma Boyer-Moore menurut penulis Mike Haertel.
5. crypt (1) di Unix mengimplementasikan varian dari algoritma enkripsi di mesin Enigma.
6. Unix diff diimplementasikan oleh Doug McIllroy, berdasarkan prototipe yang ditulis bersama James Hunt, berkinerja lebih baik daripada algoritma pemrograman dinamis standar yang digunakan untuk menghitung jarak Levenshtein. Versi Linux menghitung jarak edit terpendek.

Algoritma Kriptografi

Ini bisa menjadi daftar yang sangat panjang. Algoritma kriptografi diimplementasikan dalam semua perangkat lunak yang dapat melakukan komunikasi atau transaksi aman.

1. Pohon merkle , khususnya varian Tiger Tree Hash, digunakan dalam aplikasi peer-to-peer seperti GTK Gnutella dan LimeWire .
2. MD5 digunakan untuk menyediakan checksum untuk paket perangkat lunak dan digunakan untuk pemeriksaan integritas pada sistem * nix ( implementasi Linux ) dan juga didukung pada Windows dan OS X.
3. OpenSSL mengimplementasikan banyak algoritma kriptografi termasuk AES, Blowfish, DES, SHA-1, SHA-2, RSA, DES, dll.

Kompiler

1. Parsing LALR diimplementasikan oleh yacc dan bison.
2. Algoritma Dominator digunakan dalam kebanyakan kompiler yang mengoptimalkan berdasarkan formulir SSA.
3. lex dan flex kompilasi ekspresi reguler ke NFA.

Kompresi dan Pemrosesan Gambar

1. Algoritma Lempel-Ziv untuk format gambar GIF diimplementasikan dalam program manipulasi gambar, mulai dari utilitas * nix convert hingga program yang kompleks.
2. Pengodean run length digunakan untuk menghasilkan file PCX (digunakan oleh program Paintbrush asli), file BMP terkompresi, dan file TIFF.
3. Kompresi wavelet adalah dasar untuk JPEG 2000 sehingga semua kamera digital yang menghasilkan file JPEG 2000 akan mengimplementasikan algoritma ini.
4. Koreksi kesalahan Reed-Solomon diimplementasikan di kernel Linux , drive CD, pembaca barcode dan dikombinasikan dengan konvolusi untuk transmisi gambar dari Voyager.

Pembelajaran Klausul Berbasis Konflik

Sejak tahun 2000, waktu berjalan pemecah SAT pada tolok ukur industri (biasanya dari industri perangkat keras, meskipun sumber lain juga digunakan) telah menurun hampir secara eksponensial setiap tahun. Bagian yang sangat penting dari pengembangan ini adalah algoritma Pembelajaran Konflik yang Didorong yang menggabungkan algoritma Boolean Constraint Propagation dalam makalah asli Davis Logemann dan Loveland dengan teknik pembelajaran klausa yang berasal dari pemrograman kendala dan penelitian kecerdasan buatan. Untuk pemodelan industri yang spesifik, SAT dianggap masalah mudah ( lihat diskusi ini). Bagi saya, ini adalah salah satu kisah sukses terbesar dalam beberapa waktu terakhir karena menggabungkan kemajuan algoritmik yang tersebar selama beberapa tahun, ide-ide teknik yang cerdas, evaluasi eksperimental, dan upaya bersama untuk menyelesaikan masalah. The CACM artikel oleh Malik dan Zhang adalah membaca yang baik. Algoritma ini diajarkan di banyak universitas (saya telah menghadiri empat di mana itu terjadi) tetapi biasanya dalam kelas logika atau metode formal.

Aplikasi pemecah SAT banyak. IBM, Intel dan banyak perusahaan lain memiliki implementasi SAT solver mereka sendiri. The manajer paket di OpenSUSE juga menggunakan pemecah SAT.

PageRank adalah salah satu dari algoritma yang paling terkenal. Dikembangkan oleh co-founder Google Larry Page dan co-author, itu membentuk dasar dari mesin pencari asli Google dan secara luas dikreditkan dengan membantu mereka untuk mencapai hasil pencarian yang lebih baik daripada pesaing mereka pada saat itu.

Kami membayangkan "surfer acak" mulai dari beberapa halaman web, dan berulang kali mengklik tautan acak untuk membawanya ke halaman baru. Pertanyaannya adalah, "Berapa lama waktu yang akan dihabiskan oleh surfer di setiap halaman?" Semakin banyak waktu yang dihabiskan oleh surfer di suatu halaman, semakin penting halaman tersebut dipertimbangkan.

Secara lebih formal, kami melihat internet sebagai grafik di mana halaman adalah simpul dan tautan diarahkan ke tepian. Kami kemudian dapat model tindakan surfer sebagai acak berjalan pada grafik atau ekuivalen sebagai Rantai Markov dengan matriks transisi . Setelah berurusan dengan beberapa masalah untuk memastikan bahwa Rantai Markov ergodik (ke mana surfer pergi jika suatu halaman tidak memiliki tautan keluar?), Kami menghitung jumlah waktu yang dihabiskan oleh surfer di setiap halaman sebagai distribusi kondisi mantap dari Rantai Markov. .$M$

Algoritme itu sendiri dalam beberapa hal sepele - kami hanya menghitung untuk besar dan distribusi awal sewenang-wenang . Ini hanya berjumlah perkalian matriks-matriks atau matriks-vektor berulang. Konten algoritma terutama dalam pengaturan (memastikan ergodisitas, membuktikan bahwa Rantai Markov yang ergodik memiliki distribusi kondisi tunak yang unik) dan analisis konvergensi (ketergantungan pada celah spektral ). k π 0$M^k \pi_0$$k$$\pi_0$$M$

Saya akan menyebutkan CPLEX perangkat lunak yang banyak digunakan (atau serupa) implementasi metode / algoritma Simplex untuk memecahkan masalah pemrograman linier. Ini adalah algoritma (?) Yang paling banyak digunakan dalam riset ekonomi dan operasi.

"Jika seseorang mengambil statistik tentang masalah matematika mana yang menghabiskan sebagian besar waktu komputer di dunia, maka (tidak termasuk database yang menangani masalah seperti penyortiran dan pencarian) jawabannya mungkin adalah pemrograman linier. " (L. Lovász, A new algoritma pemrograman linier - lebih baik atau lebih buruk daripada metode simpleks? Matematika. Intelijen 2 (3) (1979/80) 141-146.)

Algoritma Simplex juga memiliki pengaruh besar dalam teori; lihat, misalnya, dugaan Hirsch (Polinomial) .

Saya kira sarjana atau Ph.D. kelas dalam penawaran algoritma dengan algoritma Simplex (termasuk algoritma dasar dari aljabar linier seperti Metode Eliminasi Gauss).

(Algoritma sukses lainnya, termasuk Quicksort untuk menyortir, tercantum dalam Algoritma dari Buku .)

Seperti yang saya pahami, Program Pencocokan Penduduk Nasional untuk waktu yang lama hanyalah aplikasi langsung dari algoritma Gale-Shapley untuk masalah pernikahan yang stabil. Sejak itu telah sedikit diperbarui untuk menangani beberapa detail tambahan seperti tugas pasangan (alias "masalah dua tubuh"), dll ...

Jika Anda juga termasuk hal-hal tingkat PhD, banyak (kebanyakan?) Program CS lulusan memasukkan beberapa kursus dalam teori pengkodean. Jika Anda memiliki kursus dalam teori pengkodean, Anda pasti akan membahas kode Reed-Solomon yang merupakan bagian integral dari cara kerja compact disc dan pengkodean Huffman yang digunakan dalam format file JPEG, MP3, dan ZIP. Bergantung pada orientasi kursus, Anda juga dapat membahas Lempel-Ziv yang digunakan dalam format GIF. Secara pribadi, saya mendapat Lempel-Ziv dalam kursus algoritma sarjana, tapi saya pikir itu mungkin tidak biasa.

GNU grep adalah alat baris perintah untuk mencari satu atau lebih file input untuk baris yang berisi kecocokan dengan pola tertentu. Sudah diketahui bahwa grep sangat cepat! Berikut ini kutipan dari pengarangnya Mike Haertel (diambil dari sini ):

GNU grep uses the well-known Boyer-Moore algorithm, which looks first for the
final letter of the target string, and uses a lookup table to tell it how far
ahead it can skip in the input whenever it finds a non-matching character.

Secara lebih umum, hadiah Kanellakis diberikan oleh ACM untuk penemuan teoretis yang tepat yang berdampak besar dalam praktik.

penghargaan 2012 adalah untuk hashing yang sensitif terhadap lokalitas , yang telah menjadi metode masuk untuk pengurangan dimensi dalam penambangan data untuk masalah tetangga dekat (dan relatif mudah untuk diajarkan - setidaknya algoritma itu sendiri)

$\varepsilon$

Beberapa contoh penggunaan industri dari struktur data ini adalah:

• Sistem Sawzall Google untuk analisis data yang tidak terstruktur menggunakan Count Sketch untuk mengimplementasikan fungsi 'item paling populer'
• Sistem "stream database" Gigassope AT&T untuk pemantauan lalu lintas jaringan mengimplementasikan sketsa CountMin.
• Sistem Monitoring Berkelanjutan (CMON) Sprint mengimplementasikan CountMin.

Berikut ini juga situs yang mengumpulkan informasi tentang aplikasi CountMin.

Sejauh mengajar, saya tahu bahwa teknik membuat sketsa dasar diajarkan di Princeton dalam program matematika sarjana sarjana. Saya diajari sketsa CountMin dalam kursus algoritma pertama saya. Bagaimanapun, analisis CountMin lebih sederhana daripada analisis untuk hampir semua algoritma acak lainnya: ini adalah aplikasi langsung dari independensi berpasangan dan ketidaksetaraan Markov. Jika ini bukan bahan standar dalam sebagian besar kursus algoritma, saya pikir ini karena alasan historis.

Dalam dekade terakhir, algoritma telah digunakan untuk meningkatkan jumlah (dan kualitas, saya kira?) Transplantasi ginjal melalui berbagai program pencocokan donor ginjal. Saya mengalami kesulitan menemukan berita terbaru tentang ini, tetapi di sini setidaknya ada beberapa petunjuk:

• Baru-baru ini 2007 Alliance for Paired Donation menggunakan algoritma Abraham, Blum, dan Sandholm . Mereka mungkin masih menggunakannya, tetapi saya tidak bisa mengetahuinya dengan mencari online. Meskipun algoritma ini hampir pasti tidak tercakup dalam kursus "standar", itu menggabungkan beberapa ide mendasar yang pasti diajarkan dalam kursus tersebut untuk memberikan algoritma yang cukup baik untuk masalah yang, secara umum, NP-complete (varian dari Cycle Cover ).

• National Kidney Registry juga menggunakan beberapa algoritma standar, termasuk (pada satu titik) CPLEX. Hal ini menyebabkan rantai transplantasi yang benar-benar dilakukan yang menghubungkan 60 orang .

Ini adalah salah satu contoh favorit saya bukan hanya keberhasilan algoritma, tetapi juga pentingnya mempelajari algoritma untuk masalah NP-complete. Mereka benar - benar dapat menyelamatkan hidup , dan telah melakukannya!

Algoritma Viterbi, yang masih banyak digunakan dalam pengenalan suara dan beberapa aplikasi lain: http://en.wikipedia.org/wiki/Viterbi_algorithm Algoritme itu sendiri adalah pemrograman dinamis dasar.

Dari Wikipedia: "Algoritme Viterbi diusulkan oleh Andrew Viterbi pada tahun 1967 sebagai algoritma penguraian kode konvolusional melalui tautan komunikasi digital yang bising. [1] Algoritma ini telah menemukan aplikasi universal dalam mendekode kode konvolusional yang digunakan dalam seluler digital CDMA dan GSM, modem dial-up, satelit, komunikasi dalam-ruang, dan LAN nirkabel 802.11. Sekarang juga umum digunakan dalam pengenalan suara, sintesis ucapan, bercak kata kunci, linguistik komputasi, dan bioinformatika. Misalnya, dalam ucapan-ke-teks (ucapan pengakuan), sinyal akustik diperlakukan sebagai urutan peristiwa yang diamati, dan string teks dianggap sebagai "penyebab tersembunyi" dari sinyal akustik. Algoritma Viterbi menemukan string teks yang paling mungkin diberikan sinyal akustik. "

1. A * digunakan di banyak Perangkat Navigasi Pribadi (alias unit GPS)
2. A * didefinisikan dengan sangat baik, dan telah dilaksanakan dengan cukup mudah.
3. A * tidak sepenuhnya sepele, tetapi tidak mengambil gelar Ph.D. untuk memahaminya.

Lihat proyek Jens Vygen, BonnTools for Chip Design. http://www.or.uni-bonn.de/~vygen/projects.html Saya telah mendengar beberapa pembicaraan tentang ini dan juga melihat beberapa makalah mereka. Mereka menggunakan pembulatan acak gaya Raghavan-Thompson serta metode pembaruan berat multiplikatif untuk memecahkan piringan hitam aliran multikommoditas berskala besar. Namun, seperti proyek besar lainnya, mereka perlu melakukan beberapa rekayasa juga tetapi metodologinya sangat banyak didasarkan pada algoritma yang terkenal.

Lucu bahwa saya melihat pertanyaan ini hari ini dan kemudian secara kebetulan mengklik tautan ini pada banyak penggunaan Transformasi Fourier .

Saya agak terkejut bahwa dengan semua algoritma mewah di atas, tidak ada yang menyebutkan keluarga terhormat algoritma kompresi Lempel-Ziv (ditemukan pada 1977/78).

1. Itu digunakan di mana-mana - teks ke gambar untuk memproses aliran. Sangat mungkin bahwa LZ * adalah keluarga algoritma tunggal yang paling banyak digunakan.
2. Kompresi kamus merupakan terobosan besar dalam teori kompresi dan sangat berbeda dari pendekatan gaya Shannon-Fano.
3. Algoritma dalam keluarga agak mudah dan mudah dipahami.

Memperbarui

Rupanya sudah disebutkan secara singkat.

singular value decomposition (SVD) memiliki hubungan yang kuat dengan analisis faktor statistik atau analisis komponen utama dan dapat dipahami dalam aljabar linier sarjana atau kelas statistik, dan memiliki banyak sifat teoritis yang penting. itu juga berperan dalam algoritma kompresi gambar. itu memainkan elemen kunci dalam entri yang menang dalam kontes hadiah Netflix $ 1M (salah satu kompetisi pengumpulan data terbesar di dunia dalam sejarah) dan sekarang diterapkan di situs mereka untuk memprediksi peringkat pengguna. itu juga diketahui sangat terkait dengan jaringan saraf swadaya yang mengatur diri sendiri yang berasal dari teori biologis.

ada beberapa koneksi juga ke gradient descent yang digunakan secara luas dalam pembelajaran mesin & jaringan syaraf tiruan dan sebagai teknik optimisasi yang diterapkan secara universal yang mana metode Newton adalah bentuk 2d dasar. ada algoritma gradient-descent untuk mendapatkan SVD.

Menemukan jalur Euler adalah dasar dari perakitan genom - tugas yang biasa dilakukan ketika bekerja dengan genom penuh (dalam bioinformatika, kedokteran, forensik, ekologi).

PEMBARUAN Lupa yang jelas ini: UPS, FedEx, USPS semua harus menyelesaikan masalah besar Traveling Salesman Problem setiap malam. Menghemat banyak waktu dan uang bagi mereka untuk mengirim driver pada rute yang optimal.

UPDATE2 Masalah set simpul umpan balik minimum digunakan untuk resolusi kebuntuan di banyak OS.

Saya suka sistem ini untuk menyelamatkan jumlah maksimum nyawa di Inggris dengan transplantasi ginjal, berdasarkan algoritma pencocokan maksimum: Donasi Ginjal Altruistik dan Berpasangan . Mereka mencocokkan orang-orang yang membutuhkan ginjal yang memiliki teman / saudara yang tidak cocok yang mau menyumbang, dengan orang lain dalam situasi yang sama, secara maksimal. Kemudian pada hari donasi, semua donatur menyumbang pada waktu yang bersamaan, diikuti dengan pengiriman cepat ginjal ke seluruh negara ke penerima.

buku yang relatif baru ini layak dipertimbangkan sebagai jawaban lengkap / terperinci untuk pertanyaan dalam bentuk yang mudah digunakan, diperluas / dikumpulkan dan yang dapat digunakan sebagai bahan pelengkap untuk kelas algoritma. [beberapa di antaranya telah disebutkan; tumpang tindih yang kuat itu sendiri terkenal.]

• Sembilan Algoritma yang Mengubah Masa Depan: Ide-Ide Cerdas yang Menggerakkan Komputer Saat Ini oleh MacCormick

  • pengindeksan mesin pencari
  • Peringkat halaman
  • kriptografi kunci publik
  • kode koreksi kesalahan
  • pengenalan pola
  • kompresi data
  • basis data
  • tanda tangan digital
  • teori komputabilitas

• referensi lain yang agak mirip tetapi lebih teoretis, The Best of the 20th Century: Nama Editor Top 10 Algoritma Cipra / SIAM.

  • Metode Monte Carlo
  • algoritma simpleks
  • Iterasi ruang bagian Krylov
  • perhitungan matriks dekomposisi
  • Kompiler Fortran
  • Algoritma matriks QR
  • quicksort
  • FFT
  • deteksi hubungan integer
  • algoritma multipole cepat

The Knuth-Morris-Pratt string pencarian secara luas digunakan, spesifik, dan mengajar di undergrad / lulusan CS.

Memikirkan algoritma yang sangat mendasar

1. Generator angka acak ditemukan di mana-mana dan khususnya di semua game.
2. Database terdiri dari banyak algoritma, termasuk B +, Hash, antrian prioritas, ekspresi reguler, criptography, sorting, dll ... Seorang teman saya mengatakan SGBD berada di puncak rantai makanan komputasi.
3. Sortir digunakan di mana-mana, misalnya di Excel. Ini sebenarnya digunakan sepanjang waktu dalam kehidupan nyata, tetapi biasanya manusia menggunakan algoritma ad-hoc
4. Bit paritas digunakan di sekitar
5. Pengodean Huffman ada dalam perangkat lunak kompresi dan transmisi
6. Tumpukan (LIFO) digunakan di mana-mana. Di dalam bahasa pemrograman, di CPU, dll ...

Senang menunjukkan mereka muncul dalam kehidupan nyata:

A. Banyak kelompok menggunakan semacam algoritma pohon penutup untuk berkomunikasi, dengan membagi daftar telepon dengan cara hierarkis di antara orang-orang B. Mobil di persimpangan biasanya menggunakan algoritma round-robin (dengan cara sukarela) C. Sebagian besar tempat, seperti bank dan rumah sakit, mengatur klien mereka dalam algoritma FIFO

Masalah algoritmik yang menarik muncul dalam aplikasi medis CT scan. Dalam Computed Tomography (CT), tubuh terpapar sinar-X dari berbagai sudut. Di satu ujung pemindai adalah pemancar sinar-X dan di ujung lainnya sensor. Dari serangkaian pemindaian, gambar direkonstruksi untuk diperiksa oleh dokter!

The proyeksi disaring kembali algoritma adalah dasar untuk rekonstruksi gambar dari satu set scan. Algoritma ini sebenarnya merupakan bentuk masalah perkiraan di mana "sinyal" disampel di bawah tingkat Nyquist. Algoritma ini digunakan "di belakang layar" di semua rumah sakit dan proyeksi dasar yang difilter menggunakan matematika sarjana seperti transformasi Fourier untuk mencapai Teorema Slice Fourier .

Contoh dari FFT

Saya pernah membantu port algoritma FFT ke bahasa sistem yang berbeda.

Algoritma ini digunakan untuk menentukan jeda baris dalam pengiriman kabel tv / internet / telepon coaxial. Pada dasarnya teknisi akan meminta sinyal untuk dikirim ke kotak pelanggan, pada saat yang sama mereka akan menampilkan tampilan statistik real-time untuk pelanggan tertentu, seperti QoS, dB, .... Teknisi dapat menggunakan data dan grafik untuk menentukan dalam beberapa kaki antara rumah dan tiang tempat istirahat parsial ada (atau beberapa istirahat seperti yang saya diberitahu).

Seperti yang disebutkan di atas FFT banyak digunakan, tetapi ini adalah salah satu yang lebih mencolok dan jelas (dalam hal mengapa dan bagaimana) yang saya lihat dalam praktek.

Maaf saya harus menjaganya agar tetap tinggi.

Algoritma garis Bresenham adalah algoritma tunggal paling berguna yang pernah saya jumpai. Mudah dimengerti Ive menggunakannya untuk banyak aplikasi dari gambar garis ke spliner kompleks untuk mesin casting 3d hingga renderer poligon yang kompleks, serta untuk animasi yang kompleks dan penggunaan skala.

Perencanaan Rute yang Dapat Disesuaikan (Daniel Delling, Andrew V. Goldberg, Thomas Pajor, dan Renato F. Werneck) http://research.microsoft.com/apps/pubs/default.aspx?id=145688

menggerakkan Bing Maps: http://www.bing.com/blogs/site_blogs/b/maps/archive/2012/01/05/bing-maps-new-routing-engine.aspx

Wikipedia memiliki koleksi algoritma / aplikasi yang layak yang diklasifikasikan kurang lebih dalam daftar . Microsoft menyediakan makalah yang dikutip tetapi tidak ada penjelasan eksplisit tentang bidang ilmu komputer atau aplikasi. Ada juga daftar kronologis dari berbagai konferensi CS _http: //jeffhuang.com/best_paper_awards.html_ dikompilasi oleh Prof. Huang.

Spectral Clustering adalah algoritma pengelompokan yang elegan, yang dikenal sebagai algoritma pemotongan ternormalisasi yang diperkenalkan oleh Jianbo Shi dan Jitendra Malik untuk segmentasi gambar. Ini juga telah dikembangkan dengan baik dalam aplikasi pengelompokan data, menjadi persimpangan yang baik antara kedua komunitas.

dua contoh favorit pribadi lainnya berakar kuat dalam ilmu komputer tetapi mungkin mudah diabaikan oleh para teoretikus abstraksionis, yang telah mengalami kemajuan besar / transformatif dan memiliki dampak praktis / penerapan besar-ke-besar dalam kehidupan sehari-hari selama beberapa dekade terakhir. sudah seluruh generasi tumbuh tanpa mengenal dunia tanpa mereka. pada dasarnya kategori Pemodelan dan simulasi .

• algoritma simulasi fisika . terutama menggunakan hukum Newton tetapi menggunakan hukum lain (seperti dinamika fluida). digunakan dalam berbagai macam aplikasi mulai dari aplikasi teknik, video game, dan terkadang film. ini bertanggung jawab juga untuk secara signifikan meningkatkan keselamatan, efisiensi, atau keandalan misalnya mobil & pesawat terbang melalui desain uji virtual / untuk tekanan simulasi. area penelitian yang sedang berlangsung terkait utama dari bioinformatika dengan implikasi besar dalam biologi misalnya desain obat, pencegahan penyakit dll: protein lipat / prediksi struktur . Juga perhatikan tahun ini Hadiah Nobel Kimia diberikan untuk simulasi kimia untuk Karplus, Levitt, Warshel. Algoritma simulasi fisika sangat terlibat dalam keamanan / pengujian senjata nuklir misalnya di laboratorium Los Alamos.

• algoritma raytracing / CGI . ini dimulai sebagai topik penelitian hanya beberapa dekade yang lalu [seorang teman mendapatkan gelar master dalam algoritma penulisan CS raytracing] tetapi menjadi sangat diterapkan dalam misalnya permainan dan bisnis pembuatan film, mencapai tingkat kewaspadaan luar biasa yang bertanggung jawab untuk sejumlah besar efek khusus dalam film. industri-industri ini secara harfiah telah menginvestasikan miliaran dolar dan menggunakan algoritma ini dan seluruh perusahaan besar didasarkan pada pemanfaatannya, misalnya Pixar . sebagian besar awalnya digunakan dalam film scifi misalnya, teknik ini sekarang sangat luas dan secara rutin digunakan bahkan dalam film "khas". misalnya baru - baru ini The Great Gatsby sangat bergantung pada efek CGI untuk menggambar lingkungan yang meyakinkan atau bergaya, memperbaiki film / karakter, dll.

Rosetta Code mencantumkan algoritma yang diterapkan oleh Programming Task (692) dan oleh Programming Language (518) dengan Semantic MediaWiki.

mungkin semua algoritma utama / pilihan yang diminati oleh audiens ini telah disebutkan pada titik ini. Namun, beberapa lagi pantas disebutkan untuk kelengkapan. & beberapa analisis tentang apa yang dianggap sebagai algoritma signifikan relevan di sini.

di bidang CS & IT tampaknya ada fenomena yang sudah lama diperhatikan di AI yang disebut "memindahkan tiang gawang" . ini adalah fenomena psikologis di mana bidang maju relatif cepat tetapi orang dengan cepat secara mental menyesuaikan diri dengan "normal baru" dan mengambil kemajuan nyata atau bahkan terobosan sebagai hal biasa atau tidak biasa dalam retrospeksi, setelah dilakukan, yaitu diremehkan atau diminimalkan. ini sangat ditangkap dalam pertanyaan ini dengan cara algoritma bergerak dari R&D ke "penyebaran". mengutip penulis pertanyaan di komentar selanjutnya:

Bahkan, sebagian kecil dari semua kode yang ditulis adalah mengimplementasikan sesuatu yang menarik dari sudut pandang algoritmik.

tapi ini bermasalah dan pada dasarnya merupakan definisi ulang TCS-sentris dari kata "algoritma". agaknya algoritma yang menarik adalah canggih. apakah itu berarti bahwa jika suatu masalah direduksi menjadi suatu algoritma tingkat lanjut, itu tidak lagi "menarik"? dan "maju" jelas merupakan target yang bergerak. jadi ada cara untuk mendefinisikan "algoritma" secara sempit , atau luas . tampaknya definisi TCS berubah pada konteks, tetapi perhatikan bahkan dalam TCS, ada kecenderungan ke arah definisi luas misalnya dalam apa yang disebut "lensa algoritmik" .

kadang-kadang algoritma yang paling sering ditemukan juga paling diabaikan! internet dan WWW adalah lingkungan / ekologi dekat yang besar untuk algoritma. masih relatif muda pada usia hanya sekitar 2 dekade (ditemukan ~ 1991) telah tumbuh secara besar-besaran dan secara eksponensial dalam waktu singkat. Pertumbuhan situs WWW bahkan mungkin melebihi hukum Moores eksponensial yang terkenal.

internet / WWW didukung oleh banyak algoritma canggih. internet memiliki algoritma perutean yang rumit yang dibangun ke dalam router (sekali lagi menyalakan korporasi multi-miliar dolar seperti Cisco). beberapa teori lanjut berlaku di sana misalnya dalam algoritma routing . Algoritma ini adalah subjek penelitian yang berkembang, maju / mutakhir beberapa dekade yang lalu, namun kini sangat finetuned & dipahami dengan baik sehingga agak tidak terlihat.

kita tidak boleh begitu cepat lupa bahwa beberapa dekade yang lalu, para peneliti terkemuka bahkan tidak yakin apakah dunia internet berfungsi atau mungkin (terlihat pada penelitian packet switching awal, pola desain baru yang radikal pada saat itu berangkat dari circuit-switching sebelumnya), dan bahkan beberapa tahun yang lalu ada kekhawatiran bahwa itu akan gagal untuk skala di beberapa titik dan mulai gagal karena lonjakan volume yang luar biasa.

itu juga menggunakan deteksi / koreksi kesalahan canggih . internet mungkin merupakan sistem terbesar, yang paling toleran terhadap kesalahan yang pernah dibangun oleh manusia, masih terus berkembang.

selanjutnya, ada alasan kuat untuk membuat algoritma yang memberdayakan WWW lebih maju. HTTP & server web sangat dicari / dioptimalkan dan juga menggunakan protokol keamanan / enkripsi (HTTPS) canggih. logika rendering halaman web telah menjadi sangat maju dalam HTML5 & CSS3 , bersama dengan bahasa pemrograman Javascript .

CSS yang relatif baru memiliki berbagai prinsip yang mirip dengan pemrograman OOP seperti usabilitas dan pewarisan. berbicara tentang penyusunan huruf, TeX adalah sistem pengaturan huruf ilmiah yang penting dan kompleks secara internal (tidak jauh berbeda dari bahasa pemrograman) yang ditemukan oleh Knuth yang sekarang dapat diterjemahkan di halaman web (dan mungkin digunakan dalam ratusan ribu makalah ilmiah atau lebih).

daerah lain yang relatif baru dalam membangun algoritma di internet, masih muncul, yang didasarkan pada kecerdasan kolektif . perangkat lunak stackexchange sendiri adalah contoh dari sistem intelijen kolektif yang canggih. jejaring sosial juga memperlihatkan fitur utama kecerdasan kolektif dan fitur terus ditambahkan untuk meningkatkan kecerdasan itu (misalnya facebook "Likes" baru berusia beberapa tahun). bidang sistem peringkat didasarkan pada algoritma penyaringan kolaboratif dan masih berkembang berdasarkan pada penelitian dan aplikasi baru.

jadi singkatnya, semua keberhasilan revolusioner mengubah pengalaman manusia sehari-hari sebenarnya cukup jauh melampaui sekadar "tujuan lapangan". sebagai judul pertanyaan menyatakan, semua algoritma inti dikerahkan . sekarang jadi di mana-mana dan tidak terlihat seperti ekspresi IT, "bagian dari pipa ledeng".

Algoritme (perangkat keras) yang luar biasa sukses adalah power-on reset.

Tanpa sistem di mana komputer berada dalam kondisi yang diketahui saat daya diterapkan, tidak ada hal lain yang terjadi dengan benar .

Reset pengaktifan adalah alasan mengapa segala sesuatu bekerja dengan baik yang memiliki CPU di dalamnya, baik yang disematkan atau tidak.

Lain kali Anda berada di lubang berair untuk programmer dan ilmuwan komputer, angkat gelas ceri Anda ke penyetelan daya.