Algoritma seleksi

    Dalam ilmu komputer, sebuah algoritma pemilihan adalah sebuah algoritma untuk menemukan bilangan terkecil ke-k (bilangan terbesar ke-k) dalam sebuah list. Termasuk di dalamnya adalah kasus sederhana yang lazim yaitu menemukan elemen minimum, maksimum dan median. Algoritma ini disebu juga orde statistik. Terdapat algoritma yang relatif sederhana untuk menemukan, minimum, maksimum, dan element terkecil ke-k dengan waktu linear. Algoritma ini juga memungkinkan untuk menemukan elemen terkecil ke-k dalam waktu linear yang paling buruk atau orde statistik berlipat. Seleksi adalah sebuah sub masalah dari permasalahan yang lebih kompleks seperti permasalahan tetangga terdekat.

   Satu algoritma seleksi yang sederhana dan digunakan secara luas adalah memanfaatkan algoritma pengurutan pada list, kemudian mengekstrak elemen ke-k. Ini adalah contoh reduksi satu permasalahan ke dalam permasalahan lain. Hal ini bermanfaat ketika kita ingin melakukan banyak seleksi terhadap sebuah list tunggal, dimana kasus ini membutuhkan hanya satu operasi pengurutan di awal yang membutuhkan waktu yang lama (expensive), yang diikuti oleh banyak operasi ekstraksi yang sebentar (Cheap). Ketika kita hanya ingin melakukan satu seleksi, atau ketika kita ingin selalu mengubah list di antara tiap seleksi, metode ini dapat jadi lebih lama (costly), biasanya membutuhkan paling sedikit O(n log n) waktu, dimana n adalah panjang dari list.

Algoritma minimum/maksimum linear
Kasus terburuk algoritma linear untuk menemukan minimum atau maksimum adalah sangat jelas; kita menyimpan dua peubah, satu mengacu ke indeks dari elemen minimum/maksimum yang didapatkan sementara, dan satu lagi menyimpan nilainya. Bersamaan dengan kita memindai list tersebut, kita perbarui kedua peubah tersebut jika kita menemukan sebuah elemen yang sesuai:

function minimum(a[1..n])
minIndex := 1
minValue := a[1]
for i from 2 to n
if a[i] < minValue
minIndex := i
minValue := a[i]
return minValue

function maximum(a[1..n])
maxIndex := 1
maxValue := a[1]
for i from 2 to n
if a[i] > maxValue
maxIndex := i
maxValue := a[i]
return maxValue

Sebagai catatan, kemungkinan akan terdapat banyak elemen minimum atau maksimum. Oleh karena pembandingan di atas adalah kaku (strict), algoritma tersebut menemukan elemen minimum dengan indeks yang minimum. Dengan memanfaatkan pembandingan tak kaku (non-strict) (≤ and ≥), kita akan menemukan elemen minimum dengan indeks maksimum.
Jika kita ingin menemukan kedua elemen minimum dan maksimuam bersamaan, perbaikan kecil dapat dilakukan dengan sepasang pembandingan, yaitu membandingkan elemen ganjil dan genap pada setiap pasang dan membandingkannya dengan elemen maksimum dan minimum.
Algoritma seleksi umum nonlinear
Dengan memakai ide yang sama yang digunakan dalam algoritma minimum/maksimum, kita dapat mengkonstruksi sebuah algoritma sederhana tapi tidak efisien untuk menemukan item terkecil ke-k atau terbesar ke-k, yang membutuhkan waktu O(kn), yang efektif untuk k yang kecil. Untuk memperolehnya, kita cukup menemukan nilai paling ekstrim dan memindahnya ke bagian awal sampai kita mendapatkan indeks yang diinginkan. Hal ini dapat dilihat sebagai pengurutan seleksi yang tidak lengkap. Berikut ini adalah algoritma berbasis minimum:

