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