Algorithms And Problems

Shorting Atau Penyortiran

   Masalah penyortiran adalah untuk mengatur ulang item dari daftar yang diberikan di nondecreasing memesan. Tentu saja, untuk masalah ini menjadi bermakna, sifat dari daftar item harus memungkinkan pemesanan tersebut. (Matematika akan mengatakan bahwa harus ada hubungan total pemesanan.) Sebagai masalah praktis, biasanya kita perlu memilah daftar angka, karakter dari alfabet, karakter string, dan, yang paling penting, catatan mirip dengan yang dikelola oleh sekolah tentang siswa mereka, perpustakaan tentang kepemilikan mereka, dan perusahaan tentang karyawan mereka. Dalam kasus catatan, kami harus memilih sepotong informasi untuk memandu penyortiran. Sebagai contoh, kita bisa memilih untuk menyortir catatan siswa dalam urutan abjad nama atau nomor siswa atau oleh siswa kelas-titik rata-rata. Seperti sepotong khusus dipilih dari informasi disebut kunci. ilmuwan komputer sering berbicara tentang menyortir daftar kunci bahkan ketika daftar ini item tidak catatan tetapi, mengatakan, hanya bilangan bulat.

Mengapa kita ingin daftar diurutkan? Untuk mulai dengan, daftar diurutkan dapat menjadi diperlukan

Output dari tugas seperti peringkat hasil pencarian Internet atau peringkat siswa dengan mereka GPAscores. Selanjutnya, penyortiran membuat banyak pertanyaan tentang daftar mudah untuk menjawab. Yang paling penting dari mereka adalah mencari: itu sebabnya kamus, buku telepon, daftar kelas, dan sebagainya diurutkan. di beberapa algoritma penting di daerah lain, misalnya, algoritma geometrik dan data kompresi. The-pendekatan teknik desain serakah penting algoritma dibahas nanti dalam buku-membutuhkan masukan diurutkan.

Sekarang, ilmuwan komputer telah menemukan puluhan algoritma sorting yang berbeda. Bahkan, menciptakan algoritma sorting baru telah disamakan dengan merancang yang perangkap tikus pepatah. Dan saya senang melaporkan bahwa berburu untuk lebih baik menyortir perangkap tikus terus. ketekunan ini mengagumkan dalam pandangan berikut ini fakta. Di satu sisi, ada beberapa algoritma pengurutan yang baik semacam array sewenang-wenang ukuran n menggunakan sekitar n log2 n perbandingan. Di samping itu, tidak ada algoritma yang macam oleh perbandingan kunci (sebagai lawan, katakanlah, membandingkan kecil potongan kunci) dapat melakukan jauh lebih baik dari itu. Ada alasan untuk malu ini kekayaan algoritmik di tanah penyortiran. Meskipun beberapa algoritma yang memang lebih baik daripada yang lain, tidak ada algoritma yang akan menjadi solusi terbaik dalam segala situasi. Beberapa algoritma sederhana namun relatif lambat, sementara yang lain lebih cepat tetapi lebih kompleks; beberapa bekerja masukan baik secara acak memerintahkan, sementara yang lain lebih baik pada hampir-diurutkan daftar; beberapa hanya cocok untuk daftar yang berada di memori cepat, sementara yang lain dapat diadaptasi untuk menyortir file besar yang disimpan pada disk; dan seterusnya.

Dua sifat dari algoritma pengurutan layak algoritma mention.Asorting khusus disebut stabil jika mempertahankan urutan relatif dari dua elemen yang sama dalam input. Dengan kata lain, jika daftar masukan berisi dua elemen yang sama di posisi i dan j mana i <j, maka dalam daftar diurutkan mereka harus berada di posisi i dan j, masing-masing, seperti yang i < j. Properti ini dapat diinginkan jika, misalnya, kita memiliki daftar siswa diurutkan berdasarkan abjad dan kita ingin mengurutkan sesuai dengan mahasiswa IPK: algoritma yang stabil akan menghasilkan daftar di mana siswa dengan sama IPK masih akan diurutkan berdasarkan abjad. Secara umum, algoritma yang dapat Kunci pertukaran terletak berjauhan tidak stabil, tetapi mereka biasanya bekerja lebih cepat; kamu akan melihat bagaimana komentar umum ini berlaku untuk algoritma sorting yang penting nanti di dalam buku.

Fitur penting kedua algoritma sorting adalah jumlah tambahan  memori algoritma membutuhkan. Sebuah algoritma dikatakan di tempat jika tidak tidak memerlukan memori tambahan, kecuali, mungkin, untuk unit memori beberapa. Ada algoritma penyortiran penting yang di-tempat dan orang-orang yang tidak.

Mencari atau Searching