function select(a[1..n], k)
for i from 1 to k
minIndex = i
minValue = a[i]
for j = i+1 to n
if a[j] < minValue
minIndex = j
minValue = a[j]
swap a[i] and a[minIndex]
return a[k]

Keuntungan lain dari metode ini adalah:

* Setelah mengetahui lokasi elemen terkecil ke-j, waktu yang dibutuhkan hanya O(j + (k-j)2) untuk menemukan elemen terkecil ke-k, atau hanya O(k) untuk k ≤ j.
* Metode ini dapat dilakukan dengan struktur data list berkait, dimana list terbut berbasis partisi yang membutuhkan pengaksesan acak.

Algoritma menggambar garis

Software Untuk Grafika Komputer

      Software untuk menggambar grafik pada komputer ada dua jenis yaitu software yang bebentuk library atau pustaka pada suatu bahasa pemrograman(paket pemrograman grafika) dan software yang berbentuk aplikasi khusus. Pada software yang berbentuk library suatu bahasa pemrograman akan dilengkapi fungsi fungsi grafik yang berasal dari paket software grafik tersebut yang termasuk contoh dari jenis ini adalah Open Gl yang dibuat Silicon Graphics. Sedang pada paket aplikasi khusus gambar grafik dibuat tanpa mengetahui bagaiamanahal itu dapat terjadi, contoh dari jenis ini adalah Blender ataupun Qcad.Pada Modul ini yang digunakan adalah software jenis pertama dengan menggunakan fungsi grafik pada Bahasa Pemrograman Pascal.
Note: Semua kode pada modul ini menggunakan prosedur prosedur di bawah. tambahkan pada setiap awal kode program!.
procedure init;

var gd, gm : integer;
begin
gm:=detect; gd:=0;
InitGraph(gd,gm,”);
if GraphResult <> grOk then
begin
Writeln(‘Graph driver ‘,gd,’ graph mode ‘,gm,’ not supported’);
Halt(1);
end;
end;
procedure destroy;
begin
closegraph;
end;

BAB II
Output Primitif

1. TITIK
Titik dalam Grafika Komputer bisa didefinisikan sebagai suatu posisi tertentu dalam suatu sistem koordinat. Sistem koordinat yang dipakai bisa Polar Coordinates atau Cartesian Coordinates. Biasanya dalam pemrograman grafis, yang paling umum digunakan adalah Cartesian Coordinates.
Dalam Cartesian Coordinates, titik didefinisikan sebagai kombinasi dua bilangan yang menentukan posisi tersebut dalam koordinat x dan y (2D)

Contoh Penerapan
Jika kita ingin menempatkan titiktitik A(2,4), B(1,1), C(4,1.5), D(4,2), E(–4,3)

PERBEDAAN SCREEN DAN CARTESIAN COORDINATES

Prinsipnya, karena monitor didesain untuk menggambar dari atas ke bawah, maka sumbu y pada Screen Coordinates dan Cartesian Coordinates berbeda arah, untuk Screen Coordinates, sumbu Y arahnya ke bawah, sedangkan pada Cartesian Coordinates, sumbu Y arahnya ke atas. Biasanya dalam rendering pipeline, hal yang terakhir dilakukan adalah mengkonversi Cartesian Coordinates ke Screen Coordinates.
Dalam Sistem Operasi Linux, koordinat yang dipakai antara Cartesian dan Screen sama, yaitu Y positif ke atas.
Untuk koordinate 3D, sama dengan 2D, hanya saja ditambah 1 sumbu yaitu sumbu z (axisz). Ada beberapa cara untuk menggambarkan sumbu X, Y dan Z, ini. Pertama dengan sumbu z mengarah ke atas

2. Garis

Umumnya persamaan garis lurus pada koordinat kartesius diwujudkan dalam persamaan garis : y=m.x+b
jika dimisalkan pada dua titik(x0,y0 dan x1,y1) akan dibuat sebuah garis lurus, kita dapat menentukan nilai “m’ dan “b” dengan persamaan berikut:
y1y0

