Algoritma tingkat tinggi

Sebagian besar algoritma terkenal adalah urutan pertama, dalam arti bahwa input dan outputnya adalah data "biasa". Beberapa di antaranya adalah urutan kedua dengan cara sepele, misalnya menyortir, hashtable atau fungsi peta dan lipat: semuanya di-parameterkan oleh suatu fungsi, tetapi mereka tidak benar-benar melakukan sesuatu yang menarik dengannya kecuali memintanya pada potongan data input lainnya.

Beberapa juga ada di urutan kedua tetapi agak lebih menarik:

• Fingertrees diparameterisasi oleh monoids
• Membagi satu ujung jari pada predikat monoton
• Algoritma penjumlahan awalan, lagi biasanya diparameterisasi dengan monoid atau predikat dll.

Akhirnya, ada yang "benar-benar" tingkat tinggi dalam arti yang paling menarik bagi saya:

• Penggabung Y
• Daftar perbedaan

Apakah ada algoritma orde tinggi nontrivial lainnya?

Dalam upaya untuk mengklarifikasi pertanyaan saya, di bawah "orde tinggi tingkat tinggi" yang saya maksudkan "menggunakan fasilitas tingkat tinggi dari formalisme komputasi dengan cara yang kritis dalam antarmuka dan / atau implementasi algoritme"

Ada banyak fungsi urutan yang lebih tinggi pada http://math.andrej.com/ , misalnya dalam posting tentang eksponensial ganda , tipe Haskell berikut muncul (dengan jenis sinonim diperluas):

shift :: Bool -> ((Int -> Bool) -> Bool) -> ((Int -> Bool) -> Bool)

Anda juga dapat bersenang-senang dengan pos A Haskell Monad untuk Pencarian Tak Terbatas di Waktu Terbatas - misalnya:

newtype S a = S ((a -> Bool) -> a)
bigUnion :: S (S a) -> S a

Saya kira tipe bigUnion adalah pesanan ke-4 atau ke-5!

ada banyak algoritma yang "benar-benar urutan kedua" meskipun biasanya tidak dijelaskan secara eksplisit dalam istilah ini. Setiap kali kita memiliki algoritma waktu sub-linear, implisit adalah semacam akses oracle ke input, yaitu benar-benar memperlakukan input sebagai fungsi.

Contoh:

