Hasil Pencarian  ::  Simpan CSV :: Kembali

"Untuk sebarang bilangan bulat positif 𝑎≥2 dan 𝑛≥1 yang diberikan, dapat di-lakukan konstruksi graf de Bruijn yang didefinisikan sebagai graf berarah dengan banyaknya simpul 𝑎𝑛−1, panjang label simpulnya 𝑛−1, banyaknya busur berarah 𝑎𝑛, dan panjang label busurnya 𝑛. Karena setiap graf de Bruijn merupakan graf Euler maka dapat ditentukan sirkuit Euler dengan label minimal. Barisan de Bruijn yang dibangun oleh 𝑛 dinyatakan oleh Sirkuit Euler dengan label minimal. Graf de Bruijn tidak mudah dikonstruksi untuk 𝑛 yang berukuran besar, kesulitan selanjutnya dijumpai pada penentuan sirkuit Euler dengan label minimal. Oleh karena itu, pada tesis ini akan diberikan metode alternatif sebagai solusi konstruk-si barisan de Bruijn dengan menggunakan teorema Fredicksen dan Maiorana. Teo-rema ini menjamin keberadaan barisan de Bruijn untuk setiap 𝑛 yang diberikan dengan merangkai Lyndon word yang terurut secara Lexicographic. Hasil kajian ini memberikan kontribusi terhadap langkah-langkah untuk merangkai sebarang Lyndon word dari suatu alfabet 𝐴 dengan panjang 𝑛, sehingga diperoleh barisan de Bruijn yang dibangun oleh 𝑛. Sebagai akhir pembahasan akan diberikan kaitan antara graf de Bruijn dan barisan de Bruijn.

---

Given any integer 𝑎≥2 and 𝑛≥1, de Bruijn graph can be constructed. De Bruijn graph is a digraph with 𝑎𝑛−1 vertices, each has 𝑛−1 length label, and 𝑎𝑛 arc, each has 𝑛 length label. Since each of de Bruijn graph is an Eulerian graph, then we can find an Eulerian circuit with minimal label. De Bruijn sequence which is spanned by 𝑛 can be representated by Eulerian circuit with minimal la-bel. It is not easy to construct de Bruijn graph for 𝑛 large, it is implied difficulties to find Eulerian circuit with minimal label. In this ?thesis? will be presented alter-native method on how to construct de Bruijn sequence using Fredicksen and Mai-orana Theorem. This theorem guarantees the existence of de Bruijn sequence for any given 𝑛 using concatenation Lexicographic ordered of Lyndon word. The re-search result has contributed on construct step by step to obtain concatenation any Lyndon word of length 𝑛 of alphabet 𝐴, so we obtain de Bruijn sequence span by 𝑛. For conclusi, will be given correlations between de Bruijn graph and de Bruijn sequences."

"Untuk sebarang bUntuk sebarang bilangan bulat positif k ≥ 2 dan n ≥ 1 yang diberikan, dapat dilakukan konstruksi barisan de Bruijn dengan panjang barisan 2n dari suatu alfabet A dengan panjang k. Pada tesis ini akan diberikan 3 buah metode untuk mengkonstruksi barisan de Bruijn. Metode pertama adalah metode Tabel. Metode ini menggunakan elemen An, yaitu string dengan panjang n yang dibangkitkan dari alfabet A, kemudian dicari semua kemungkinan urutan yang dapat terjadi. Metode kedua adalah metode Martin. Metode ini menggunakan algoritma M, langkahnya dengan cara selalu menambahkan simbol terbesar yang mungkin sedemikian sehingga n-barisan baru belum pernah muncul sebelumnya. Metode terakhir adalah metode Fredricksen ? Maiorana. Metode ini menggunakan teorema Fredricksen ? Maiorana yang menjamin keberadaan barisan de Bruijn untuk setiap n yang diberikan dengan merangkai Lyndon word yang terurut secara Lexicographic. Sebagai akhir pembahasan akan diberikan kaitan serta waktu proses antara masing-masing metode konstruksi barisan de Bruijn.

---

Given any integer k ≥ 2 dan n ≥ 1, de Bruijn sequence with length 2n can be constructed from alfabet A length k. In this ?thesis? will be presented three method on how to cons-tructed de Bruijn sequences. The first method is Table method. This method using element of An, which is string with length n spanned by alfabet A and then find all of possibility order that can be happen. The second is Martin method. This method using M algorithm, which is always add the largest symbol such that the resulting new sequences has not appeared previously. The last method is Fredicksen ? Maiorana?s method. This method using Fredicksen ? Maiorana's theorm that guarantees the existence of de Bruijn sequen-ce for any given n using concatenation Lexicographic ordered of Lyndon word. For conclusi, will be given correlations and time process between each method on constructed de Bruijn sequences."

"The plumage industry, the role of Antonie Augustus Bruijn, 1842-1890 and the start of world wide bird protectionAntonie Augustus Bruijn, 1842-1890, his family and life as a marine officer in the Dutch NavyRetired Antonie Augustus Bruijn, 1842-1890, his family life in Ternate observed and written by Alfred Russel Wallace and Achille RaffrayHistory of Ternate and Tidore."