Algoritma Prims dan Kruskal

Langkah langkah algoritma Prims :

1. ambil sisi dari graf G berbobot minimum , masukkan dalam T
2. pilih sisi lain dengan bobot minimum dan incident dengan simpul di T, dan tak terbentuk sirkuit
3. ulangi langkah 2 sebanyak n-2 kali

Lintasan dan sirkuit Hamilton

• Lintasan Hamilton ialah lintasan yang melalui tiap simpul didalam graf tepat satu kali

• Sirkuit Hamilton ialah sirkuit yang melalui tiap simpul didalam graf tepat satu kali, kecuali simpul awal (juga mrpk simpul akhir) dilalui 2 kali
• Graf yang memiliki sirkuit Hamilton disebut graf Hamilton , sedangkan graf yang memiliki lintasan Hamilton disebut graf semi Hamilton

Contoh :

Graf Di samping memiliki lintasan Hamilton dengan lintasan :

b,c,d,e,f,g,a,b

dan Graf di samping juga memiliki sirkuit Hamilton karena di awali di simpul b dan berakhir di simpul b








Graf disamping memiliki lintasan Hamilton dengan lintasan :

a,b,c,d,e,i,f,g,h

Tapii graf disamping tidak memiliki sirkuit Hamilton.











Teorema Untuk Lintasan dan Sirkuit Hamilton

• Syarat cukup (bukan syarat perlu) supaya graf sederhana G dengan n buah simpul (n>=3) adalah graf Hamilton ialah jika derajad tiap simpul paling sedikit n/2
• Setiap graf lengkap adalah graf Hamilton
• Dalam graf l engkap dengan n buah simpul (n>=3) terdapat (n-1)! /2 buah sirkuit Hamilton
• Dalam graf lengkap G dengan jumlah simpul n>=3 dan n ganjil , terdapat (n-1)/2 buah sirkuit Hamilton yang saling lepas (tidak ada sisi yang beririsan). Jika n genap dan n>=4 , maka dalam G terdapat (n-2)/2 buah sirkuit Hamilton

Lintasan dan Sirkuit Euler

Lintasan dan Sirkuit Euler

• Lintasan Euler ialah lintasan yang melalui tiap sisi dalam graf tepat sekali
• Sirkuit Euler ialah sirkuit yang melalui tiap sisi dalam graf tepat satu kali
• Graf yang mempunyai sirkuit Euler disebut graf Euler, sedang graf yang mempunyai lintasan Euler disebut semi Euler

Contoh
a. Apakah Ada Lintasan Euler ?
b. Apakah ada sirkuit Euler ?

Jawab
a. ADA lintasan euler dengan lintasan :
a,b,c,d,e,f,g,b,d,f,a,g

b. Tidak ADA sirkuit Euler.








a. Apakah ada lintasan Euler ?
b. Apakah ada Sirkuit Euler ?

Jawab
a. ADA lintasan Euler dengan lintasan :
a,b,c,d,e,c,h,b,f,h,e,f,g,a
b. Ada sirkuit euler karena berawal dari simpul a dan berakhir di simpul a

Teorema Untuk Lintasan dan sirkuit euler

• Graf tak berarah memiliki lintasan Euler jika dan hanya jika terhubung dan mempunyai 2 buah simpul berderajat ganjil atau tidak ada simpul berderajad ganjil samasekali

• Graf tak berarah G adalah graf Euler jika hanya jika setiap simpul berderajad genap

• Graf berarah G memiliki sirkuit Euler jika hanya jika G terhubung dan setiap simpul memiliki derajad masuk dan derajad keluar sama. G memiliki lintasan Euler jika dan hanya jika G terhubung dan setiap simpul memiliki derajad masuk dan derajad keluar sama kecuali 2 simpul, yang pertama memiliki derajad keluar satu lebih besar dari derajad masuk, dan yang kedua memiliki derajad masuk satu lebih besar dari derajad keluar

Bentuk Logika terstruktur dengan Flow Chart

1. Struktur urut sederhana (simple sequence)
2. Struktur 1 pilihan dengan IF-Then

3. Struktur 2 pilihan dengan IF-THEN-ELSE

4a. Struktur banyak pilihan dengan IF-THEN-ELSEIF

4b. Struktur banyak pilihan dengan CASE


5. Struktur perulangan FOR

6. Struktur perulangan WHILE

7. Struktur perulangan UNTIL

Filosofis Terstruktur

• Mana yang susunannya terstruktur (teratur, …)
• Mana yang lebih mudah anda hafalkan
• Jika akan ditambah satu batang lagi, dimana harus diletakkan agar posisinya dapat dinilai benar
• Jika susunannya dirombak, mana yang lebih mudah untuk disusun kembali

