problem solution : introduction to algoritm 15-2 &15-6

15-2 Neatly Printing
Input text yang akan diprint adalah sejumlah n words/kata-kata dengan panjang setiap kata adalah l1,l2…, ln karakter. Paragraph yang yang terdiri dari words akan diprint dengan rapi dalam sejumlah baris dengan memuat M karakter maksimum setiap baris.
Kriteria hasil print yang rapi adalah: Jika sebuah baris terdiri dari words I sampai j dimana I <= j dan terdapat sebuah space/spasi antar words, jumlah extra space karakter pada akhir baris adalah

Step 1. Struktur pembentukan print yang rapi.
Kita asumsikan bahwa kita mengetahui baris terakhir mulai dari kata i sampai kata j. Sehingga baris sebelumnya akan memuat kata 1,…,i-1.
Misalkan c[j] adalah cost dari susunan optimal dari kata 1,…,j. Jika kita mengetahui baris terakhir memuat kata I,…,j maka Jika kita menghitung c[1], maka kita membutuhkan c[0]. Jika c[0] = 0 maka c[1]=lc[1,1].
Untuk mendapatkan kata mana yang akan dibentuk pada sebuah line, kita dapat membuat parallel p yang menunjukkan masing-masing asal/sumber nilai cost(c). Ketika c[j] dihitung, jika c[j] sesuai dengan nilai c[k-1], set p[j] = k. Selanjutnya setelah c[n] dihitung, kita dapat menemukan pointer dimana untuk break/pemutusan baris. Baris akhir dimulai dari kata[n] sampai kata n. Baris sebelumnya dimulai dari p[p[n]] sampai kata p[n]-1, demikian selanjutnya
Step 2. Solusi Rekursif.
Kita perlu mengetahui kata mana yang memulai baris akhir untuk subproblem dari kata 1,…,j. Oleh karena itu kita mencoba semua kemungkinan untuk kata i, dan kita pilih satu yang memberikan cost paling rendah. Disini i disusun dari 1 sampai j. Jadi, kita dapat mendefinisikan c[j] secara rekursif dari:

Ketentuan untuk lc
• Semua pilihan yang dibuat akan dapat disusun dalam line(karena susunan dengan tidak dapa dipilih sebagai minimum)
• Cost dalam menempatkan kata i,…,j pada baris terakhir tidak akan 0 kecuali jika baris terakhir pada paragraph (j = n) atau kata i…j akan diisi oleh baris yang sudah ada.

Kita dapat menghitung nilai c dari kiri kekanan karena setiap nilai tergantung pada nilai sebelumnya.

15-6 Checkboard Problem
Terdapat sebuah papan yang berukuran n x n dan sebuah bidak diletakkan pada pojok bawah pada papan. Tujuan dari permainan ini adalah bagaimana memindahkan bidak dari ujung papan bawah ke ujung papan atas dan tiap perpindahan bidak pemain akan mendapatkan uang. Pemain diharapkan akan memperoleh uang sebanyak-banyaknya dari perpindahan bidak.


Aturan berpindah:
1. bidak hanya dapat berpindah satu kotak diatasnya.
2. Bidak dapat berpindah satu kotak keatas dan satu kotak ke kiri.
3. Bidak dapat berpindah satu kotak keatas dan satu kotak ke kanan.

Step 1. Struktur perjalanan bidak.
Dimisalkan baris papan dilambangkan dengan A dan kolom dilambangkan dengan B . pada akhir perjalanan, bidak akan menempati kotak (A,B) dan sebelum tiba pada kotak (A,B), bidak akan melewati kotak (A’,B-1) dengan A’ = A-1 atau A atau A+1. Jika perjalanan dari (A’,B-1) menuju (A,B) kita mendapatkan uang sebanyak p ((A’,B-1), (A,B)) dollar dan perjalan dari titik (A’,B-1) dati titik sebelumnya sebanyak d dollar, maka jumlah uang yang dikumpulkan dari perjalanan titik awal sampai perjalanan titik akhir sebanyak d+ p ((A’,B-1), (A,B)) dollar

Step 2. Solusi Rekursif.
Untuk mendapatkan uang terbanyak untuk sampai ke (A,B) maka harus dicari juga jalan yang paling menguntungkan untuk sampai ke (A+1, B-1), (A+1, B), dan (A +1, B +1) .
Dari persamaan untuk mendapatkan nilai uang terbesar ke titik akhir pada step 1, dapat dicari bahwa untuk mendapatkan nilai uang terbanyak untuk sampai ke titik (A,B) atau d(A,B) adalah dengan melewati ketiga jalur di bawah ini :




Artikel ini seharusnya mengandung beberapa gambar yang menerangkan persoalan dan rumus-rumus yang berbentuk gambar. untuk lebih lengkapnya silahkan mengirimkan email permintaan file lengkap dalam bentuk microsoft word document ke penulis insya allah akan di balas max dalam 2 hari.

Blu-Ray

