Algoritma round robin

Implementasi Algoritma Round-robin Schedule Sederhana


Round-robin Schedule Algorithm merupakan algoritma yang digunakan untuk membuat sebuah jadwal pertandingan yang digunakan oleh Round-robin tournament seperti salah satunya adalah FIFA World Cup. Dengan algoritma ini, partisipan pertandingan akan dibagi lawan mainnya seadil mungkin (termasuk posisi home dan away). So, ingin tahu kan bagaimana cara mereka membagi jadwal pertandingannya?

Pada tulisan kali ini, saya akan menjelaskan algoritma Round-robin versi sederhana yang mana masih perlu dikembangkan lebih jauh. Sebelum masuk tahap implementasi, ada beberapa kelemahan yang harus saya terangkan terlebih dahulu. Asumsikan ada 5 partisipan yang direpresentasikan sebagai [1, 2, 3, 4, 5].

Kelemahannya:

Partisipan 1 selalu di bagian "home".
Partisipan 1 bermain 5 kali yang mana seharusnya 4 kali agar adil.
Well, algoritma ini belum bisa mengatasi partisipan yang jumlahnya ganjil. Dan, apabila genap pun, partisipan 1 selalu mendapat home. Artinya, algoritma sederhana ini masih belum bisa dikatakan adil. Di tulisan berikutnya, akan kembali saya jelaskan mengenai algoritma ini yang telah dikembangkan menggunakan Berger tables.

Algoritma

Langkah-langkah untuk implementasi algoritma ini adalah:

1. Ambil daftar partisipan
=> [1, 2, 3, 4, 5, 6]

2. Buat daftar tadi menjadi dua (dibagi 2)
=> [1, 2, 3] [4, 5, 6]

3. Asumsikan daftar yang dibagi dua adalah A dan B
=> A = [1, 2, 3]
=> B = [4, 5, 6]

4. Posisi B dibalik (reverse)
=> A = [1, 2, 3]
=> B = [6, 5, 4]

5. Ambil data sebagai Round 1
=> Round 1:
=> 1 vs 6
=> 2 vs 5
=> 3 vs 4

6. Ubah daftar A menjadi [1, (data pertama B), ..., (hapus data terakhir)]
=> A = [1, 6, 2]

7. Ubah daftar B menjadi [(hapus data pertama), ..., (data terakhir A)]
=> B = [5, 4, 3]

8. Daftar yang sudah diubah menjadi Round berikutnya
=> A = [1, 6, 2]
=> B = [5, 4, 3]
=>
=> Round 2
=> 1 vs 5
=> 6 vs 4
=> 2 vs 3

9. Ulangi langkah 6, 7, dan 8 hingga Round habis (sebanyak N).

Dimana N adalah
- (banyaknya partisipan - 1) jika jumlah partisipannya genap
- (banyaknya partisipan) jika jumlah partisipannya ganjil

Dalam kasus di atas (partisipan 6, genap) maka N = (6 - 1) = 5.
Berarti, jumlah Round-nya sebanyak 5.
Tabel perpindahan data kira-kira seperti di bawah. Bagian yang diberi kutip adalah data yang dipindahkan.

1, 2, 3, 4
8, 7, 6, 5

1, "8", 2, 3
7, 6, 5, "4"

1, "7", 8, 2
6, 5, 4, "3"

...

Dan seterusnya.
Apabila kamu tertarik melihat implementasinya dengan bahasa Haskell, kamu bisa melihatnya di repository saya yaitu wisn/halgorithms. Adapun cuplikan kodenya sebagai berikut.

-- Create the schedule. Here is the main Round-robin Schedule Algorithm
schedulizer :: [a] -> [[(a, a)]]
schedulizer list = makesSchedule list (length list) (-1)
  where
    makesSchedule :: [a] -> Int -> Int -> [[(a, a)]]
    makesSchedule _ _ 0        = []
    makesSchedule list n games =
      let games'  = if games == (-1)
                      then do
                        if even n then (n - 1) else n
                      else games

          middle  = n `div` 2
          divide  = splitAt middle list

          left  = fst divide
          right = if even n
                     then (reverse . snd) divide
                     else (reverse . init . snd) divide

          zipped = zip left right
      in [zipped] ++ makesSchedule (rotater list)

Fungsi Yang Harus Ada di Embedded System