(1) Algoritme Ellipsoid saat bekerja dengan "oracle separasi" (mis. Http://math.mit.edu/~vempala/18.433/L18.pdf )

(2) Minimalisasi fungsi submodular (mis. Http://people.commerce.ubc.ca/faculty/mccormick/sfmchap8a.pdf )

(3) Seluruh bidang pengujian properti benar-benar dalam bentuk ini ( http://www.wisdom.weizmann.ac.il/~oded/test.html )

(4) Lelang kombinatorial dalam model kueri (mis. Http://pluto.huji.ac.il/~blumrosen/papers/iter.pdf )

Ada jawaban lain untuk pertanyaan ini: tidak ada. Lebih khusus lagi, algoritma tingkat tinggi (dapat diterapkan!) Seperti itu secara mekanis setara dengan algoritma tingkat pertama, menggunakan defungsionalisasi .

Biarkan saya lebih tepat: walaupun memang ada algoritma tingkat tinggi yang sebenarnya, dalam praktiknya selalu mungkin untuk menulis ulang setiap contoh sebagai program murni tingkat pertama. Dengan kata lain, tidak ada program tingkat tinggi jenuh - pada dasarnya karena input / output program adalah string bit. [Ya, string bit itu bisa mewakili fungsi, tapi itu intinya: mereka mewakili fungsi, itu bukan fungsi].

Jawaban yang sudah diberikan sangat bagus, dan jawaban saya tidak boleh dianggap bertentangan. Itu harus dianggap sebagai menjawab pertanyaan dari dalam konteks yang sedikit lebih besar (menyelesaikan program bukannya algoritma yang berdiri sendiri). Dan perubahan konteks ini mengubah jawabannya secara radikal. Inti dari jawaban saya adalah untuk mengingatkan orang akan hal ini, yang terlalu mudah untuk dilupakan.

Dalam parser combinator libraries urutan fungsi umumnya cukup tinggi. Lihat Bahkan Fungsi Orde Tinggi untuk Parsing atau Mengapa Ada Yang Ingin Menggunakan Fungsi Orde Keenam? oleh Chris Okasaki. Jurnal Pemrograman Fungsional , 8 (2): 195-199, Maret 1998.

Analisis yang dapat dikomputasi mencirikan bilangan real secara terprogram, karena bilangan real mengandung jumlah informasi yang tidak terbatas, sehingga operasi pada bilangan real lebih berurutan tinggi dalam arti pertanyaan. Biasanya, bilangan real disajikan dengan menggunakan pandangan topologi pada aliran bit tak terbatas, ruang Cantor, memberikan minat pada bidang topologi komputabel yang lebih luas.

Klaus Weihrach telah membicarakan hal ini sebagai Hierarki Efektivitas Tipe Dua dari topologi yang dapat dihitung. Untuk lebih lanjut tentang ini, lihat Weihrach & Grubba, 2009, Topologi Komputasi Dasar , dan di halaman penelitian John Tucker, Komputasi dengan Data Topologis . Saya menyebutkan halaman Tucker dalam pertanyaan saya, Aplikasi Ruang Cantor .

Sebuah modulus kontinuitas fungsional adalah peta myang menerima (kontinu) fungsional F : (nat -> nat) -> natdan output nomor ksehingga F f = F gsetiap kali f i = g iuntuk semua i < k. Ada algoritma untuk menghitung modulus kontinuitas (bukan yang sangat efisien), sehingga menjadikannya sebuah instance dari algoritma urutan ke-3.

Untuk melengkapi jawaban Noam , ada juga beberapa situasi di mana penting untuk memiliki output menjadi (representasi eksplisit dari) suatu fungsi.

$C: \\{0,1\\}^n \rightarrow \\{0,1\\}^m$$A$ $(\alpha,L,\epsilon)$$C$$n$$A$$M_1,\dots,M_L$

$\begin{align}\forall w \in \\{0,1\\}^m, Pr_A [&\forall m,~(Ag(C(m),w) \geq \alpha \Rightarrow \\\ &\exists i \in [L],~\forall j \in [n],~Pr_{M_i}[M_i(j) = m_j] \geq 1-\epsilon)] \geq 2/3\end{align}$

$Ag$$A$$2/3$$\epsilon$$m$$m$$\alpha$

Dalam algoritme grafik, simpul dan tepi biasanya dianggap sebagai data biasa tetapi sebenarnya dapat digeneralisasikan secara produktif sehingga diprogram sesuai permintaan.

Selama PhD saya (dalam kimia komputasi) saya menerapkan banyak algoritma grafik dalam bentuk tingkat tinggi untuk menerapkannya pada analisis grafik implisit, terutama karena grafik aktual saya tidak terbatas sehingga saya tidak mampu menyimpannya secara eksplisit! Secara khusus, saya sedang mempelajari topologi bahan amorf yang direpresentasikan sebagai 3D tilings sel unit (supercell).

Misalnya, Anda dapat menulis fungsi untuk menghitung shell tetangga n-terdekat dari simpul asal iseperti ini:

nth i 0 = {i}
nth i 1 = neighbors i
nth i n = diff (diff (fold union empty (map neighbors (nth i (n-1)))) (nth i (n-1))) (nth i (n-2))

di mana neighborsfungsi yang mengembalikan himpunan simpul tetangga ke simpul yang diberikan.

Misalnya, kisi persegi 2D:

neighbors (x, y) = {(x-1, y), (x+1, y), (x, y-1), (x, y+1)}

Algoritma menarik lainnya dalam konteks ini termasuk statistik jalur terpendek Franzblau.