Masalah pencarian penawaran dengan menemukan nilai yang diberikan, disebut kunci pencarian, dalam diberikan set (atau multiset, yang memungkinkan beberapa elemen memiliki nilai yang sama).

Ada banyak mencari algoritma untuk memilih dari. Mulai dari langsung pencarian sekuensial ke biner spektakuler efisien tapi terbatas Cari dan algoritma berdasarkan mewakili set yang mendasari dalam bentuk yang berbeda lebih kondusif untuk mencari. Algoritma yang terakhir ini sangat penting

untuk aplikasi dunia nyata karena mereka sangat diperlukan untuk menyimpan dan mengambil informasi dari database besar. Untuk pencarian, juga, tidak ada algoritma tunggal yang cocok untuk semua situasi terbaik.

Beberapa algoritma bekerja lebih cepat daripada yang lain tapi memerlukan lebih banyak memori; beberapa sangat cepat tetapi berlaku hanya untuk array diurutkan; dan seterusnya. Berbeda dengan menyortir algoritma, tidak ada masalah stabilitas, tetapi isu-isu yang berbeda muncul. Secara khusus,

dalam aplikasi dimana data yang mendasarinya mungkin sering berubah relatif terhadap jumlah pencarian, pencarian harus dipertimbangkan dalam hubungannya dengan dua lainnya operasi: penambah dan penghapusan dari set data item. Sedemikian situasi, struktur data dan algoritma harus dipilih untuk keseimbangan antara persyaratan setiap operasi. Juga, mengatur set data yang sangat besar untuk mencari efisien menimbulkan tantangan khusus dengan implikasi penting untuk

aplikasi dunia nyata.

Pengolahan String atau String Processing

Dalam beberapa dekade terakhir, proliferasi cepat dari aplikasi berurusan dengan nonnumerical Data telah menggiatkan minat para peneliti dan praktisi komputasi di algoritma string penanganan. Sebuah string adalah rangkaian karakter dari alfabet. 

String kepentingan tertentu adalah string teks, yang terdiri huruf, angka, dan karakter spesial; bit string, yang terdiri nol dan satu; dan urutan gen, yang dapat dimodelkan oleh string karakter dari alfabet empat karakter {A, C, G, T}. Ini harus menunjukkan, bagaimanapun, bahwa algoritma pengolahan string memiliki pernah penting bagi ilmu komputer untuk waktu yang lama dalam hubungannya dengan komputer bahasa dan masalah kompilasi. Satu masalah-yang tertentu mencari kata tertentu dalam teks-memiliki menarik perhatian khusus dari para peneliti. Mereka menyebutnya string matching. Beberapa algoritma yang mengeksploitasi sifat khusus dari jenis pencarian telah diciptakan.

Masalah grafik atau Graph Problems

Salah satu daerah tertua dan paling menarik di Algorithmics adalah algoritma grafik. Secara informal, grafik dapat dianggap sebagai kumpulan titik yang disebut simpul, beberapa yang dihubungkan oleh segmen garis yang disebut tepi. (Definisi yang lebih formal diberikan dalam bagian berikutnya.) Grafik merupakan subjek yang menarik untuk belajar, baik teoritis dan praktis alasan. Grafik dapat digunakan untuk memodelkan berbagai aplikasi, termasuk transportasi, komunikasi, sosial dan ekonomi jaringan, penjadwalan proyek, dan games. Belajar yang berbeda teknis dan sosial aspek khususnya internet adalah salah satu daerah penelitian aktif saat ini melibatkan ilmuwan komputer, ekonom, dan ilmuwan sosial (lihat, misalnya, [Eas10]).

algoritma grafik dasar meliputi algoritma graph-traversal (bagaimana seseorang bisa mencapai semua titik dalam jaringan?), algoritma shortest-path (apa rute terbaik antara dua kota?), dan pemilahan topologi untuk grafik dengan tepi diarahkan (adalah satu set kursus dengan prasyarat mereka konsisten atau kontradiksi-diri?). Untung, algoritma ini dapat dianggap ilustrasi teknik desain umum; demikian, Anda akan menemukan mereka di sesuai bab dari buku ini. 

Beberapa masalah grafik adalah komputasi sangat sulit; paling terkenal contoh adalah masalah salesman bepergian dan masalah grafik-mewarnai. Masalah salesman keliling (TSP) adalah masalah menemukan tur terpendek melalui n kota yang dilihat setiap kota tepat satu kali. Selain aplikasi yang jelas melibatkan perencanaan rute, itu muncul dalam aplikasi modern seperti sirkuit fabrikasi papan dan chip yang VLSI, X-ray kristalografi, dan rekayasa genetika. 