1 1.  Embeded System Harus Mengikuti Aturan Tertentu

Contoh : Pengeraman pada motor /rem ABS(Anti Lock Braking System)

Penjelasan

Cara kerja rem ABS pada motor ini sendiri adalah sensor sistem ABS ini akan mendeteksi terjadinya sebuah penguncian terhadap roda, dan secara otomatis sensor akan mengirimkan sebuah sinyal ke modulator yg kemudian berfungsi utk memerintahkan piston rem pada roda tersebut agar mengendur. Dan pada saat penguncian pada roda sudah mulai berkurang, maka tekanan terhadap piston rem tersebut akan kembali ditingkatkan. Secara teknikal, cara kerja rem ABS ini sendiri seperti kita sedang melakukan settingan terhadap rem dengan cara mengocok pedal rem. Sehingga kendaraan dengan sistem rem ABS ini tidak akan langsung berhenti pada saat pedal rem ditekan secara penuh.

2.  Embeded System Harus Punya Logika Berurutan

Contoh : Pengambilan Tiket Kereta Api(Boarding Pass) 

Penjelasan

Yang harus dilakukan sebelum mengeprint tiket kereta api adalah kita harus memasukan kode tiket yang telah dipesan kemudian ketikkan pada mesin chek-in mandiri lalu akan muncul nama dan ID penumpang, kode booking, dan nama KA beserta tujuan dan jadwal keberangkatan kemudian klik print/cetak maka dengan sendirinya tiket akan keluar.

3.    Embedded system yang menggunakan sensor harus memiliki pemprosesan sinyal

Contoh : Sistem Sonar pada Kapal

Penjelasan

Cara kerja Sonar adalah pertama, echo sounder mengemisikan gelombang suara berfrekuensi tinggi. Gelombang suara ini akan merambat dalam air. Jika mengenai obyek seperti ikan, metal, dasar laut atau benda-benda yang lain, maka gelombang suara tadi akan terpantul. Sinyal pantulan akan diterima oleh hidrofon dan ditampilkan oleh display yang menggambarkan karakteristik obyek di bawah air.

Untuk mengetahui lokasi (jarak) dari obyek di bawah air, maka waktu yang dibutuhkan gelombang suara tersebut dapat digunakan untuk mencari jarak panjang gelombang yang ditempuh gelombang suara tersebut. Sedangkan jarak (posisi) aktual d dari obyek tersebut diperoleh dengan membagi dua panjang gelombang λ yang ditempuh.

4.    Perantara/interface komunikasi untuk beberapa embedded system

Contoh : Alarm Kebakaran Addressable

Penjelasan

Sistem addressable merupakan sistem yang memasang ID (address) pada detektor kebakarannya. Pada sistem ini, detektor yang dipasang terhubung langsung dengan kontrol utama. Dengan teknologi pemberian alamat pada setiap detektor, maka, saat terjadi kebakaran, ia akan langsung mengirimkan alarm dan signal lampu detektor mana yang mengirimkan. Kelebihan dari sistem ini adalah kemudahan yang didapatkan dalam menentukan letak akurat kebakaran. Saat kebakaran, hal ini sangat penting, karena dapat segera mengetahui jalur evakuasi yang tepat serta memperpanjang waktu evakuasi.

5.  Embedded system harus mampu respon terhadap kesalahan kalau ada kegagalan atau kerusakan

Contoh : Eject Flashdisk

Penjelasan

Jika flashdisk masih dalam proses mengirim data pada komputer, tetapi data belum selesai dikirim maka komputer akan menampilkan peringatan untuk melanjutkan mengirim data atau tidak melanjutkan mengirim data, agar dapat mencegah kesalahan pada pengiriman data. 

Mikroprosesor adalah sebuah IC (Integrated Circuit) yang digunakan sebagai otak/pengolah utama dalam sebuah sistem komputer. Mikroprosesor merupakan hasil dari pertumbuhan semikonduktor. Prosesor adalah chip yang sering disebut “Microprosessor” yang sekarang ukurannya sudah mencapai gigahertz. Ukuran tersebut adalah hitungan kecepatan prosesor dalam mengolah data atau informasi. Merk prosesor yang banyak beredar dipasatan adalah AMD, Apple, Cyrix VIA, IBM, IDT, dan Intel.

