Please use this identifier to cite or link to this item: http://repository.ipb.ac.id/handle/123456789/135604
Title: Algoritma paralel efisien untuk pemrograman dinamis
Authors: Nurdiati, Sri
Bukhari, Fahren
Margaret, Nora
Issue Date: 1998
Publisher: IPB University
Abstract: Pemrograman dinamis merupakan salah satu teknik optimasi yang digunakan untuk menyelesaikan masalah kombinatorial bertahap ganda (multistage), melibatkan banyak perhitungan dalam penyelesaian masalahnya dengan menggunakan komputer serial. Untuk itu, sejumlah penelitian telah dilakukan guna peningkatan kecepatan waktu eksekusi dalam menyelesaikan masalah tersebut pada komputer paralel, seperti kerangka pemikiran yang diusulkan oleh Antonio, Tsai dan Huang (1991), yaitu memparalelkan pemrograman dinamis untuk menyelesaikan masalah- masalah multistage. Hanya saja pendekatan pemrograman dinamis yang diusulkan tersebut dibatasi untuk beberapa masalah saja. Untuk banyak masalah menarik lainnya, misalkan masalah urutan penggandaan matriks (The Matrix Chain Multiplication Problem) dan masalah pengoptimalan triangulasi poligon (Optimal Polygon Triangulation Problem), pendekatan Antonio, Tsai dan Huang tidak bisa digunakan. D. Tang dan G. Gupta (1995) mencoba mengatasi masalah tersebut dengan memperkenalkan suatu teknik dalam memparalelkan pemrograman dinamis melalui perancangan algoritma paralel untuk menyelesaikan masalah urutan penggandaan matriks. Proses paralelisasi dalam merancang algoritma paralel didasarkan pada algoritma sekuensial yang memiliki waktu kompleksitas (n³). Jumlah processor yang digunakan adalah (n(n+1))/2, termasuk dalam kelas (n²). Dalam proses paralelisasi yang terjadi, dapat dibuktikan bahwa algoritma paralel yang dirancang untuk dicobakan pada komputer paralel PRAM memiliki kompleksitas (n) dan merupakan algoritma paralel yang efisien.
URI: http://repository.ipb.ac.id/handle/123456789/135604
Appears in Collections:UT - Mathematics

Files in This Item:
File SizeFormat 
G98NMA.pdf
  Restricted Access
4.84 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.