Faizin, Risyanggi Azmi (2018) Pengembangan Algoritma Pencarian Non Interaktif untuk Penyelesaian Permasalahan Ulam dengan Kebohongan Jamak. Masters thesis, Institut Teknologi Sepuluh Nopember.
Preview |
Text
5116201052-Undergraduate Thesis.pdf - Accepted Version Download (4MB) | Preview |
Abstract
Pada permasalahan permainan klasik pencarian Ulam dan Rényi, penanya harus mengajukan beberapa pertanyaan iya dan tidak untuk mencari sebuah nilai dalam range pencarian yang sudah disepakati, namun penjawab diperbolehkan berbohong. Sudah ada solusi dari beberapa variasi pada permasalahan pencarian Ulam dan Rényi, yaitu pada jenis query antara rentang atau subset dan jumlah maksimal bohong antara satu, dua, tiga, dan seterusnya. Namun belum ada solusi yang sempurna untuk query yang non interaktif yaitu penjawab hanya boleh menjawab query penanya setelah penanya selesai menanyakan semua querynya. Belum ada penelitian yang menyelesaikan permasalahan ini. Pada paper ini akan dijelaskan solusi sempurna untuk permainan Ulam dan Rényi non interaktif dengan maksimal kebohongan jamak menggunakan kode biner dengan jarak Hamming. Hasil algoritma pada paper ini menunjukkan jumlah query yang jauh lebih sedikit dari algoritma umum repetisi biner dan hasil terbaik pada pengujian online ternama.
============================
On the classic Ulam and Rényi searching problem, the questioner has to ask some yes-no questions to find an unknown value within the agreed search space, but the answerer is allowed to lie. There are already solutions of some variations in the Ulam and Rényi searching problem, i.e. on the type of query between range or subset and the maximum number of lies between one, two, three, and so on. But there is no perfect solution for non-interactive queries which the answerer can only answer the questioner's query after the questioner has finished querying all the queries. No research has resolved this problem yet. In this paper we will describe the perfect solution for non-interactive Ulam and Rényi searching problem with many lies using binary code with Hamming distance. The algorithm results in this paper shows a much smaller number of queries than the common binary repetition algorithm and the best results on a reputable online judge.
| Item Type: | Thesis (Masters) |
|---|---|
| Uncontrolled Keywords: | permainan ulam, bohong, jarak hamming, kode biner, query |
| Subjects: | T Technology > T Technology (General) > T58.5 Information technology. IT--Auditing |
| Divisions: | Faculty of Information and Communication Technology > Informatics > 55101-(S2) Master Thesis |
| Depositing User: | Risyanggi Azmi Faizin |
| Date Deposited: | 09 Jul 2021 10:17 |
| Last Modified: | 09 Jul 2021 10:17 |
| URI: | http://repository.its.ac.id/id/eprint/57344 |
Actions (login required)
 |
View Item |