Teori Matematika

Menggunakan Teori Matematika Untuk Menemukan Potensi Sebenarnya Dari Algoritma

Menggunakan Teori Matematika Untuk Menemukan Potensi Sebenarnya Dari Algoritma – Menggunakan teori matematika, Virginia Williams membujuk algoritma untuk berjalan lebih cepat atau membuktikan bahwa mereka telah mencapai kecepatan maksimumnya. Setiap semester, Associate Professor Virginia Vassilevska Williams mencoba memberikan satu pelajaran mendasar kepada mahasiswa ilmu komputernya: Matematika adalah dasar dari segalanya.

Menggunakan Teori Matematika Untuk Menemukan Potensi Sebenarnya Dari Algoritma

thebigvantheory – Seringkali, siswa datang ke kelas Williams, 6.006 (Pengantar Algoritma), ingin menyelami pemrograman tingkat lanjut yang mendukung teknik komputasi terbaru dan terhebat. Pelajarannya malah berfokus pada bagaimana algoritma dirancang di sekitar model dan konsep matematika inti.

“Saat mengambil kelas algoritme, banyak siswa berharap untuk memprogram banyak dan mungkin menggunakan pembelajaran mendalam, tetapi ini sangat matematis dan memiliki sedikit pemrograman,” kata Williams, Steven G. (1968) dan Profesor Pengembangan Karir Renee Finn yang baru-baru ini memperoleh gelar masa jabatan di Departemen Teknik Elektro dan Ilmu Komputer. “Kami tidak memiliki banyak waktu bersama di kelas (hanya dua jam seminggu), tetapi saya berharap pada waktu itu mereka dapat melihat sedikit keindahan matematika karena matematika memungkinkan Anda untuk melihat bagaimana dan mengapa semuanya bekerja bersama. Itu benar-benar hal yang indah.”

Kehidupan Williams sangat ditentukan oleh matematika. Sebagai anak dari dua orang tua matematikawan, dia jatuh cinta dengan subjek sejak dini. Tetapi meskipun dia unggul dalam mata pelajaran itu, kelas-kelas sekolah menengahnya berfokus pada bahasa Jerman, menulis, dan biologi. Kembali ke cinta pertamanya di perguruan tinggi dan seterusnya, dia menerapkan keterampilan matematikanya untuk membuat gelombang dalam ilmu komputer.

Dalam pekerjaan yang sangat berpengaruh, Williams pada tahun 2012 meningkatkan algoritme untuk “perkalian matriks” operasi mendasar di seluruh ilmu komputer yang dianggap sebagai iterasi tercepat selama 24 tahun. Bertahun-tahun kemudian, dia ikut mendirikan bidang baru yang disebut “kompleksitas berbutir halus,” yang berusaha menjelaskan, sebagian, seberapa cepat algoritme tertentu dapat menyelesaikan berbagai masalah.

Dalam perkalian matriks, pekerjaannya sekarang telah sedikit bergeser untuk menunjukkan bahwa teknik yang ada “tidak dapat melakukan yang lebih baik,” katanya. “Kami tidak dapat meningkatkan kinerja algoritme kami sendiri lagi, jadi kami menemukan cara untuk menjelaskan mengapa kami tidak dapat dan mengapa metode lain juga tidak dapat meningkatkan kinerja.”

Jalan berliku menuju matematika

Tumbuh di Sofia, Bulgaria, Williams menyukai matematika dan merupakan siswa yang berbakat. Tetapi orang tuanya sering mengingatkannya bahwa kehidupan matematikawan itu tidak sepenuhnya glamor terutama ketika mencoba mencari pertunjukan fakultas di area yang sama untuk dua orang. Mereka kadang-kadang bepergian ke mana pekerjaan membawa mereka.

Itu termasuk pengembaraan singkat di sekitar AS sebagai seorang anak. Pemberhentian pertama adalah Laramie, Wyoming. Orang tuanya mengunjungi profesor di Universitas Wyoming, sementara Williams awalnya berjuang melalui kelas empat karena kendala bahasa. “Saya tidak benar-benar berbicara bahasa Inggris, dan dilemparkan ke sekolah ini. Saya dan saudara saya belajar bahasa Inggris dengan menonton saluran Disney, yang sangat menyenangkan,” kata Williams, yang hari ini berbicara bahasa Bulgaria, Inggris, Jerman, dan sedikit bahasa Rusia.

Perhentian berikutnya adalah Los Angeles tepat pada saat kerusuhan Rodney King. “Rumah di seberang jalan kami dibakar,” kenang Williams. “Itu adalah beberapa kenangan yang sangat aneh dari LA”

Baca Juga : Geometris Sangat Berhubungan Dengan Teori Martematika

Kembali ke Bulgaria setelah dua tahun, Williams memutuskan untuk “menjelajahi pilihannya” di luar matematika dengan mendaftar di Sekolah Menengah Bahasa Jerman di Sofia, sekolah menengah atas negara itu pada saat itu, di mana dia belajar bahasa Jerman, sastra, sejarah, dan lainnya. mata pelajaran humaniora. Tapi, ketika harus mendaftar ke perguruan tinggi, dia tidak pernah bisa menggoyahkan cinta pertamanya. “Saya benar-benar mencoba menyukai humaniora, dan apa yang saya pelajari sangat membantu saya saat ini. Tapi mata pelajaran itu sangat sulit bagi saya. Otak saya tidak bekerja seperti itu,” katanya. “Aku kembali ke apa yang aku suka.”

Terpaku oleh algoritma

