Algoritma Penghampiran Bahagian I | Rangkaian Universiti

Penerangan Produk

Algoritma penghampiran, Bahagian I

Berapa cekap anda boleh membungkus objek ke dalam bilangan minimum kotak? Sebaik-baiknya anda boleh mengumpul nod supaya dapat memisahkan rangkaian dengan mudah ke beberapa komponen di sekitar beberapa pusat? Ini adalah contoh masalah pengoptimalan combinatorial NP-keras. Adalah mustahil untuk menyelesaikan masalah tersebut dengan cekap, jadi matlamat kami adalah untuk memberikan penyelesaian anggaran yang boleh dikira dalam masa polinomial dan pada masa yang sama mempunyai jaminan yang boleh terbukti pada kosnya berbanding dengan yang optimum.

Kursus ini mengasumsikan pengetahuan mengenai kursus Algoritma sarjana yang standard, dan khususnya menekankan algoritma yang boleh direka menggunakan pengaturcaraan linear, teknik kegemaran dan luar biasa yang berjaya di dalam bidang ini. Dengan mengambil kursus ini, anda akan terdedah kepada pelbagai masalah di asas sains komputer teoritis, dan teknik reka bentuk dan analisis yang kuat. Setelah selesai, anda akan dapat mengenali, ketika menghadapi masalah pengoptimalan kombinatorial baru, apakah itu dekat dengan salah satu dari beberapa masalah dasar yang diketahui, dan akan dapat merancang pelurusan pemrograman linear dan menggunakan pembulatan rawak untuk mencoba menyelesaikan masalah sendiri. Kandungan kursus dan khususnya kerja rumah adalah bersifat teori tanpa sebarang tugasan pengaturcaraan.

Ini adalah yang pertama dari kursus dua bahagian pada Algoritma Penghampiran.