Metode Dasar Pemrograman terstruktur

Ide awal penerapan pemrograman terstruktur yaitu dengan menghindari penggunaan GOTO untuk melompat ke bagian program tertentu.

Kegunaan GOTO untuk melompat ke baris program tertentu, secara umum dapat dibagi ke dalam 2 kelompok :

1. Melompat ke bagian bawah program dari posisi program saat ini
2. Melompat ke bagian atas program dari posisi program saat ini

Dengan pemrograman terstruktur;

Jika ada kebutuhan melompat ke bagian bawah, dapat digantikan dengan perintah Selection (If, Case, Select, Switch,…)

Jika ada kebutuhan melompat ke bagian atas, dapat digantikan dengan perintah Looping (for, While, repeat-until,…)

Untuk itu dalam pemrograman terstruktur hanya dikenal 3 struktur :

1. Sekuensial, yaitu program yang tidak memiliki lompatan. Baris program dijalankan secara normal (lurus) satu per-satu dari atas ke bawah
2. Selection, yaitu program yang memiliki pilihan apakah harus menjalankan baris program sesuai dengan urutannya atau melompati sejumlah baris program tersebut
3. Looping, yaitu program yang juga mengandung pilihan apakah akan mengulangi program yang sudah pernah dijalankan sebelumnya atau tidak

Prinsip utamanya adalah, program tidak boleh melompat ke atas, kecuali untuk keperluan pengulangan

Ide Pemrograman Terstruktur

• Pemrograman yaitu aktivitas membuat program, yaitu menyusun sejumlah perintah yang dikenal komputer

• Terstruktur dapat berarti terpola, bentuk yang mengikuti aturan tertentu, juga berarti sesuatu yang sistematis

• Orang pertama yang mencetuskan ide pemrograman terstruktur adalah Profesor Edsger W. Dijkstra dari University of Eindhoven, Nederland. Ide utamanya adalah bahwa statemen GOTO sebaiknya tidak digunakan di dalam pemrograman terstruktur, sebab bisa membuat program menjadi ruwet.

• Ide ini ditanggapi oleh HD Milis, yang beranggapan bahwa pemrograman terstruktur semestinya tidak hanya dihubungkan dengan tanpa penggunaan GOTO, tetapi yang lebih utama adalah struktur program itulah yang menentukan apakah suatu pemrograman terstruktur atau tidak.

• Ide pemrograman terstruktur muncul karena jumlah baris program semakin lama semakin besar, tentu saja hal ini terjadi karena diinginkan aplikasi yang lengkap dan lebih berkualitas.

• Dengan ide pemrograman terstruktur diharapkan dapat membantu manajemen source code (kode program) sehingga program mudah untuk dikelola bagi kepentingan selanjutnya.

• Tujuan utama pemrograman terstruktur adalah : agar program-program besar menjadi lebih mudah ditelusuri alur logikanya, mudah untuk dimodifikasi (dikembangkan) dan mudah pula untuk ditemukan bagian yang salah ketika program sedang diuji.
  
  

Aturan Penulisan Algoritma

• Judul algoritma

Bagian yang terdiri atas nama algoritma dan penjelasan (spesifikasi) tentang algoritma tersebut. Nama sebaiknya singkat dan menggambarkan apa yang dilakukan oleh algoritma tersebut.

• Deklarasi

Bagian untuk mendefinisikan semua nama yang digunakan di dalam program. Nama tersebut dapat berupa nama tetapan, peubah, tipe, prosedur dan fungsi.

• Deskripsi

Bagian ini berisi uraian langkah-langkah penyelesaian masalah yang ditulis dengan menggunakan notasi yang akan dijelaskan selanjutnya

Bahasa Pemrograman

Program yang ditulis dalam bahasa pemrograman akan diterjemahkan ke dalam bahasa mesin (biner) menggunakan penterjemah.

Interpreter :
Menterjemahkan baris per baris instruksi [Bahasa Basic]

Compiler
Menterjemahkan setelah seluruh instruksi di tulis [Pascal, C]

Memprogram dan Bahasa pemograman

• Belajar memprogram adalah belajar tentang metodologi pemecahan masalah, kemudianmenuangkannya dalam suatu notasi tertentu yang mudah dibaca dan dipahami.

• Belajar bahasa pemrograman adalah belajar memakai suatu bahasa, aturan tata bahasanya, instruksi-instruksinya, tata cara pengoperasian compiler-nya untuk membuat program yangditulis dalam bahasa itu saja.