Sejarah Perkembangan Microprocessor

1904 : Dioda tabung pertama kali diciptakan oleh seorang ilmuwan dari Inggris yang bernama Sir John Ambrose Fleming (1849-1945)

1906 : ditemukan trioda hasil pengembangan dioda tabung oleh seorang ilmuwan Amerika yang bernama Dr. Lee De Forest. Yang kemudian terciptalah tetroda dan pentode.

Akan tetapi penggunaan dari tabung hampa tersebut tergeser pada tahun 1960 setelah ditemukannya komponen semikonduktor.

1947 : Transistor diciptakan di labolatorium Bell.

1965 : Gordon Moore dari Fairchild semiconductor dalam sebuah artikel untuk majalan elektronik mengatakan bahwa chip semikonduktor berkembang dua kali lipat setiap dua tahun selama lebih dari tiga dekade.

1968 : Moore, Robert Noyce dan Andy Grove menemukan Intel Corp. untuk menjalankan bisnis “INTegrated Electronics.”

1969 : Intel mengumumkan produk pertamanya, RAM statis 1101, metal oxide semiconductor (MOS) pertama di dunia. Ia memberikan sinyal pada berakhirnya era memori magnetis.

1971 : Intel meluncurkan mikroprosesor pertama di dunia, 4-bit 4004, yang didesain oleh Federico Faggin.

1972 : Intel mengumumkan prosesor 8-bit 8008. Bill Gates muda dan Paul Allen coba mengembangkan bahasa pemograman untuk chip tersebut, namun saat itu masih kurang kuat.

1974 : Intel memperkenalkan prosesor 8-bit 8080, dengan 4.500 transistor yang memiliki kinerja 10 kali pendahulunya.

1975 : Chip 8080 menemukan aplikasi PC pertamanya pada Altair 8800, sekaligus merevolusi PC. Gates dan Allen sukses mengembangkan bahasa dasar Altair, yang kemudian menjadi Microsoft Basic, untuk 8080.

1976 : Arsitektur x86 mengalami kemunduran saat Steve Jobs dan Steve Wozniak memperkenalkan Apple II computer dengan menggunakan prosesor 8-bit Motorola 6502.

1978 : Intel memperkenalkan mikroprosesor 16-bit 8086 yang kelak menjadi standar industri pada tanggal 8 Juni.

1979 : Intel memperkenalkan versi dengan harga yang lebih murah dari 8086, yaitu 8088 dengan 8-bit bus.

1980 : Intel memperkenalkan 8087 math co-processor.

1981 : IBM memilih 8088 untuk menjalankan PC-nya. Seorang eksekutif Intel kemudian mengatakannya sebagai “Kemenangan besar pertama Intel.”

1982 : IBM menandatangani Advanced Micro Devices sebagai sumber kedua Intel untuk mikroprosesor 8086 dan 8088.

1982 : Intel memperkenalkan prosesor 16-bit 80286 dengan 134.000 transistor.

1984 : IBM mengembangkan PC generasi kedua, 80286-based PC-AT. PC-AT yang menjalankan MS-DOS,

kelak menjadi standar PC selama hampir 10 tahun.

1985 : Intel keluar dari bisnis RAM dinamis untuk fokus pada mikroprosesor, dan akhirnya ia mengeluarkan prosesor 80386, sebuah chip 32-bit dengan 275.000 transistor dan kemampuan menjalankan berbagai macam program sekaligus.

1986 : Compaq Computer melambungkan IBM dengan PC yang didasarkan pada 80386.

1987 : VIA Technologies didirikan di Fremont, Calif., mereka akan mejual chip set core logic x86.

1989 : 80486 diluncurkan, dengan 1.2 juta buah transistor dan built-in math co-processor.

Intel telah memprediksi pengembangan prosesor multicore suatu saat pada tahun 2000-an.

1990 : Compaq memperkenalkan server PC pertama, yang dijalankan dengan menggunakan 80486.

1993 : Transistor 3.1 juta, prosesor 66-MHz Pentium dengan teknologi superscalar diperkenalkan.

1994 : AMD dan Compaq membentuk aliansi untuk mendukung Compaq computer dengan mikroprosesor Am486.

