Hasil Pencarian  ::  Simpan CSV :: Kembali

Abstrak :
Tesis ini membahas algoritma mengenal graf pariti G=(V,E) dan mencari klik terbesarnya, serta implementasinya pada pseudo_code yang diuraikan pada bahasa pemrograman C versi Turbo C. Algoritma ini merupakan algoritma sekuensial yang mengacu pada algoritma paralel 0(log2n) pada n /1og2n prosesor dari [PRZ91]. Langkah pertama dari algoritma mengenal graf pariti adalah memilih sembarang verteks u E V sedemikian sehingga bentuk graf G diubah nenjadi himpunan subgraf level per level, dengan u sebagai verteks tunggal di level ke 0. Kemudian langkah berikutnya, hubungan verteks-verteks antar level dibuktikan keparitiannya berdasarkan sifat-sifat graf pariti [PR291]. Sedangkan langkah pertama dari algoritma meneari klik terbesar pada graf pariti adalah membentuk himpunan subgraf yang dibangun dari gabungan komponen di level ke i dengan tetangganya di level ke i-1. Kemudian langkah berikutnya, penentuan klik terbesar dapat dicari dari setiap subgraf tersebut [PRZ91). Hasil pengamatan pada banyaknya iterasi (langkah) dari basil eksekusi program pada 10 sampai dengan 70 verteks untuk 15 bentuk graf, diperoleh kesimpulan bahwa pemilihan verteks u untuk level ke 0 mempengaruhi jumlah iterasi, dan semakin besar jumlah komponen yang terjadi dalam pembuktian keparitian graf semakin besar pula jumlah iterasi yang diperoleh. Hasil pengamatan menunjukkan jumlah iterasi terbesar terjadi pada graf bipartisi lengkap dengan bentuk = level ke 1 berisi n-1- |n/3| verteks, level ke 2 benisi. 1n/31 verteks dan gabungan subgraf level ke 1 dan 2 merupakan bipartisi lengkap (n=|V|). Dengan mengasumsikan bahwa jumlah operasi pada setiap iterasi adalah konstan, maka implementasi algoritma menunjukkan kompleksitas 0(n4).

Abstrak :
ABSTRAK
Traveling Salesperson Problem (TSP) merupakan masalah optimasi kombinatorial klasik. Semua algoritme konvensional yang dikenal saat ini untuk pemecahan TSP, membutuhkan usaha komputasi yang meningkat secara eksponensial terhadap jumlah kota.
Dalam tulisan ini dibahas jaringan neural Hopfield dengan masukan kontinyu sebagai alternatif pemecahan TSP. Jaringan neural ini memecahkan TSP dengan kompleksitas komputasi sebanding dengan polinomial pangkat 4 dari jumlah kota. Komputasi jaringan neural ini efektif, karena adanya tanggapan analog non-linier dari neuron dan koriektifitas yang besar di antara neuron. Metode ini hanya membertkan penyelesaian minimum lokal, yang diharapkan mendekati minimum global. Implementasi jaringan neural ini disimulasikan pada komputer sekuensial. Komputer yang digunakan berupa workstation SUN SPARC 1+ berbasis UNIX dengan kapasitas memori 8 Mb. Kinerja metode jaringan neural Hopfield dievaluasi berdasarkan jarak tour dan waktu yang dibutuhkan. Kemudian hasilnya dibandingkan dengan penyelesaian optimal yang diperoleh dengan algoritme konvensional Least Cost Branch anc' Bound (LCBB).
Dari hasil eksekusi program pada workstation SUN SPARC 1+ berbasis UNIX untuk jumlah kota 15 s/d 22 buah diperoleh jarak tour rata-rata dengan metode jaringan neural berkisar antara 1,63 s/d 2,06 kali jarak tour dengan algoritme LCBB. Waktu rata-rata yang dibutuhkan jaringan neural (jumlah kota 15 s/d 22 buah) sebesar 4 x 10-4 sampai dengan 4 x 10-1 kali waktu yang dibutuhkan algoritme LCBB. Pada jumlah kota 5 s/d 14 buah, hasil dari jaringan neural kurang bagus dibandingkan dengan basil dari algoritme LCBB. Jarak tour rata-rata dengan jaringan neural Hopfield berkisar antara 1.01 s/d 1.45 kali jarak tour dengan algoritme LCBB, tetapi waktu yang dibutuhkan jaringan neural Hopfield sebesar 1 s/d 10 kali waktu yang dibutuhkan algoritme LCBB.

Abstrak :
Pada tulisan ini disusun suatu algoritma sebagai pengembangan dari algoritma yang sudah ada yaitu algoritma Quine-McCluskey untuk membantu meminimalkan fungsi Boole dalam bentuk sum of product. Algoritma ini berguna dalam perancangan rangkaian logika kombinasi terutama PLA (Programmable Logic Array) sehingga diperoleh rangkaian berbiaya rendah. Dalam rangkaian logika kombinasi, fungsinya secara eksplisit dinyatakan dalam fungsi Boole. Untuk meminimalkan fungsi Boole ini sudah dikenal beberapa metode antara lain metode Peta Karnaugh, metode tabulasi (HILLBI), metode MINI (ARE78) dan metode ESPRESSO (BRAY84) Pada metode tabulasi diperlukan tiga tahap untuk meminimalkan fungsi Boole, yaitu pencarian PI (Prime Implicant), pencarian EPI (Essential Prime Impicant) dan pemilihan NON-EPI. Algoritma Quine-McCluskey hanya melaksanakan tahap pertama yaitu pencarian Prime Implicant. Dengan menelusuri ide dasar penyusunan algoritma Quine-McCluskey, yaitu teori kubus, dan dengan menentuan suatu relasi partial ordering di himpunan C=(O,1,X) yang menjadikan (C,>-) sebuah lattice, maka dengan menggunakan sifat lattice tersebut dapat disusun aturan-aturan tertentu sehingga dapat dibuat algoritma yang lebih sederhana dari pada algoritma Quine-McCLuskey. Di samping itu, algoritma ini melaksanakan tahap pertama dan tahap kedua dari metode tabulasi sehingga selain menghasilkan Prime Implicant sekaligus juga menghasilkan Essential Prime Implicant, meskipun algoritma modifikasi ini memiliki kompleksitas waktu dan space yang sama dengan algoritma Quine-McCluskey yaitu O(n3) dan O(n).