Notasi Algoritma
Penulisan algoritma tidak tergantung dari spesifikasi bahasa pemrograman dan komputer yang mengeksekusinya. Notasi algoritma bukan notasi bahasa pemrograman tetapi dapat diterjemahkan ke dalam berbagai bahasa pemrograman
Notasi algoritma : Uraian Kalimat Deskriptif (narasi)

Contoh
Algoritma Kelulusan_mhs
Diberikan nama dan nilai mahasiswa, jika nilai tersebut lebih besar atau sama dengan 60 maka mahasiswa tersebut dinyatakan lulus. jika nilai lebih kecil dari 60 maka dinyatakan tidak lulus.
DESKRIPSI :
baca nama dan nilai mahasiswa.
jika nilai >= 60 maka
keterangan = lulus
tetapi jika
keterangan = tidak lulus.
tulis nama dan keterangan
Notasi Algoritma : PseudoCode

Algoritma Kelulusan_mhs
{diberikan nama dan nilai mahasiswa, jika nilai tersebut lebih besar atau sama dengan 60 maka mahasiswa tersebut dinyatakan lulus jika tidak maka dinyatakan tidak lulus}
DEKLARASI :
Nama : string
Nilai : integer
Keterangan : string
DESKRIPSI :
read (nama, nilai)
if nilai >= 60 then
keterangan = ‘lulus’
else
keterangan = ‘tidak lulus’
write(nama, keterangan)


FlowChart Kelulusan Mahasiswa

Contoh Sederhana Algoritma (2)

Ada minyak yang terdapat dalam sebuah wadah. kita di minta untuk menghitung 1 liter dengan menggunakan ember yng berukuran 3 liter dan 5 liter. Jelaskan rangkaian urut-urutannya..??



Ciri Penting Algoritma

• Algoritma harus berhenti setelah mengerjakan jumlah langkah terbatas.
• Setiap langkah harus didefinisikan dengan tepat dan tidak berarti-dua (Ambiguitas).
• Algoritma memiliki nol atau lebih masukkan.
• Algoritma memiliki nol atau lebih keluaran.
• Algoritma harus efektif (setiap langkah harus sederhana sehingga dapat dikerjakan dalam waktu yang masuk akal).

Dalam bidang komputer, algoritma sangat diperlukan dalam menyelesaikan berbagai masalah pemrograman, terutama dalam komputasi numeris.
Tanpa algoritma yang dirancang baik maka proses pemrograman akan menjadi salah, rusak, atau lambat dan tidak efisien.

Pelaksana algoritma adalah Komputer.
Manusia dan komputer berkomunikasi dengan cara : manusia memberikan perintah-perintah kepada komputer berupa instruksi-instruksi yang disebut program

Komputer adalah alat bantu untuk menyelesaikan masalah.
• Dalam menyelesaian masalah dengan komputer perlu merumuskan langkah langkah penyelesaian masalah dalam sekumpulan instruksi.
• Sekumpulan instruksi yang dimengerti oleh komputer yang disebut dengan program

Terminologi Graf

• Ketetanggaan (adjocent) antara 2 simpul: bila kedua simpul tersebut terhubung langsung
• Contoh: G1= {{1,2},{1,3},{2,3},{2,4},{3,4}}
• Simpul 1 bertetangga dengan simpul 2 dan 3
• Simpul 1 tdk bertetangga dengan simpul 4
• Bersisian (incidency)
• Sisi e= {vj,vk}
• e bersisian dengan simpul vj dan
• e bersisian dengan simpul vk

Contoh :

• Simpul terpencil adalah simpul yang tidak mempunyai sisi yang bersisian dengannya

• Graf kosong adalah graf yang himpunan sisinya merupakan himpunan kosong

• Derajad suatu simpul pada graf tak berarah adalah jumlah sisi yang bersisian dengan simpul tersebut

Derajad (a) = 2
Derajad (b) = 2
Derajad (c) = 3
Derajad (d) = 1
Derajad (e) = 0

Jumlah Derajad = 8

Derajad pada graf tak berarah adalah GENAP atau 2x sisinya.

• Notasi : d(v)
• d(simpul terpencil)?
• d(simpul anting-anting) ?

Pada Graf Berarah

• din (v)= derajad masuk
• =jumlah sisi yang masuk kesimpul tersebut
• dout(v) = derajad keluar
• =jumlah sisi yang keluar dari simpul tersebut
• d(v)= din (v) + dout(v)

Contoh :

• Lintasan dari simpul awal v0 kesimpul tujuan vn
• Panjang lintasan adalah jumlah sisi dalam lintasan tersebut
• Sirkuit adalah lintasan yang berawal dan berakhir pada simpul yang sama
• Graf disebut terhubung jika untuk setiap 2 pasang simpul vi dan vj terdapat lntasan dari vi ke vj

