Hasil Pencarian  ::  Simpan CSV :: Kembali

"Graph clustering adalah pengelompokkan simpul-simpul pada suatu graf menjadi cluster-cluster. Ada berbagai macam algoritma graph clustering yang dapat diterapkan pada graf berbobot, di antaranya adalah algoritma yang berbasis MST (Minimum Spanning Tree). Kelebihan dari algoritma graph clustering yang berbasis MST adalah mampu mendeteksi bentuk cluster yang tidak beraturan. Algoritma graph clustering berbasis MST yang dibahas dalam penelitian ini adalah Maximum Standard Deviation Reduction atau disingkat MSDR. Algoritma tersebut bersifat unsupervised, yang artinya banyaknya cluster tidak ditetapkan oleh pengguna. MSDR memiliki dua tujuan. Tujuan yang pertama adalah membentuk cluster-cluster dimana pada masing-masing cluster, busur-busurnya memiliki nilai bobot yang serupa. Tujuan yang kedua adalah menjaga agar banyaknya cluster yang terbentuk, tidak terlalu banyak. Pada algoritma MSDR, tujuan yang kedua dipenuhi melalui suatu proses yang menggunakan regresi polinomial. Dalam penelitian ini, dilakukan modifikasi MSDR dengan menggantikan proses yang menggunakan regresi tersebut dengan suatu proses baru yang disebut "Loncatan Terbesar", sehingga dihasilkan algoritma baru yang disebut Modifikasi MSDR atau disingkat MMSDR. Dilakukan implementasi MMSDR pada beberapa graf lengkap Euclidean, yaitu graf lengkap yang setiap simpulnya adalah titik di suatu ruang Rn dan setiap busurnya diberi bobot yang berupa jarak Euclidean antara dua titik. Kemudian dilakukan implementasi MMSDR pada graf yang memodelkan rute penerbangan domestik di Indonesia oleh suatu maskapai X.

---

Graph clustering is the grouping of vertices in a graph into clusters. There are various clustering algorithms for weighted graphs, for example a graph clustering algorithm which is based on MST (minimum spanning tree). The advantage of MST-based clustering is that it allows the detection of clusters with irregular boundaries. An MST-based clustering known as MSDR (Maximum Standard Deviation Reduction) is studied in this research. MSDR is an unspervised clustering, in which the number of clusters is not dictated by the user. There are two goals of MSDR. The first goal is to produce clusters such that in each cluster the edges have similar weights. The second goal is to prevent the formation of too many clusters. In MSDR, the second goal is met through a process that uses polynomial regression. In this research, MSDR is modified by replacing the process that uses polynomial regression with a new process that is called "largest jump". A new algorithm is produced, which is called Modified MSDR (MMSDR). MMSDR is implemented on several complete Euclidean graphs, where a Euclidean graph is a graph whose vertices are points in a space Rn and the weight of an edge is the distance between the endpoints. MMSDR is also implemented on a graph that models domestic flight routes in Indonesia of an unidentified airline X. As a validation, MMSDR is tested on several Euclidean data, and the result is compared to visually-identified clusters. Afterwards, MMSDR is implemented on a graph that models the domestic flight routes of an airline in Indonesia."

"Pengklasteran clustering yang dilakukan dengan menggunakan metode graf disebut dengan pengklasteran graf graph clustering . Pengklasteran graf dengan memperhatikan bobot dapat diselesaikan dengan menggunakan pohon rentangan minimum. Salah satu algoritma yang dapat digunakan untuk menyelesaikan pengklasteran graf berbobot berdasarkan pohon rentangan minimum adalah algoritma maximum standard deviation reduction MSDR . Pada algoritma MSDR tidak perlu ditentukan banyaknya klaster yang terbentuk, karena terdapat perhitungan untuk menentukan banyak klaster secara otomatis. Namun dalam penelitian lanjutan algoritma MSDR cukup sulit dikerjakan karena sulitnya dalam menentukan nilai kandidat klaster terbaik, sehingga dilakukan modifikasi untuk menentukan nilai -nya. Modifikasi ini disebut dengan modifikasi MSDR MMSDR. Penelitian ini merupakan implementasi dari algoritma MMSDR pada masalah rute penerbangan di Indonesia yang disebut maskapai X, dengan menggunakan input matriks komplemen. Dengan menggunakan input matriks dari komplemen graf didapatkan pengklasteran berdasarkan jarak antar bandara. Penelitian ini juga menganalisis perubahan nilai epsilon dan perubahan matriks input. Hasil analisis menunjukkan bahwa perubahan nilai epsilon tidak mempengaruhi banyaknya klaster dan anggota klaster, sedangkan perubahan matriks input dapat mempengaruhi perbedaan anggota klaster.

