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.


Komentar bukan untuk diskusi panjang; percakapan ini telah dipindahkan ke obrolan .
Bjørn Kjos-Hanssen

Jawaban:


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 .
Ada juga struktur data dan algoritma dalam kode pihak ketiga yang termasuk dalam kode Chromium.

  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.


5
@HuckBennett, CDCL adalah algoritma yang diparameterisasi oleh heuristik tetapi tidak sendiri heuristik. Ini memiliki perilaku eksponensial kasus terburuk tetapi tidak sepele untuk menunjukkan hal itu. Selain itu, kami tidak dapat melakukan yang lebih baik dan itu yang terbaik yang dapat kami lakukan dalam praktik, jadi saya merasa semua ilmuwan komputer harus mengetahuinya! Adapun LRU, FIFO, dll. Mereka adalah heuristik, tetapi, seperti ARC, mungkin memerlukan algoritma atau struktur data yang pintar untuk diimplementasikan.
Vijay D

9
Tidakkah komentar seperti itu telah diterapkan pada Simplex: awalnya tidak dipahami dengan baik dan kemudian terbukti eksponensial tetapi bekerja dalam praktik dan kemudian terbukti memiliki kompleksitas polinomial yang diperhalus? CDCL menarik untuk analisis algoritme karena Anda harus melalui kompleksitas bukti untuk memperoleh keluarga formula yang menunjukkan perilaku terburuk, dan juga untuk menunjukkannya bisa secara eksponensial lebih ringkas daripada beberapa varian resolusi. Ada berbagai ekstensi, seperti pemecahan simetri dan teknik autarky yang analisisnya masih terbuka.
Vijay D

28
Ini adalah harta karun bagi seorang siswa
neo1691

2
@ EmanueleViola, saya telah menambahkan beberapa contoh lagi. Posting sudah lama sekarang, jadi saya tidak ingin memperpanjangnya. Mungkin Anda harus mengajukan pertanyaan baru secara khusus tentang implementasi filter Dijkstra, Simplex, Bloom sebagai bagian dari sistem nyata seperti Linux, Chrome, server web, dll. Saya pikir Anda lebih mungkin mendapatkan jawaban yang baik jika Anda spesifik.
Vijay D

4
Berita hacker dan r / pemrograman.
Vijay D

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 MMkπ0kπ0M


7
Saya tidak berpikir ini adalah bahan algoritma yang khas.
Manu

14
Kebetulan saya pertama kali belajar tentang PageRank di kelas algoritma. Bahkan, saya pikir profesor memilihnya karena itu adalah contoh yang bagus dari "algoritma yang digunakan dalam praktek." Jika Anda membatasi contoh pada materi jenis "paruh pertama CLRS", daftar contoh akan terlalu panjang atau terlalu sepele - algoritma quicksort, B-tree, dan Dijkstra ada di mana-mana.
Huck Bennett

2
Kami mengajarkan PageRank kepada mahasiswa.
Aaron Roth

6
Saya juga mengajarkannya kepada mahasiswa tingkat sarjana (baik di kelas algoritme yang diperlukan maupun dalam algoritme grafik yang lebih terspesialisasi).
David Eppstein

2
Saya belajar PageRank sebagai sarjana dalam bidang pilihan.
Vijay D

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 .)


"Penelitian ekonomi dan operasi" tidak cukup spesifik. CPLEX juga bukan tipe contoh yang saya cari, karena ini hanyalah implementasi dari algoritma; akan berbeda jika, katakanlah, kompiler gcc menggunakan metode simpleks.
Manu

12
Saya pikir "masalah pemrograman linear" cukup spesifik ketika kita berbicara tentang ekonomi dan OR. Juga, oleh CPLEX saya maksudkan algoritma di balik implementasi.
vb le

16
"Hari ini, sebagian besar perusahaan besar menggunakan pemrograman linier untuk menentukan harga produk dan mengelola rantai pasokan. Perusahaan transportasi menggunakannya untuk memilih cara termurah untuk mengkonsolidasikan, mengoordinasikan, dan merutekan pengiriman banyak produk dari pemasok yang didistribusikan secara global ke pasar yang jauh dengan keterbatasan kapasitas. Minyak bumi industri menggunakannya untuk eksplorasi, pencampuran, penjadwalan dan distribusi produksi. Industri besi dan baja menggunakannya untuk mengevaluasi bijih besi, mengeksplorasi penambahan oven kokas dan memilih produk ... " news.stanford.edu/news/2005/may25/ dantzigobit-052505.html
Sasho Nikolov