1997 : Intel meluncurkan teknologi prosesor 64-bit Epic. Ia juga memperkenalkan MMX Pentium untuk aplikasi prosesor sinyal digital, yang juga mencakup grafik, audio, dan pemrosesan suara.

1998 : Intel memperkenalkan prosesor Celeron di bulan April.

1999 : VIA mengakuisisi Cyrix Corp. dan Centaur Technology, pembuat prosesor x86 dan x87 co-processor.

2000 : Debut Pentium 4 dengan 42 juta transistor.

2003 : AMD memperkenalkan x86-64, versi 64-bit dari x86 instruction set.

2004 : AMD mendemonstrasikan x86 dual-core processor chip.

2005 : Intel menjual prosesor Dual-Core pertamanya.

2006 : Dell Inc. mengumumkan akan menawarkan system prosesor berbasis A

Three Little Bird

Lagu Three Little Bird yang di ciptakan dan di populerkan oleh Bob Marley, seseorang yang indentik dengan Reggae. Pria kelahiran 6 Februari 1945 ini adalah orang yang memperkenalkan reggae pada dunia. Gue adalah salah satu penggemar reggae dan bukan penggemar reggae namanya kalau nggak suka Bob Marley. 

Di Indonesia, Reggae belum terlalu terlihat, seenggaknya di televisi yang dibanjiri lagu-lagu pop. Namun tak dapat dipungkiri penggemar Reggae sudah banyak, terbukti banyak acara-acara kampus yang menghadirkan band-band beraliran Reggae.

Salah satu lagu Bob Marley yang bagus dan sekaligus soundtrack film adalah Three Little Bird Seperti halnya kebanyakan lagu Bob Marley yang bercerita tentang jangan terlalu memikirkan masalah dan nikmati saja hidup apa adanya, Three Little Bird juga menampilkan lirik yang mengajak pendengarnya untuk santai sejenak dan cobalah berpikir positif, nggak ada masalah yang diberi Allah SWT melebihi kemampuan suatu individu, kan? Seperti kata Steven Coconut Treez, "kalau kau frustasi karena kurang santai, kaupun sakit hati karena kurang santai." Jadi cobalah santai kawan....(sambil joget patah-patah ala reggae (ala reggae loh, ya, bukan ala Anissa Bahar)).

Lagu Three Little Bird ini muncul di film I am legend, sebagai lagu favorit sang peran utama yang dimainkan oleh Will Smith yaitu Robert Neville, yang seorang ahli virus militer Amerika. Film ini menurut gue bagus banget selain karena gue suka film dengan genre semacam ini, science fiction. Bagi yang belum nonton coba deh tonton, seru.

Kembali ke lagunya, lagu yang berada di album Exodus ini memiliki dua versi tentang asal usul judul lagunya. Satu pihak mengatakan bahwa Bob Marley terinsipirasi dari banyak hal, ia mengamati kehidupan lalu Bob Marley teringat akan tiga burung kenari yang datang ke jendela rumahnya. Namun ada pula yang mengatakan bahwa Three Little Bird merupakan tiga penyanyi wanita dari grup Reggae. Tak masalah siapa yang benar, namun memang lagu ini benar-benar bagus. Berikut makna liriknya menurut saya.

Three Little Birds

Bob Marley

'Don't worry about a thing,

Jangan khawatir tentang hal itu
'Cause every little thing is gonna be all right.

Karena setiap hal kecil akan baik-baik saja
Singing: 'Don't worry about a thing,

Bernyanyi: "jangan khawatir tentang hal itu,"
'Cause every little thing gonna be all right!'

Karena setiap hal kecil akan baik-baik saja

(Lirik ini mengajak kita agar tak terlalu khawatir akan suatu hal, karena semua hal akan baik-baik saja. Karena memang masalah kan bukan buat dikhawatirin tapi untuk diselesaikan, namun jika dalam perjalanan untuk menyelesaikannya sangat sulit maka coba tanamkan dalam pikiran, "semuanya akan baik-baik saja" Liriknya bener-bener masuk apalagi dipadu sama musik Reggae yang menurut gue ngajak santai)

Rise up this morning,

Bangkitlah pagi ini
Smiled with the rising sun,

Tersenyumlah dengan matahari terbit
Three little birds

Tiga burung kecil
Pitch by my doorstep
Berada di depan pintu rumahku