---

Clustering is done by using graph method called graph clustering. Graph clustering with weights can be solved by using a minimum spanning tree. One of the algorithms that can be used to complete a weighted graph clustering based on a minimum spanning tree is the maximum standard deviation reduction MSDR algorithm. In the MSDR algorithm there is no need to determine the number of clusters that are formed, because there are calculaions to determine many clusters automically. However, in advanced research MSDR algorithm is quite difficult to do because of the difficulty in determining the value of best cluster candidates, so modifications are made to determine the value of. This modification is called the modification MSDR MMSDR. This research is an implementation of MMSDR algorithm on flight route problem in Indonesia called airline X, by using input complement matrix. Using the matrix input from the complement graph obtained clustering based on the distance between airports. This research also analyzed changes in epsilon value and changes in input matrix. The results of the analysis show that the change in epsilon value does not affect the number of clusters and clusters members, whereas the change in input matrix may affect the cluster members."

"Didefinisikan bahwa panjang sebuah basis dari ruang circuit pada sebuah graph adalah merupakan jumlah dan panjang semua circuit dalam basis tersebut. Sebuah algoritma untuk mencari circuit basis dengan kemungkinan panjang terpendek dalam 0 (mn2) operasi, dengan m banyaknya ruas dan n banyaknya simpul dikenal sebagai algoritma berwaktu polinomial. Waktu kompleksitas suatu algoritma menentukan cepat atau lambatnya proses menjalankan suatu algoritma. Algoritma yang dijelaskan dalain tulisan ini yang berhubungan dengan circuit basis minimum adalah algoritma Dijkstra, Quicksort dan Greedy serta dibahas juga tentang analisis waktu kompleksitas masing-masing algoritima tersebut."

"Pencacahan clique maksimal adalah suatu metode graph clustering yang bertujuan untuk mencari simpul mana saja yang memiliki peranan paling besar dalam suatu graf. Pencacahan clique maksimal ini telah banyak diaplikasikan, diantaranya analisis pada jaringan sosial, pendeteksian hierarki melalui jaringan email, analisis statistik jaringan finansial, clustering pada jaringan dinamis, dan komputasi biologi. Algoritma Bron-Kerbosch merupakan salah satu algoritma tercepat dalam pencarian clique maksimal, maka pada penelitian ini, digunakanlah algoritma Bron-Kerbosch. Dalam mencacah semua clique maksimal dari suatu graf, matriks yang biasa digunakan adalah matriks ketetanggaan dari graf tersebut, sehingga dapat diperoleh simpul mana saja pada graf yang memiliki peranan paling besar. Selain matriks ketetanggaan, penelitian ini juga menggunakan matriks komplemen dalam mencacah clique maksimal. Data yang digunakan dalam penelitian ini adalah graf yang merepresentasikan rute jalur penerbangan domestik dari salah satu maskapai penerbangan di Indonesia. Dengan menerapkan algoritma Bron-Kerbosch, semua clique maksimal dari graf terkait akan didaftar, sehingga dapat diperoleh simpul yang memiliki peranan paling besar dalam graf ini. Graf tersebut direpresentasikan dalam bentuk matriks ketetanggaan dan juga matriks komplemen. Hasil penerapan algoritma Bron-Kerbosch pada data, baik yang menggunakan matriks ketetanggaan maupun matriks komplemen, keduanya memberikan hasil yang sama dalam menentukan simpul yang memiliki peranan paling besar dari graf terkait. Selain itu, melalui hasil penerapan yang menggunakan matriks komplemen, dapat diketahui pula simpul-simpul yang hanya bertetangga langsung dengan simpul yang memiliki peranan paling besar.

---

