Apakah ada analisis matematis algoritmik?

Ada teori grafik algoritmik / teori bilangan / kombinatorik / teori informasi / teori permainan.

Apakah ada analisis matematis algoritmik?

Menurut wiki, analisis matematis mencakup teori diferensiasi, integrasi, ukuran, batas, deret tak hingga, dan fungsi analitik. Tidak masalah untuk fokus pada analisis nyata (wiki) yang berkaitan dengan bilangan real dan fungsi bernilai riil dari variabel nyata.

"Algoritma" berarti mempelajari sesuatu dari sudut pandang teori komputabilitas dan teori kompleksitas.

Googling dari "analisis matematika algoritmik" menuntun saya ke "analisis matematika algoritma" atau "aplikasi analisis algoritma", yang bukan itu yang saya maksud.

Lihat Komputasi dan Kompleksitas dalam jaringan Analisis . Mengutip:

Topik-topik yang menarik termasuk pekerjaan dasar pada berbagai model dan pendekatan untuk menggambarkan komputabilitas dan kompleksitas dibandingkan bilangan real. Mereka juga termasuk investigasi kompleksitas-teoritik, baik yang mendasar maupun sehubungan dengan masalah nyata, dan implementasi baru aritmatika nyata yang tepat, serta pengembangan lebih lanjut dari paket perangkat lunak yang sudah ada.

(Penafian: Saya bukan ahli, silakan menyarankan koreksi, atau menulis jawaban yang lebih komprehensif jika Anda.)

$e^x$ tidak dapat dihitung dalam model BSS.

$f: \mathbb{R} \to \mathbb{R}$$f(x)$$x$

$f:[0,1] \to [0,1]$

Merumuskan teori kompleksitas untuk fungsi nyata adalah, AFAIK, bahkan lebih rumit. Ini terkait dengan fakta bahwa menghitung fungsi nyata adalah perhitungan tingkat tinggi (karena dibutuhkan mesin Turing sebagai input) sehingga ukuran bit input biasanya bukan hal yang tepat untuk mengukur runtime terhadap. Periksa makalah ini oleh Mark Braverman untuk satu pendekatan untuk mendefinisikan komputasi nyata yang efisien. Pada titik ini saya jauh dari kedalaman untuk mengatakan lebih banyak, jadi saya akan berhenti.

Referensi klasik untuk kompleksitas perhitungan fungsi nyata adalah:

• Ker-I Ko, Kompleksitas Komputasi Fungsi Riil, 1991

Lihat juga bab 7 dalam buku Weirauch.

Melihat pertanyaan ini lebih dari dua tahun setelah diposting dan, jangan tersinggung, saya kecewa dengan jawaban dan komentarnya.

Inilah yang terjadi ketika departemen CS di seluruh dunia salah memberi label pada topik mereka dan menyesatkan banyak generasi ilmuwan dan insinyur.

• Baik kelas Algoritma di semua departemen CS perlu dilabel ulang ke Algoritma Diskrit .

• Atau konten saat ini dari kelas itu perlu dikurangi hingga 50% atau kurang (bahwa 50% atau kurang termasuk Struktur Data ) dan setengah sisanya perlu mencakup beberapa topik yang beragam dari Analisis Numerik dan Komputasi Ilmiah .

Karena apa inti dari Analisis Matematika ? Analisis nyata dan garis nyata. Dan bagaimana bilangan real direpresentasikan dalam komputer? floating point, atau presisi sewenang-wenang, dll. Jadi, lain kali Anda bekerja pada algoritma apa pun yang berkaitan dengan floating point dan / atau presisi arbitrer sebagai komponen inti (bukan sebagai konten, seperti dalam mengurutkan sekelompok angka floating point) , ketahuilah bahwa Anda sedang melakukan Analisis Matematika Algoritmik (AMA)!

Dan bahkan tidak memulai saya dengan semesta besar topik NA / Ilmu Komputasi. Ini bisa dibilang kerdil seluruh TCS. Ketika Anda memecahkan sistem beberapa PDE non-linear pada komputer, Anda tidak hanya memanfaatkan dasar-dasar analisis matematis, tetapi juga analisis fungsional mutakhir dalam segala kejayaannya, lengkap dengan masalah penelitian terbuka, dll. dapatkan lebih banyak AMA dari itu.