Definisi Graf

Definisi Graf

• Graf G=(V,E)
• V=himpunan tdk kosong dari simpul-simpul
• E=himpunan sisi yang menghubungkan sepasang simpul

= { e1, e2, e3,…., en}


Graf

• Untuk menggambarkan obyek diskrit dan hubungan antar obyek
• Misal menggambarkan peta jaringan jalan raya yang menghubungkan sejumlah kota
• Untuk menyelesaikan masalah jembatan Konigsberg pada 1736
• Simpul menyatakan daratan dan sisi menyatakan jembatan
• Masalah: bisakah melalui setiap jembatan tepat sekali dan kembali lagi ketempat semula?

Contoh Sederhana Algoritma (1)

Definisi Algoritma adalah urutan langkah-langkah logis
penyelesaian masalah yang disusun secara sistematis.

Algoritma TUKAR ISI BEJANA

Diberikan dua buah bejana A dan B, bejana A berisi
larutan berwarna merah, bejana B berisi larutan
berwarna biru. Pertukarkan isi kedua bejana itu
sedemikian sehingga bejana A berisi larutan
berwarna biru dan bejana B berisi larutan berwarna
merah.

DESKRIPSI :
– Tuangkan larutan dari bejana A ke dalam bejana B
– Tuangkan larutan dari bejana B ke dalam bejana A.

Algoritma TUKAR ISI BEJANA di atas tidak menghasilkan pertukaran yang benar. Langkah
di atas tidak logis, hasil pertukaran yang terjadi adalah percampuran kedua larutan tersebut.

• Untuk mempertukarkan isi duah bejana, diperlukan sebuah bejana tambahan sebagai tempat penampungan sementara, misalnya bejana C. Maka algoritma untuk menghasilkan pertukaran yang benar adalah sebagai berikut :
Algoritma Tukar Isi Bejana

Diberikan dua buah bejana A dan B, bejana A berisi larutan berwarna merah, bejana B berisi larutan berwarna biru. Pertukarkan isi kedua bejana itu sedemikian sehingga bejana A berisi larutan berwarna biru dan bejana B berisi larutan berwarna merah.

DESKRIPSI :

1. Tuangkan larutan dari bejana A ke dalam bejana C.
2. Tuangkan larutan dari bejana B ke dalam bejana A.
3. Tuangkan larutan dari bejana C ke dalam bejana B.

Dasar dasar ALgoritma

ALGORITMA
Dilihat dari Struktur Sistem Komputer dan Siklus diatas, Algoritma Pemrograman menempati posisi dibagian software dan di bagian implementasi karena bagian implementasi merupakan bagian dimana pemrogram melakukan proses coding (pembuatan program.)


Asal kata Algoritma berasal dari nama Abu Ja’far Mohammed Ibn Musa al-Khowarizmi, ilmuan Persia yang menulis kitab al jabr w’al-muqabala (rules of restoration and reduction) sekitar tahun 825 M


Definisi Algoritma
Algoritma adalah urutan langkah logis tertentu untuk memecahkan suatu masalah. Yang ditekankan adalah urutan langkah logis, yang berarti algoritma harus mengikuti suatu urutan tertentu, tidak boleh melompat-lompat.

Alur pemikiran dalam menyelesaikan suatu pekerjaan yang dituangkan secara tertulis. Yang ditekankan pertama adalah alur pikiran, sehingga algoritma seseorang dapat juga berbeda dari algoritma orang lain. Sedangkan penekanan kedua adalah tertulis, yang artinya dapat berupa kalimat, gambar, atau tabel tertentu.

COntoh :
Jika seseorang ingin mengirim surat kepada kenalannya
di tempat lain, langkah yang harus dilakukan adalah :

1. Menulis surat
2. Surat dimasukkan ke dalam amplop tertutup
3. Amplop ditempeli perangko secukupnya
4. Pergi ke Kantor Pos terdekat untuk mengirimkannya

Contoh :
Algoritma menghitung luas persegi panjang:

Masukkan panjang (P)
Masukkan lebar (L)
Luas = P * L
Tulis L

Jenis Graf

• Graf sederhana: graf tak berarah dengan setiap pasang simpul paling banyak 1 sisi

• Graf ganda : graf tak berarah yang mengandung sisi ganda

• Graf semu : graf tak berarah yang mengandung sisi gelang dan bisa mengandung sisi ganda

Jenis graf menurut orientasi arah

• Graf tak berarah : graf yang sisinya tidak mempunyai orientasi arah

• Graf berarah : graf yang sisinya mempunyai orientasi arah