Maximal clique enumeration is a graph clustering method for finding all vertices that have the most influence in a graph. This maximal clique enumeration has largely been applied, including social network analysis, hierarchy detection through email networks, statistical analysis of financial networks, clustering in dynamic networks, and computational biology. The Bron-Kerbosch algorithm is one of the fastest algorithms to find all maximal cliques, hence this research will focus on that algorithm to find all maximal cliques. Counting all maximal cliques of a graph usually uses an adjacency matrix of the graph to find all vertices in the graph that have the most influence. Other than adjacency matrix, this research will also use a complement matrix in counting all maximal cliques. This research uses a graph that represents a domestic flight route of one of the airlines in Indonesia. By using Bron-Kerbosch algorithm, all maximal cliques of the graph will be listed, so that it will come up with the vertices which are the most influential in this graph. The graph will be represented in an adjacency matrix as well as a complement matrix. The result of applying the Bron-Kerbosch algorithm both the adjacency and the complement matrix?will give the same result in determining vertices that have the most influence in the graph. Besides that, by using a complement matrix, the result gives more information on the vertices which are only connected to the vertices that have the most influence."

"Tugas akhir ini membahas 2 algoritma untuk menentukan himpunan bebas maksimum pada graph busur sirkular. Algoritma tersebut adalab algoritma dari LEUNG dan algoritma dari MASUDA NAKAJIMA. Kemudian dilakukan perbandingan pada kedua algonitma tersebut untuk menentukan algoritma yang terbaik ditinjau dari sudut kompleksitas waktu."

"University Course Timetabling Problem merupakan proses penjadwalan mata kuliah di sebuah universitas yang hasilnya diusahakan seoptimal mungkin untuk tidak saling berbenturan dengan batasan-batasan dan syarat-syarat (constraints) tertentu. Dalam menentukan penjadwalan berbasis perhitungan, salah satu metode yang dapat digunakan adalah Graph Coloring. Graph Coloring merupakan merupakan metode yang paling sederhana dan dapat digunakan untuk menentukan penjadwalan yang memiliki berbagai macam constraints. Pada penelitian ini, peneliti mengusulkan pengembangan dari metode Graph Coloring yang ada untuk membuat penjadwalan mata kuliah yang optimal dengan memertimbangkan berbagai macam constraints. Pengembangan ini diujicobakan ke penjadwalan mata kuliah di Fakultas Teknologi Informasi Universitas Tarumanagara (FTI Untar). Hasil percobaan menunjukkan bahwa pengembangan metode Graph Coloring memberikan hasil penjadwalan yang memenuhi rata-rata 93% seluruh constraints yang ditentukan. Rata-rata 7% pelanggaran constraints dikarenakan keterbatasan jumlah ruang dan total slot waktu kuliah, serta permintaan jadwal tertentu oleh dosen."

"Kebutuhan untuk mendapatkan pola yang terbentuk dari matriks biner pada masa ini dan mendatang, meningkat dengan pesat. Data dari 'clickstream' pengguna internet, 'face-recognition', matriks setelah dilakukan prapengolahan dari data kategorik, interaksi protein-protein dan masih banyak daftar lainnya yang menghasilkan matriks biner. Salah satu pola yang dapat dibentuk dari matriks biner merupakan satu himpunan submatriks yang semua entrinya bernilai 1. Submatrik tersebut disebut dengan 'bicluste''r' dengan jenis nilai konstan. Permasalahan dari pembentukan 'bicluster' disebut dengan 'biclustering'. Permasalahan tersebut tergolong dalam permasalahan 'NP-complete'. Meskipun demikian, hasil yang suboptimal mampu didapatkan dengan membuat algoritma 'biclustering'.Penelitian ini mengusulkan suatu algoritma 'biclustering' baru dengan menggunakan jarak 'Hamming' antara satu kolom dengan kolom yang lainnya pada matriks biner. Algoritma yang diberi nama 'bicHPT' ('biclustering based on Hamming distance Pattern Table') ini, mampu membuat satu himpunan 'bicluster' dengan lima langkah, yaitu mereduksi kolom matriks, membuat tabel jarak 'Hamming', mencari kandidat 'bicluster', menyaring kandidat 'bicluster', dan membentuk 'bicluster'. Setelah uji coba performa, algoritma 'bicHPT' mampu menghasilkan satu himpunan 'bicluster', bahkan mampu mengungguli algoritma lain dalam hal jumlah 'bicluster' yang dibentuk. Algoritma ini juga mampu untuk diaplikasikan sebagai salah satu unsur yang digunakan untuk memprediksi interaksi protein-protein baru, antara protein 'Human Immunodeficiency Virus type' 1 (HIV-1) dan protein manusia. Total interaksi baru yang didapatkan dengan menggunakan algoritma ini ada sebanyak 482 interaksi.

---

