Apakah ada aplikasi teknik dalam analisis nyata untuk ilmu komputer teoretis?

Saya telah mencari jauh untuk aplikasi semacam itu dan sebagian besar muncul pendek. Saya dapat menemukan banyak aplikasi topologi dan struktur serupa pada set yang dapat dihitung (atau tidak terhitung), tetapi jarang saya benar-benar menemukan set yang tidak terhitung sebagai objek studi oleh para ilmuwan komputer, dan karena itu mengarah pada kebutuhan akan teknik dari analisis.

Berikut adalah dua kursus terkait:

• Metode analitik dalam kombinatorik dan CS oleh Ehud Friedgut di University of Toronto (2009),
• Metode Analitik dalam Combinatorics dan Ilmu Komputer oleh Irit Dinur dan Ehud Friedgut di Hebrew University (2006).

Periksa juga catatan Ryan O'Donnell untuk bukunya:

• Analisis Fungsi Boolean oleh Ryan O'Donnell.

dan tautan di sudut kanan atas.

Lihat buku Matematika Beton - Yayasan Ilmu Komputer oleh Graham, Knuth dan Patashnik. Dalam Bab 9 mereka menjelaskan rumus penjumlahan Euler-Maclaurin . Ini adalah teknik yang memungkinkan Anda untuk memperkirakan jumlah terbatas dengan menggunakan integral. Dalam bab yang sama, halaman 466, mereka menggunakan teknik ini untuk mendekati angka harmonik (yang banyak muncul di beberapa area TCS). Itu terjadi pada saya satu kali saya harus menggunakannya, dan akhirnya menyelesaikan integral menggunakan teknik pendekatan asimptotik untuk persamaan diferensial!

Ada teori batas urutan grafik yang padat, yang dikembangkan dalam karya Lovasz dan B. Szegedy. Ini memiliki implikasi untuk masalah pengujian properti tertentu pada grafik. Lihat http://www.cs.elte.hu/~lovasz/hom-stoc.pdf . Pada dasarnya idenya adalah bahwa mereka menentukan metrik yang sesuai pada grafik dan gagasan mengambil batas urutan grafik, dan kemudian mereka menunjukkan bahwa properti grafik dapat diuji jika fungsi yang memetakan grafik ke jarak edit ke properti kontinu dalam ruang metrik pada grafik yang ditentukan.

Dan tentu saja ada magnum opus Flajolet dan Sedgewick yang didedikasikan sepenuhnya untuk menggunakan metode analitik untuk analisis asimtotik dari struktur kombinatorial, termasuk analisis algoritma. Ini sebagian besar menghasilkan trik fungsi yang mengandalkan analisis yang kompleks

Seperti yang disebutkan Shir, ketidaksetaraan Jensen selalu muncul. Terutama dalam membuktikan batas dalam masalah kombinatorial. Sebagai contoh pertimbangkan masalah berikut:

Diberikan keluarga dari himpunan bagian dari V = { 1 , ... , n } , grafik perpotongannya G = ( V , E ) didefinisikan oleh { i , j } ∈ E jika dan hanya jika S i ∩ S j ≠ ∅ . Misalkan ukuran set rata-rata adalah r dan ukuran rata-rata persimpangan berpasangan paling banyak k. Menunjukkan bahwa$S_1, \ldots, S_n$$V = \{1, \ldots, n\}$$G = (V, E)$$\{i, j\} \in E$$S_i \cap S_j \neq \emptyset$$r$ .$|E| \geq \frac{n}{k} \cdot \binom{r}{2}$

Bukti:

Mari kita hitung pasangan sehingga x ∈ V dan x ∈ S i ∩ S j . Mari kita perbaiki dulu ( S i , S j ) , kita melihat bahwa ada paling banyak k pilihan seperti itu. Mengambil semua nilai ( S i , S j ) juga, kita memiliki batas atas k ⋅ ($(x, (S_i, S_j))$$x \in V$$x \in S_i \cap S_j$$(S_i, S_j)$$k$$(S_i, S_j)$. Kami sekarang memperbaiki x. Sangat mudah untuk melihat bahwa setiapxmemiliki ( d(x$k \cdot \binom{n}{2} = k \cdot |E|$$x$ cara untuk memilih(Si,Sj). Dengan ketidaksetaraan Jensen kita memiliki:$\binom{d(x)}{2}$$(S_i, S_j)$

.$n \cdot \binom{r}{2} = n \cdot \binom{\frac{1}{n}\sum_x d(x)}{2} \leq \sum_x \binom{d(x)}{2} \leq k \cdot |E|$

Kami akhirnya menggabungkan istilah untuk memiliki .$\frac{n}{k} \cdot \binom{r}{2} \leq |E|$

Meskipun ini sedikit lebih "matematis" daripada CS, ini berfungsi untuk menunjukkan bagaimana alat untuk fungsi cembung dapat digunakan - dalam optimasi kombinatorial, khususnya.

bagaimana dengan Perhitungan Efisien dengan Dedekind Reals oleh Andrej Bauer dan Paul Taylor.

Teknik yang sangat umum dan sering berguna ketika mendekati masalah dalam matematika diskrit adalah menanamkannya dalam domain kontinu, karena ini memungkinkan pilihan alat matematika yang lebih kaya untuk digunakan. Jadi, mengoreksi jawaban saya: selain bidang yang analisis nyata akan muncul secara alami di (grafik, pemrosesan sinyal dan bidang lain yang meniru atau berinteraksi dengan dunia fisik), itu muncul pada dasarnya di mana-mana, dan di tempat yang tidak - saya Dugaan itu akan terjadi di masa depan.

Beberapa contoh cepat:

1. Kode koreksi kesalahan: Reed solomon menggunakan polinomial. Beberapa batasan pada kode melibatkan melihat fungsi indikator dari kode sebagai fungsi dari kubus diskrit ke real, sehingga menerapkan transformasi Fourier dan teknik lainnya.
2. Metode probabilistik - mengukur teorema konsentrasi (alat analitik) digunakan untuk menunjukkan berbagai sifat grafik acak (misalnya bilangan kromatik). Lihat buku Alon and Spencer.

3. $v$$e$$\frac {1}{61} \cdot \frac {e^3} {v^2}$

4. $k-1$$k$$k-1$

Jika saya mengingat kembali dengan benar teorema Noga Alon tentang membelah kalung menggunakan versi masalah yang berkelanjutan.

Lihat: http://www.cs.tau.ac.il/~nogaa/PDFS/nocon.pdf

Ada juga yang menyebutkan hal itu di halaman wiki di sini: http://en.wikipedia.org/wiki/Hobby%E2%80%93Rice_theorem

Bidang ukuran terbatas sumber daya berlaku ukuran Lebesgue untuk kelas kompleksitas. Idenya adalah untuk memperoleh pemisahan antara kelas kompleksitas dengan berbicara tentang "ukuran" relatif dari set ini.

Ada makalah yang indah, Quantum One-Way Communication secara eksponensial lebih kuat daripada komunikasi klasik oleh Boaz Klartag & Oded Regev, yang menggunakan sejumlah besar teknik dari analisis nyata yang tidak biasa dalam TCS, termasuk transformasi Radon, harmonik bola & hypercontractive ketidaksetaraan pada unit sphere (non-diskrit)

Batas Bawah Eksponensial untuk Ukuran Sirkuit Nyata Monoton (1997) oleh Haken, Cook

Saya selalu menemukan koneksi antara bahasa reguler / bebas konteks dan teori fungsi (seri formal) cukup menarik: itulah sebabnya orang Prancis menyebut kelas bahasa ini "rasional" dan "aljabar". Ini juga menunjukkan koneksi ke geometri fraktal. Dalam nada yang sama, misalnya, automata terbatas mungkin mendefinisikan bahasa pada kata-kata tak terbatas yang memiliki sifat topologi yang bagus ketika dilengkapi dengan topologi metrik standar.

Koneksi lain mungkin adalah teori "set convolutions" yang dikembangkan baru-baru ini yang memungkinkan untuk mempercepat beberapa algoritma yang mirip dengan apa yang dikenal dari transformasi Fourier. Saya berasumsi bahwa ini adalah setidaknya "kesamaan inspirasi".