media penyimpanan digital telah berkembang secara pesat. setelah kita meninggalkan er CD kini kita berada pada ujung era penyimpanan data dengan menggunakan DVD. pada masi sekarang ini CD sudah mulai ditinggalkan karena sudah tidak mencukupi kebutuhan dalam pnyimpanan data. pengguna teknologi pada hari ini cenderung menyimpan data dengan kapasitas ukuran sampai diatas 1 GB (Giga Byte). dengan adanya DVD maka kebutuhan penyimpanan data masyarakat saat ini tercukupi. namun kepuasan manusia tidak ada batasnya. tidak puas dengan tersedianya media sebesar 4,5 GB, kini muncul media penyimpanan berupa disk yang bisa memuat data sampai 50 GB. eduuuuuun.. hampir mengejar kapasitas penyimpanan harddisk. walaupun kita tidak kaget lagi mendengar harddisk dengan kapasitas 1 TB (Terra Byte).

Blu-ray, nama "piringan-cakram" yang sedang kita bicarakan ini. dibuat oleh Blu-Ray Disk Assosiation, sebuah grup yang merepresentasikan konsumen barang-barang eletronik, hardware komputer, dan produsen film. agustus 2008 tepatnya tanggal 27,sebanyak 780 Blu-ray telah di rilis di negaranya paris hilton (USA) dan 480 buah di negaranya maria ozawa (jepang). sampaisekarang (akhir tahun 2008), 1220 buah Blu-ray diedarkan di USA.

nama blue ray berasal dari blue laser (walaupun warnanya violet), lase ini digunakan untuk membaca dan menulis pada disk jenis ini. karena memiliki panjang gelombang yang pendek (405 nm), konsekuensinya adalah laser ini dapat menuliskan data lebih banyak dibandingkan pada DVD biasa yang menggunakan laser dengan -panjang gelombang lebih besar (650 nm). sebuah blu-ray dual layer dapat menampung 50GB data hampir 2 kali lebih besar pada dual layer DVD.

panjang gelombang yang relatif pendek memungkinkan blu-ray untuk memuat informasi lebih banyak pada media yang sama lebarnya dengan keping CD atau DVD. nilai minimal ukuran titik dimana laser dapat difokuskan terbatas karena adanya "diffraction", bergantung pada panjang gelombang cahaya, dan besarnya lubang pada lensa yang digunakan untuk memfokuskan pada titik pada disk. dengan mamendekkan panjang gelombang, menaikkan nilai lubang lensa dar 0.6 ke 0.85, dan menipiskan lapisan cover untuk mengurangi rsiko terjadinya efek optik, sinar laser dapat fokus pada lobang yang lebih kecil. hal ini yang memungkinkan memasukkan lebih banyak informasi pada area yang sama. pada blu-ray ukuran lubang pada disk rata-rata sebesar 580 nm. sebagai tambahan untuk peningkatan optik, disk blu-ray memiliki peningkatan fitur pada data encoding yang akan jauh meningkatkan kapasitas disk.

karena lapisan data berada sangat dengan dengan lapisan terluarnya, maka disk blu-ray sangat rentan terhadap goresan. untuk mengatasi hal tersebut, dibuatlah lapisan pelindung yang kebal goresan. beberapa perusahaan mengembangkan lapisan ini dan menamainya sesuai dengan kesukaan masing-masing. TDK menyebut hasil buatannya dengan Durabis. sedangkan verbatim memberi nama hasil buatannya dengan ScratchGuard.

dari semua itu ada yang lebih mengejutkan lagi, sebuah disk dengan kapasitas 10 TB (Terra Byte). BusseeeeeT....!!.

Fluorescent Multilayer Disc (FM Disc) itu nama disk yang lebih hebat dari blu-ray. FM Disc sendiri merupakan perkembangan atas penemuan seorang kimiawan Rusia beberapa waktu sebelumnya. yaitu sebuah bahan organis yang bernama “stable photocrome”, sebuah bahan bila terkena sinar laser dapat memancarkan cahaya Fluoroscent.

Salah satu perbedaan mendasar adalah bila CD dan DVD permukaannya tergores, data akan sulit dibaca, sedangkan pada FM Disc hal tersebut tidak terjadi. Isinya akan tetap terbaca meskipun permukaannya tergores atau kotor. Karena sifat cahaya pada FM Disc bersifat incoherent berbeda dengan CD dan DVD yang bersifat coherent.

Dari segi bentuk, FM Disc memiliki bentuk seukuran dengan CD, DVD, dan Blue Ray Disc (BSD) tetapi transparan, tidak terdapat lapisan mengkilap seperi generasi sebelumnya. FM Disc memiliki lebih banyak layer, yaitu untuk kapasitas 50 GB diperlukan 12 layer dengan kecepatan akses yang sangat cepat mencapai 1 GB/s.

Untuk tahap awal, teknologi FM Disc masih menggunakan laser merah yang hanya mampu menampung sekitar 140 GB data. Dan untuk tahap berikutnya akan menggunakan laser biru dengan panjang gelombang 480 nm, dengan kapasitas mencapai 10 TB (Tera Byte). Sungguh merupakan kapasitas yang sangat luar biasa besar.

NB: yang FM Disk langsung copy paste ga pake edit, capek nulisnya..

artikel pertama

Whalah..!!
siip tenan