Masalah grafik-mewarnai berusaha untuk menetapkan jumlah terkecil dari warna untuk simpul dari grafik sehingga tidak ada dua simpul yang berdekatan adalah warna yang sama. Ini Masalah muncul dalam beberapa aplikasi, seperti penjadwalan acara: jika peristiwa yang diwakili oleh simpul yang terhubung dengan sebuah sisi jika dan hanya jika sesuai Peristiwa tidak bisa dijadwalkan pada saat yang sama, solusi untuk pewarnaan graf masalah menghasilkan jadwal yang optimal.

Masalah Kombinatorial atau Combinatorial Problems

Dari perspektif yang lebih abstrak, masalah salesman bepergian dan graphcoloring yang Masalah adalah contoh dari masalah kombinatorial. Ini adalah masalah yang meminta, secara eksplisit atau implisit, untuk menemukan benda-seperti kombinatorial sebagai permutasi, kombinasi, atau bagian-yang memenuhi kendala tertentu. Sebuah diinginkan objek kombinatorial juga mungkin diperlukan untuk memiliki beberapa properti tambahan seperti sebagai nilai maksimum atau biaya minimum. kombinatorial Masalah Dari perspektif yang lebih abstrak, masalah salesman bepergian dan graphcoloring yang Masalah adalah contoh dari masalah kombinatorial. Ini adalah masalah yang meminta, secara eksplisit atau implisit, untuk menemukan benda-seperti kombinatorial sebagai permutasi, kombinasi, atau bagian-yang memenuhi kendala tertentu. Sebuah diinginkan objek kombinatorial juga mungkin diperlukan untuk memiliki beberapa properti tambahan seperti sebagai nilai maksimum atau biaya minimum.

Masalah geometris atau Geometric Problems

Algoritma geometrik berurusan dengan benda-benda geometris seperti titik, garis, dan poligon. Orang Yunani kuno yang sangat tertarik untuk mengembangkan prosedur (Mereka tidak menyebutnya algoritma, tentu saja) untuk memecahkan berbagai geometris masalah, termasuk masalah membangun sederhana geometris bentuk-segitiga, lingkaran, dan sebagainya-dengan penguasa ditandai dan kompas. Kemudian, untuk sekitar 2000 tahun, minat yang kuat dalam algoritma geometrik menghilang, akan dibangkitkan di usia komputer-tidak lebih penguasa dan kompas, hanya bit, byte, dan baik lama kecerdikan manusia. Tentu saja, saat ini orang yang tertarik dalam algoritma geometrik dengan aplikasi sangat berbeda dalam pikiran, seperti komputer grafis, robotika, dan

tomografi. 

Kami akan membahas algoritma untuk hanya dua masalah klasik komputasi geometri: masalah terdekat-pasangan dan masalah cembung-hull. Yang paling dekat-pair Masalah ini cukup jelas: diberikan n poin dalam pesawat, menemukan pasangan terdekat antara mereka. Masalah cembung-hull meminta untuk menemukan poligon cembung terkecil yang akan mencakup semua poin dari himpunan.

Masalah numerik atau Numerical Problems

masalah numerik, area khusus besar lain aplikasi, masalah yang melibatkan objek matematika alam terus menerus: memecahkan persamaan dan sistem persamaan, komputasi integral tertentu, mengevaluasi fungsi, dan sebagainya. Mayoritas masalah matematika tersebut dapat diselesaikan hanya sekitar. Kesulitan utama lain berasal dari kenyataan bahwa masalah tersebut biasanya membutuhkan memanipulasi bilangan real, yang dapat direpresentasikan dalam komputer hanya sekitar. Selain itu, sejumlah besar operasi aritmatika dilakukan pada nomor sekitar diwakili dapat menyebabkan akumulasi babak- stop error ke titik di mana secara drastis dapat mendistorsi output yang dihasilkan oleh tampaknya algoritma suara.

Banyak algoritma yang canggih telah dikembangkan selama bertahun-tahun dalam hal ini daerah, dan mereka terus memainkan peran penting dalam banyak ilmiah dan rekayasa aplikasi. Namun dalam 30 tahun terakhir atau lebih, industri komputasi telah bergeser fokusnya untuk aplikasi bisnis. Aplikasi baru membutuhkan terutama algoritma untuk penyimpanan informasi, pengambilan, transportasi melalui jaringan, dan presentasi kepada pengguna. Sebagai hasil dari perubahan revolusioner ini, analisis numerik telah kehilangan posisi yang sebelumnya mendominasi di kedua industri dan ilmu komputer program. Namun, penting bagi setiap orang melek komputer memiliki setidaknya Ide dasar tentang numerik algorithms.

sumber : Design & Analisis Algorithms [ Anany Levitin ]