Terima kasih. Tetapi saya menemukan kutipan itu sangat kabur. Saya pikir jika saya mengatakan bahwa di depan kelas siswa, setengahnya akan tertidur ;-) Akan berbeda jika kita mengatakan sesuatu seperti: UPS menggunakan LP untuk mengirim paket sebagai berikut ... Saya tidak mengatakan contoh seperti itu sepele untuk ditemukan, tetapi mengingat bahwa "sebagian besar perusahaan besar menggunakan LP" Saya berharap setidaknya kita bisa menunjuk ke satu .
Manu

10
Dari atas kepala saya, sejak 2007 LAX (bandara) telah menggunakan perangkat lunak untuk menyelesaikan permainan Stackelberg untuk menjadwalkan personil keamanan. Memecahkan piringan hitam besar adalah bagian dari semuanya, lihat misalnya teamcore.usc.edu/ARMOR-LAX . Selain itu, saya akan bertanya kepada seseorang dari departemen Riset Operasi Anda: mereka biasanya memiliki banyak cerita perang tentang penggunaan LP dalam kehidupan nyata
Sasho Nikolov

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 ...


Saya tidak yakin pernikahan yang stabil adalah materi algoritma yang umum.
Manu

16
Ada dalam buku Tardos dan Kleinberg Algorithms Design, dan juga dalam Randomized Algorithms Motwani, dan kedua buku ini banyak digunakan. Perkawinan yang stabil mungkin tidak diajarkan secara universal dalam kursus algoritme, tetapi hal itu tentu diajarkan dalam banyak hal.
Sasho Nikolov

10
Sebuah pencarian cepat mengungkapkan bahwa ia telah muncul di CS70 Berkeley , MIT 6,042 , UMD ini CMSC451 , dll ...
MHum

1
Menariknya, ketika Anda menambahkan dalam tugas pasangan, masalahnya menjadi NP-lengkap: arxiv.org/abs/1308.4534 . Namun, dalam praktiknya hal ini tampaknya tidak menyebabkan terlalu banyak masalah: en.wikipedia.org/wiki/…
Joshua Grochow

2
@EmanueleViola sementara itu mungkin tidak dibahas secara tradisional, dimasukkannya dalam buku Kleinberg / Tardos telah membuatnya menjadi lebih populer, (dan jika tidak seharusnya!)
Suresh Venkat

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.


1
Dan saya mendapat kuliah tentang pengkodean Huffman sebagai mahasiswa, yang diperlukan untuk sebuah proyek.
Brian S

Huffman ada di salah satu bab pertama CLRS, jadi pasti harus memenuhi syarat
Sasho Nikolov

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)


Saya pikir ini bisa diajarkan tetapi tidak diajarkan secara luas.
Manu

3
Sayangnya, tetapi benar. Namun, varian LSH (seperti sketsa Count-min dan kerabat) mulai muncul dalam kursus "data besar" atau "penambangan data". Saya mengajar filter bloom di kelas algoritma saya, misalnya.
Suresh Venkat

Sebagai pengalaman pribadi, LSH tidak memberi skala pada kami pada "big data" (item 100mln).
lynxoid

1
@lynxoid itu diskusi / pertanyaan terpisah :). Ada cukup banyak contoh di mana ia tidak bekerja yang saya pikir itu relevan dengan pertanyaan khusus ini.
Suresh Venkat

ε

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.


1
Contoh yang bagus (meskipun tidak cukup inti sekarang).
Manu

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!


Juga, versi sederhana dari algoritma ini digunakan untuk bertukar permainan papan: okasaki.blogspot.co.uk/2008/03/what-heck-is-math-trade.html
Radu GRIGore

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.

A * juga sering diajarkan dalam desain game. Saya tidak berpikir game 3D modern umumnya menggunakan A * untuk navigasi NPC, tetapi game 2D / isometrik, serta game yang lebih lama, memanfaatkan algoritma.
Brian S

@ Brian Apakah Anda tahu contoh algoritme pathfinding yang digunakan dalam game 3D, khususnya musuh NPC dalam game (seperti nPC penembak) Saya ingat pernah membaca sesuatu seperti ... membagi peta dalam sektor heksagonal dan menggunakannya sebagai node, bukan kotak. , dan itu memungkinkan gerakan yang lebih halus.
Goodwine

@ Goodwine, Maaf, saya tidak punya contoh nyata dari algoritma pathfinding di game 3D. Pengalaman pribadi saya adalah dengan lingkungan seperti "kubus" (peta yang terbuat dari kubus, karakter yang berdiri - pada dasarnya 2D, terlepas dari rendering 3D) dan AI boneka yang digunakan untuk menguji karakter pemain terhadap.
Brian S

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.