The demand to obtain patterns from a binary matrix today and in the future is rapidly increasing. Data from internet users clickstreams, face-recognition, the matrix after preprocessing categorical data, protein-protein interactions, and so on that will produce a binary matrix. One kind of pattern that might be obtained from a binary matrix is a set of submatrices which all their entries have the value of 1. A submatrix is called with bicluster with constant values. The problem to make biclusters is called with biclustering. This problem is NP-complete. Although, the suboptimal solution might be obtained with constructing a biclustering algorithm.

This research proposes a novel biclustering algorithm based on Hamming distance among each column in a binary matrix. The algorithm which called with \pt (biclustering based on Hamming distance Pattern Table) can produce biclusters in 5 steps, which are, the column reduction of the matrix, constructing Hamming distance table, finding bicluster candidate, filtering bicluster candidate and forming the biclusters. After testing the performance, this algorithm can produce biclusters. Moreover, it can outperform another algorithm in numbers of biclusters. This algorithm is also succeeded to be applied as one of the elements to predict protein-protein interaction between Human Immunodeficiency Virus type 1 protein (HIV-1) and human protein. The total new interactions which using this algorithm are 482 interaction."

"Dalam tuqas akhir ini dibahas mengenai pemodelan masalah perhitungan pesanan materi iklan yang masuk pada suatu biro iklan agar didapat sejumlah maksimum materi yang siap pakai, sesuai kapasitas yang ada. Algoritma yang digunakan adalah algoritma maksimum Low minimum cut yang disesuaikan agar dapat menyelesaikan masalah lalu lintas kerja dalam pembuatan materi ikian ini."

"Pada mode infrastruktur, ketika setiap kali node wired dan node wireless hendak mengirimkan paket data ke node wireless lainnya, data harus dulu dikirimkan ke access point (AP). Kemudian access point (AP) akan memforward paket data ke node coresponden. Oleh karena itu AP adalah tempat yang bagus untuk menambahkan mekanisme FEC untuk improve delivery video yang berkualitas. Jumlah redundant data yang ada pada mekanisme FEC statis adalah tetap. Dalam Mekanisme EAFEC redundant data ditentukan oleh access point (AP) berdasarkan beban traffic jaringan dan wireless channel state. Algoritma EAFEC menentukan berapa jumlah paket redundant yang harus di-generate berdasarkan panjang antrian yang mengindikasikan beban traffic jaringan dan times retransmisi paket yang mengindikasikan wireless channel state. Layanan video streaming tidak pernah lepas dari throughput, delay, jitter dan packet loss. Pada penelitian ini penulis membangun simulasi optimalisasi streaming video pada jaringan wireless. Penulis juga melakukan studi literatur dalam merancang simulasi ini. Dalam membangun simulasi penulis menggunakan aplikasi NS2 (network simulator) versi 2.28 yang berjalan diatas sistem operasi Microsoft Windows Xp Sp2 dengan aplikasi Cygwin. Hasil output akhir pada NS-2 divisualisasikan berupa grafik dan tabel yang kemudian dianalisa lebih lanjut yaitu berupa pengukuran throughput, delay, jitter, packet error dan dengan menggunakan script AWK beserta beberapa tambahan modifikasinya. Dari thesis ini diperoleh performance dari penggunaan mekanisme EAFEC dapat mengurangi kemacetan pada jaringan (congestion) sehingga berdampak pula berkurangnya jumlah packet loss.

---

In the infrastructure mode, when a wired and wireless node wants to send data packets to other wireless nodes, data must first be sent to the Access Point (AP). The AP then forwards packets to the corresponding node. Therefore, AP is a good place for adding the FEC mechanism for improving video delivery quality. The number of redundant FEC data in a fixed number.

EAFEC redundant data is determined by AP which is based on both network traffic load and wireless channel state. EAFEC Algorithm determines number FEC redundant generated based on queue length indicating network traffic load and packet retransmisi times indicating wireless channel state. Streaming video services are usually related to throughput, delay, jitter and packet loss.

In this thesis, the author develops a simulation study of streaming video service on wireless network. The research method is performed studying and developing simulation using Network simulator (NS-2) application version 2.28. The application running at Microsoft Windows Xp SP2 operating sistem, with CYGWIN aplication.

The result of simulation are graphics and measurement such us throughput, delay, jitter and packet error. The measurements are conducted using AWK script with some modifications. From this thesis obtained performance usage of mechanism EAFEC can lessen traffic jam on network ( congestion ) also causing affects the lessen amounts of packet loss."