m= ______
x1x0
b=y1m.x1

algoritma untuk menggambar garis pada komputer didasarkan pada dua persamaan di atas. dimana m adalah gradien atau kemiringan garis tersebut.
1.Algoritma digital differential analyzer(DDA),
Prinsip algoritma ini adalah mengambil nilai integer terdekat dengan jalur garis berdasarkan atas sebuah titik yang telah ditentukan sebelumnya(titik awal garis).
Algoritma pembentukan garis DDA:
1.Tentukan dua titik yang akan dihubungkan dalam pembentukan garis.
2.Tentukan salah satu titik sebagai awal(x0,y0) dan titik akhir(x1,y1).
3.Hitung dx=x1x0, dan dy= y1y0.
4.Tentukan langkah, yaitu dengan cara jarak maksimum jumlah penambahan nilai x maupun nilai y, dengan cara:
Bila nilai absolut dari dx lebih besar dari absolut dy, maka langkah= absolut dari dx.
Bila tidak maka langkah= absolutdari dy
5.Hitung penambahan koordinat pixel yaitu x_increment=dx/langkah, dan y_increment=dy/langkah
6.Koordinat selanjutnya (x+x_increment, y+y_increment)
7.Posisi pixel pada layar ditentukan dengan pembulatan nilai koordinat tersebut.
8.Ulangi nomor 6 dan 7 untuk menentukan posisi pixel selanjutnya,sampai x=x1 dan y=y1.
Contoh Prosedur DDA dalam pascal:
uses graph,crt;
{tambahkan pada bagian ini prosedur penginisialisasian device, lihat pada bab 1}
procedure drawLine(xstart,ystart,xend,yend:integer);

var
step,k:integer;
dx,dy:real;
x_inc,y_inc,x,y:real;
begin
dx:=xend-xstart;
dy:=yend-ystart;
x:=xstart;
y:=ystart;
if abs(dx) > abs(dy) then
step:=round(abs(dx))
else
step:=round(abs(dy));
x_inc:=dx/step;
y_inc:=dy/step;
putPixel(round(x),round(y),30);
for k:=1 to step do
begin
x:=x+x_inc;
y:=y+y_inc;
putPixel(round(x),round(y),30);
end;
end;
begin
init;
{menggambar garis dari titik 10,10 ke 500,10}
drawLine(10,10,500,10);
readkey;
destroy;
end.

Algoritma Lingkaran Midpoint

        Algoritma Lingkaran Midpoint juga disebut algoritma lingkaran Bressenham. Bressenham mengembangkan generator lingkaran yang cukup efisien. Algoritma yang digunakan membentuk semua titik berdasarkan titik pusat dengan penambahan semua jalur sekeliling lingkaran. Algoritma ini diturunkan dari algoritma Midpoint untuk pembentukan garis. Dalam hal ini hanya diperhatikan bagian 45’ dari suatu lingkaran, yaitu oktan kedua dari x=0 ke x=R/Ö2, dan menggunakan CirclePoints untuk menampilkan titik dari seluruh lingkaran.

Langkah langkah untuk membentuk lingkaran algoritma Circle Midpoint:
1. Tentukan radius r dengan titk pusat lingkaran(xc,yc) kemudian diperoleh (x0,y0)=(0,r)

2. Hitung nilai dari parameter P0=5/4r
3. Tentukan nilai awal k=0, untuk setiap posisi xk berlaku sebagai berikut:
- Bila Pk< 0, maka titik selanjutnya adalah (xk+1,k+1,k+1,k+1,yk)k))dan Pk+1k+1k+1=Pk+2xk+1k+1k+1+1 - Bila tidak, maka selanjutnya adalah(xk+1,k+1,k+1,k+1,yk-1k-1k-1), dan Pk+1k+1k+1=Pk+2xk+1k+1k+1+12yk+1k+1k+1 Dimana 2xk+1=k+1=k+1=k+1=2xk+2 dan 2yk+k+=2yk2 4. Tentukan titik simetris pada ketujuh oktan yang lain 5.Gerakkan setiap posisi pixel(x,y) pada garis melingkar dari lingkaran dengan titik pusat (xc,yc) dan tentukan nilai koordinat: x=x+xcy=y+yc 6.Ulangi langkah ke3 sampai 5, sehingga x>=y