Saya akan melihat tetapi tidak terdengar seperti bahan algoritma yang khas.
Manu

8
Hmm, pembulatan acak biasanya diajarkan dalam kursus algoritma tingkat PhD, bukan?
Chandra Chekuri

2
Mengapa pembulatan acak saja? Sanjeev Arora, Elad Hazan dan Satyen Kale berpikir bahwa metode pembaruan bobot mulplicative pun cukup mendasar untuk diajarkan di level UG :) "Kami merasa bahwa algoritme meta kami dan analisisnya sederhana dan cukup berguna sehingga harus dilihat sebagai alat dasar diajarkan untuk semua siswa algoritma bersama dengan membagi-dan-menaklukkan, pemrograman dinamis, pengambilan sampel acak, dan sejenisnya. " (lih. cs.princeton.edu/~arora/pubs/MWsurvey.pdf ).
Jagadish


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.


Apakah Anda yakin TSP adalah masalah yang ingin diselesaikan perusahaan pengiriman paket? Saya pikir tantangan praktis yang lebih besar adalah ransel dan masalah pengepakan lainnya.
András Salamon

Tugas untuk pengemudi berubah setiap hari (yaitu orang UPS tidak perlu mengunjungi rumah yang sama setiap hari), sehingga rute harus diperbarui setiap hari. Ini bukan TSP murni - ada kendala tambahan seperti jalan satu arah, tidak ada putaran, mengantarkan paket di satu sisi jalan, tetapi tidak di sisi lain.
lynxoid

Saya yakin pengepakan juga penting.
lynxoid

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.]


Rujukan kedua berasal dari edisi Januari / Februari 2000 dari Computing in Science & Engineering, publikasi bersama American Institute of Physics dan IEEE Computer Society. dikompilasi oleh editor tamu Jack Dongarra dari University of Tennessee dan Oak Ridge National Laboratory dan Francis Sullivan dari Center for Computing Sciences di Institute for Defense Analysis
vzn

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


2
Akan lebih baik jika Anda bisa menunjuk ke penggunaan tertentu. Sesuatu seperti MS Word menggunakan KMP.
Manu

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


4
Penyortiran bukanlah suatu algoritma. Ini adalah tugas, yaitu, sesuatu yang ingin Anda lakukan, untuk itu Anda harus merancang (atau, dalam praktiknya, memilih) suatu algoritma.
David Richerby

Ini sepertinya bukan contoh spesifik seperti yang diminta dalam pertanyaan.
Kaveh

SGBD == RDBMS FYI untuk mereka yang tidak tahu.
Autodidact

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.



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.


Bagaimana ini contoh "algoritma inti ... yang digunakan dalam perangkat lunak / perangkat lunak komersial, pemerintahan, atau yang banyak digunakan"?
David Richerby

Akan bermanfaat untuk referensi silang implementasi dari masing-masing algoritma yang sangat baik yang tercantum dalam jawaban lain di sini untuk Wikipedia / DBpedia URI. Tidak ada Wikipedia / DBpedia URI untuk semua algoritme ini; tetapi ada halaman Kode Rosetta.
Wes Turner

bigocheatsheet.com juga mencantumkan kompleksitas Big-O dan tautan ke artikel Wikipedia untuk beberapa algoritma.
Wes Turner

Pertanyaannya menanyakan contoh algoritma inti yang digunakan dalam perangkat lunak yang signifikan. "Ini situs web dengan algoritme yang diterapkan dalam sejuta bahasa" tidak menjawab pertanyaan itu sama sekali. Sebenarnya, itu kebalikan dari apa yang dicari pertanyaan itu.
David Richerby

Referensi yang berguna, relevan secara kontekstual.
Wes Turner

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".


banyak kutipan dapat ditambahkan ke ini. di sini adalah salah satu untuk memulai: DARPA dan revolusi internet oleh Waldrop
vzn

ref lain pada optimasi internet, biografi Danny Lewin , salah seorang pendiri akamai, "genius yang mengubah internet"
vzn

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.


5
Reset pengaktifan bukan algoritma. Ini adalah tugas, yaitu, sesuatu yang ingin Anda lakukan, di mana Anda harus merancang algoritma.
David Richerby
Dengan menggunakan situs kami, Anda mengakui telah membaca dan memahami Kebijakan Cookie dan Kebijakan Privasi kami.
Licensed under cc by-sa 3.0 with attribution required.