Singing sweet songs
Menyanyikan lagu-lagu manis
Of melodies pure and true,
Melodi murni dan benar
Saying, ('This is my message to you-ou-ou')
Bernyanyi, "lagu ini adalah pesan untukmu-ou-ou"
(Di lirik ini Bob Marley mengajak untuk menyambut hari dengan senyuman. Dan disini pendapat pertama tentang asal usul judul lagu kayanya terbukti soalnya ada lirik yang mengungkapkan tentang tiga ekor burung di rumah Bob Marley)

Singing 'Don't worry about a thing,

 Bernyanyi Jangan khawatir tentang hal itu
'Cause every little thing is gonna be all right.

Karena setiap hal kecil akan baik-baik saja
Singing: 'Don't worry about a thing,

Bernyanyi: "jangan khawatir tentang hal itu,"
'Cause every little thing gonna be all right!'

Karena setiap hal kecil akan baik-baik saja

(Lirik ini mengajak kita agar tak terlalu khawatir akan suatu hal, karena semua hal akan baik-baik saja. Karena memang masalah kan bukan buat dikhawatirin tapi untuk diselesaikan, namun jika dalam perjalanan untuk menyelesaikannya sangat sulit maka coba tanamkan dalam pikiran, "semuanya akan baik-baik saja" Liriknya bener-bener masuk apalagi dipadu sama musik Reggae yang menurut gue ngajak santai)

Rise up this morning,

Bangkitlah pagi ini
Smiled with the rising sun,

Tersenyumlah dengan matahari terbit
Three little birds

Tiga burung kecil
Pitch by my doorstep
Berada di depan pintu rumahku

Singing sweet songs
Menyanyikan lagu-lagu manis

Of melodies pure and true,
Melodi murni dan benar

Saying, ('This is my message to you-ou-ou')
Bernyanyi, "lagu ini adalah pesan untukmu-ou-ou"
(Di lirik ini Bob Marley mengajak untuk menyambut hari dengan senyuman. Dan disini pendapat pertama tentang asal usul judul lagu kayanya terbukti soalnya ada lirik yang mengungkapkan tentang tiga ekor burung di rumah Bob Marley)


Singing 'Don't worry about a thing, worry about a thing, oh!
Bernyanyi 'jangan khawatir tentang hal itu, khawatir tentang hal itu, oh!
Every little thing is gonna be all right. Don't worry!'
Setiap hal kecil akan baik-baik saja. Jangan khawatir!
Singing 'Don't worry about a thing' - I won't worry!
Bernyanyi 'jangan khawatir tentang hal itu - aku tidak akan khawatir!
''Cause every little thing is gonna be all right.'
Karena setiap hal kecil akan baik-baik saja


Singing 'Don't worry about a thing' - I won't worry!
Bernyanyi 'jangan khawatir tentang hal itu - aku tidak akan khawatir!
''Cause every little thing is gonna be all right.'
Karena setiap hal kecil akan baik-baik saja
 Singing 'Don't worry about a thing' 
Bernyanyi 'jangan khawatir tentang hal itu
''Cause every little thing is gonna be all right.'
Karena setiap hal kecil akan baik-baik saja
Singing 'Don't worry about a thing' - Oh no!
Bernyanyi 'jangan khawatir tentang hal itu - oh tidak!
''Cause every little thing is gonna be all right.'
Karena setiap hal kecil akan baik-baik saja 

Bio Damian Marley

Damian Marley adalah putra bungsu dari legenda reggae Bob Marley. Damian's nickname adalah Junior Gong yang berasal dari nama panggilan ayahnya dari Tuff Gong.

Seorang seniman berbakat di kanan sendiri, Damian telah melakukan sejak usia 13. Khusus musiknya adalah "bersulang", gaya Jamaika "rap" yang beberapa orang menganggap modern pendahulu hip-hop. Damian memiliki banyak catatan, termasuk reggae ditempatkan tertinggi album di Amerika Serikat tangga album billboard dengan Welcome To Jamrock,

dan tempat tertinggi lagu reggae di UK Top 40 dengan PlayWelcome untuk Jamrock.

Seperti ayahnya sebelum dia dan seluruh keluarga Marley, dia adalah seorang Rastafarian dan musiknya mencerminkan kedua keyakinan dan prinsip-prinsip Rastafari satu cinta, satu planet dan kebebasan untuk semua.