Prosedur algoritma lingkaran midpoint:
Input yang digunakan pada prosedur ini adalah koordinat titik pusat dan radius lingkaran. Posisi pixel ditentukan dengan rutin setPixel.

uses graph,crt;
procedure init;
var gd, gm : integer;
begin
gm:=detect; gd:=0;
InitGraph(gd,gm,'');
if GraphResult <> grOk then
begin
Writeln('Graph driver ',gd,' graph mode ',gm,' not supported');
Halt(1);
end;
end;
procedure destroy;
begin
closegraph;
end;
procedure circlePlotPoints(xCenter,yCenter,x,y:integer);
begin
putPixel(xCenter+x, yCenter+y,30);
putPixel(xCenter-x, yCenter+y,30);
putPixel(xCenter+x, yCenter-y,30);
putPixel(xCenter-x, yCenter-y,30);
putPixel(xCenter+y, yCenter+x,30);
putPixel(xCenter-y, yCenter+x,30);
putPixel(xCenter+y, yCenter-x,30);
putPixel(xCenter-y, yCenter-x,30);
end;
procedure circleMidPoint (xCenter,yCenter,radius:integer);
var
x,y,p:integer;
begin
x:=0;
y:=radius;
p:=1-radius;
circlePlotpoints(xCenter,yCenter,x,y);
while x
begin
x:=x+1;;
if p<0 then p:=p+(2*x+1) else begin y:=y-1; p:=p+(2*(x-y)+1); end; end; circlePlotPoints(xCenter,yCenter,x,y); end; begin init; circleMidPoint(100,100,90); readkey; destroy; end. Latihan : Diketahui titik pusat lingkaran (0,0) dan radius 8, perhitungan berdasarkan oktan dari kuadran pertama dimana x = 0 sampai y = 0. Nilai parameter dapat ditentukan dengan P0 = 1 – r = 1 – 8 = -7 Koordinat titik awal adalah (x,r) = (0,8) Jawab: X = 0 Y = r = 8 -------------------------------------------------------------- K=0 P = 1 – r = 1 – 8 = -7 Loop ke-1 x = x +1 y tetap 8 = 0 +1 = 1 --------------------------------------------------------------- K=1 P = P + 2 * X + 1 = -7 + 2 * 1 + 1 = -4 Loop ke-2 x = x +1 y tetap 8 = 1 +1 = 2 --------------------------------------------------------------- K=2 P = P + 2 * X + 1 = -4 + 2 * 2 + 1 = 1 Loop ke-3 x = x +1 y = y-1 = 2 +1 = 3 = 8-1 = 7 --------------------------------------------------------------- K=3 P = P + 2 * (X –Y) +1 = 1 + 2 * (3 – 7) + 1 = -6 Loop ke-4 x = x +1 y tetap 7 = 3 +1 = 4 --------------------------------------------------------------- K=4 P = P + 2 * X + 1 = -6 + 2 * 4 + 1 = 3 Loop ke-5 x = x +1 y = y-1 = 4 +1 = 5 = 7-1 = 6 --------------------------------------------------------------- K=5 P = P + 2 * (X - Y) + 1 = 3 + 2 *(5 - 6) + 1 = 2 Loop ke-6 x = x +1 y = y-1 = 5 +1 = 6 = 6-2 = 5 --------------------------------------------------------------- K=6 P = P + 2 * (X - Y) + 1 = 2 + 2 *(6 - 5) + 1 = 5 Loop berhenti karena x > y