Pada tahun 1999, Williams mendaftar di Caltech. Di tahun keduanya, dia jatuh cinta pada bidang baru yang menarik: ilmu komputer. “Saya mengambil kursus pemrograman pertama saya, dan saya menyukainya,” katanya. Dia menjadi terpaku oleh algoritma perkalian matriks, yang memiliki beberapa matematika tugas berat pada intinya. Algoritme ini menghitung beberapa larik angka yang sesuai dengan beberapa data dan menghasilkan matriks gabungan tunggal dari beberapa nilai target. Aplikasi sangat luas, termasuk grafik komputer, desain produk, kecerdasan buatan, dan bioteknologi.

Sebagai Ph.D. mahasiswa di Carnegie Mellon, dan seterusnya, dia menerbitkan banyak makalah, tentang topik-topik seperti mengembangkan algoritma perkalian matriks cepat dalam struktur aljabar khusus, dengan aplikasi termasuk penjadwalan penerbangan dan perutean jaringan. Setelah mendapatkan gelar PhD, dia mengambil serangkaian posisi postdoc dan peneliti di Institute for Advanced Study, University of California di Berkeley, dan Stanford University, di mana dia mendapatkan posisi fakultas pada tahun 2013 mengajar kursus tentang algoritma.

Pada tahun 2012, ia mengembangkan algoritme baru yang lebih cepat daripada algoritme Coppersmith–Winograd, yang telah mendominasi perkalian matriks sejak 1980-an. Metode Williams mengurangi jumlah langkah yang diperlukan untuk mengalikan matriks. Algoritmenya hanya sedikit lebih lambat dari pemegang rekor saat ini.

Berurusan dengan kompleksitas
Antara 2010 dan 2015, Williams dan suaminya, Ryan Williams, yang juga seorang profesor MIT , menjadi pendiri utama “kompleksitas halus.” Bidang yang lebih tua dari “kompleksitas komputasi” menemukan algoritma yang terbukti efisien dan algoritma yang mungkin tidak efisien, berdasarkan beberapa ambang langkah komputasi yang mereka ambil untuk memecahkan masalah.

Kompleksitas berbutir halus mengelompokkan masalah bersama-sama dengan kesetaraan komputasi untuk membuktikan dengan lebih baik apakah algoritma benar-benar optimal atau tidak. Misalnya, dua masalah mungkin tampak sangat berbeda dalam penyelesaiannya dan berapa banyak langkah yang diambil algoritma untuk menyelesaikannya. Tapi kompleksitas halus menunjukkan masalah seperti itu diam-diam sama. Oleh karena itu, jika ada algoritma untuk satu masalah yang menggunakan langkah lebih sedikit, maka harus ada algoritma untuk masalah lain yang menggunakan langkah lebih sedikit, dan sebaliknya. Di sisi lain, jika ada algoritma yang terbukti optimal untuk satu masalah, maka semua masalah yang setara harus memiliki algoritma yang optimal. Jika seseorang pernah menemukan algoritma yang jauh lebih cepat untuk satu masalah, semua masalah yang setara dapat diselesaikan lebih cepat.

Sejak peluncuran bersama lapangan, “itu menggelembung,” kata Williams. “Untuk sebagian besar konferensi ilmu komputer teoretis, Anda sekarang dapat mengirimkan makalah Anda di bawah judul ‘kompleksitas berbutir halus.’”

Pada tahun 2017, Williams datang ke MIT, di mana dia mengatakan dia telah menemukan peneliti yang bersemangat dan berpikiran sama. Banyak mahasiswa pascasarjana dan rekan kerja, misalnya, bekerja dalam topik yang berkaitan dengan kompleksitas halus. Pada gilirannya, murid-muridnya telah memperkenalkannya ke mata pelajaran lain, seperti kriptografi, di mana dia sekarang memperkenalkan ide-ide dari kompleksitas halus.

Dia juga terkadang mempelajari “pilihan sosial komputasional,” bidang yang menarik perhatiannya selama sekolah pascasarjana. Karyanya berfokus pada pemeriksaan kompleksitas komputasi yang diperlukan untuk mengatur permainan olahraga, skema pemungutan suara, dan sistem lain di mana pesaing ditempatkan dalam tanda kurung berpasangan. Jika seseorang tahu, misalnya, pemain mana yang akan menang dalam pertandingan berpasangan, penyelenggara turnamen dapat menempatkan semua pemain di posisi tertentu di penyemaian awal untuk memastikan pemain tertentu memenangkan semuanya.

Mensimulasikan semua kemungkinan kombinasi untuk mengatur skema ini bisa sangat kompleks secara komputasi. Tetapi Williams, seorang pemain tenis yang rajin, menulis makalah 2010 (PDF) yang menemukan bahwa cukup mudah untuk mengatur turnamen eliminasi tunggal sehingga pemain tertentu menang, tergantung pada prediksi akurat untuk pemenang pertandingan dan faktor lainnya.

Tahun ini dia ikut menulis makalah (PDF) yang menunjukkan penyelenggara turnamen dapat mengatur penyemaian awal dan menyuap pemain top tertentu dalam anggaran tertentu — untuk memastikan pemain favorit memenangkan turnamen. “Ketika saya perlu istirahat dari pekerjaan saya yang biasa, saya bekerja di bidang ini,” kata Williams. “Ini adalah perubahan kecepatan yang menyenangkan.”

Berkat komputerisasi di mana-mana saat ini, mahasiswa pascasarjana Williams sering kali memasuki kelasnya jauh lebih berpengalaman dalam ilmu komputer daripada saat seusia mereka. Tetapi untuk membantu mengarahkan mereka ke jalan yang berbeda, dia mengambil inspirasi dari pengalaman kuliahnya sendiri, tertarik pada topik tertentu yang masih dia kejar sampai sekarang.

“Untuk melakukan penelitian yang baik, Anda harus terobsesi dengan masalah,” kata Williams. “Saya ingin mereka menemukan sesuatu dalam kursus saya yang dapat membuat mereka terobsesi.”