trivia dan penghantar

5/17/2018 trivia Dan Penghantar - slidepdf.com

http://slidepdf.com/reader/full/trivia-dan-penghantar 1/33

Apr 25, 2012

Analisis dan PerancanganAlgoritma

E. Haodudin Nurkifli

Teknik Informatika

Universitas Ahmad DahlanKuliah 0 : Administrative dan Introduction

27 Februari 2010


http://slidepdf.com/reader/full/trivia-dan-penghantar 2/33Eko AB – Analisis dan Perancangan Algoritma 2

Perkenalan

Nama : E. Haodudin Nurkifli

Alamat Asal: Karawang Jawa barat

Alamat yogya : Jl mondoliko 836 UH II

Yogyakarta

E-mail : [email protected]

mailto:[email protected]

mailto:[email protected]



RENCANA HARI INI

Admistrivia

Kuliah

Tugas Individu dan Tugas Kelompok (presentasi)

Praktikum Ujian

Pengantar

Masalah, apa itu algoritma, perancangan, analisis

algoritma



ADMINISTRIVIA



Buku Pegangan

Fundamental Of Algorithmics (Gilles Brassard and

Paul Bratley

Perancangan & Analisis Algoritma (Eko Budi

Purwanto) Algoritma dan Pemrogramman (Rinaldi Munir)

Modul Analisis dan Perancangan Algoritma (......)



Slide dan Tugas

Slide

Akan saya berikan dalam bentuk file

Slide, tugas dan lain lain

http://informatikauad.wordpress.com/ Dalam format ppt

Membuat millis ?.. Sebagai forum sering dan kumpul

tugas.

http://informatikauad.wordpress.com/

http://informatikauad.wordpress.com/



Tugas

Tugas Individu (latihan)

Latihan 2 kali sebelum mid dan 2 kali setelah mid soal

latihan dapat di download di blog dan dikumpul berupa

hardcopy. Tugas Kelompok (Presentasi)

Tugas berupa makalah dan dipresentasikan (setiap

orang wajib presentasi).

Quiz

Dilaksanakan 2 kali, 1 kali sebelum mid dan 1 kali

setelah mid ( pelaksanaan quiz tergantung saya dan

tidak diberitahukan).



Ujian

MidTerm ???

Ujian Akhir ???

Nilai Akhir Numerik

Nilai Akhir Huruf



Persentase

Tugas Individu dan Tugas kelompok 20 %

Quiz 15 %

Praktikum 15 %

Midterm 20 % Ujian Akhir (UAS) 30 %



Nilai Akhir dan Numerik

Nilai Akhir Numerik

( 20 x Tgs Individu dan Kelompok + 15 x Quiz + 15 x

Praktikum + 20 x Midterm + 30 x UAS) / 100

Nilai Akhir Huruf

o 100-85 : A

o 84-70 : B

o 69- 50 : C

o 49- 30 : D

o < 29 : E



Materi

Introduction

Iteratif and rekursif

Complexcity

Devide and conquare (bagi dan gabung) Greedy

back tracking (Runtut balik)

Pembatasan dan pencabangan



Goal

Mampu mengklasifikasikan algoritma berdasarkan

gagasan yang mendasarinya

Mampu membuat algoritma yang baik dan benar

Mengimplementasikan



Peraturan Tambahan

Kehadiran diusahakan 100 % tetapi diperbolehkan

minimum 75 %. < 75 % tidak diperbolehkan mengikuti

UAS.

Pakaian Rapi dan pakai sepatu 15 Menit dosen tidak datang berarti kosong dan

diganti pada hari lain

15 menit mahasiswa belum masuk dianggap tidak

hadir NB :

Nilai kurang, ada subjektifitas dosen dilihat dari presensi

/ kehadiran mahasiswa.



Tulis yang anda ingikan dari saya dengan 3 kalimat.



KULIAH SERIUS



Eko AB – Analisis dan Perancangan Algoritma 16

Masalah (Problem)

Masalah atau Probelm : pertanyaan atau tugas yang

kita cari jawabanya.

Contoh-contoh masalah :

1. [ Masalah Pengurutan] : diberikan senarai (list ) S yangtediri dari n buah data bilangan bulat. Bagaimana

mengurutkan n buah data tersebut sehingga terurut

secara menaik ?.

Jawaban dari masalah ini: barisan nilai di dalam senaraiyang terurut menaik.




2 [Masalah pencarian] Tentukan apakah suatu

bilangan x terdapat di dalam sebuah senarai S yang

beriri n buah bilangan bulat!

Jawaban dari masalah ini: “ya” jika x ditemukan

di dalam senarai, atau “tidak” jika x tidak terdapat

di dalam senarai.




Instansiasi masalah: parameter nilai yang

diasosiasikan pada masalah.

Jawaban terhadap instansiasi masalah disebut solusi

Contoh: Selesaikan masalah pengurutan untuk

S = [15, 4, 8, 11, 2, 10, 19] n = 7

Solusi: S = [2, 4, 8, 10, 11, 15, 19].




Algoritma

Untuk masalah dengan instansiasi yang besar,

solusinya menjadi lebih sulit.

Perlu sebuah prosedur umum yang berisilangkahlangkah penyelesaian masalah -> algoritma

Algoritma:urutan langkah-langkah untuk

memecahkan suatu masalah




Definisi lain dari algortima :

Algoritma adalah deretan langkah-langkah komputasi

yang mentransformasi data masukan menjadi data

keluaran [COR92]

Algoritma adalah deretan instruksi yang jelaskan untukmemecahkan masalah, yaitu untuk memperoleh

keluaran yang diinginkan dari suatu masukan dalam

jumlah waktu yang terbata[LEV03].

Algoritma adalah prosedur komputasi yang terdefinisi

dengan baik yang menggunakan beberapa nilai

sebagai masukan. Jadi, algoritma adalah deretan

langkah komputesi yang mentranformasikan masukan

menjadi keluaran [COR89].




Algoritmaik : Studi mengenai Algoritma

Notasi apapun dapat digunakan untuk menuliskan

algoritma asalkan mudah dibaca dan dipahami.

Algoritma dapat ditulis dengan notasi :1. Kalimat-kalimat deskriftif (bahasa natural)

2. Bagan alir (flow chart)

3. Pseudo-code (gabungan antara bahasa alami dengan

bahasa pemrograman)




Contoh :

Buatlah algoritma terbesar dari 3 buah bilangan :

Dengan kalimat deskriftif / bahasa Natural

1. Ambilah bilangan pertama dan set maks sama dengan bilanganpertama

2. Ambil bilangan kedua dan bandingkan dengan maks

3. Apabila bilangan kedua lebih besar dari mask, set maks sama

dengan bilangan kedua

4. Ambil bilangan ketiga dan bandingkan dengan maks

5. Apabila bilangan ketiga lebih besar dari maks, set maks sama

dengan bilangan ketiga

6. Variabel maks berisi bilangan terbesar. Tampilkan




flowchart




Dengan Pseudo-code

Maks ←bilangan pertama

if (maks < bilangan kedua)

maks←bilangan kedua

if (maks < bilangan ketiga) maks ← bilangan ketiga




Analis Algoritma

Sebuah algoritma tidak hanya harus benar, tetap juga

harus mangkus (efficient).

Ukuran kemangkusan algoritma : waktu dan ruangmemori (space)

Algoritma yang mangkus : algoritma yang

meminimumkan kebutuhan waktu dan ruang.




Alat ukur kemangkusan algoritma :

1. Kompleksitas waktu, T(n)

2. Kompleksitas ruang, S(n).

n= ukuran masukan yang diproses oleh algoritma

T(n) : jumlah operasi yang dilakukan untuk

menjalankan sebuah algoritma sebagai fungsi dari

ukuran masukan n.

S(n): ruang memori yang dibutuhkan algotima sebagai

fungsi dari ukutan masukan n.




Operasi yang dihitung hanyalah operasi dasar (basic

operation) saja

Operasi dasar : operasi khas yang mendasari suatu

algoritma. Misalnya :

1. Operasi perbandingan elemen pada algoritma

pengurutan / pencarian

2. Operasi penjumlahan dan perkalian pada algortimaperkalian matriks




Kompleksitas waktu asimtotik :

1. Perkiraan kasar kebutuhan waktu algoritma dengan

meningkatkan nilai n

2. Menyatakan laju pertumbuhan waktu, bukanmenyatakan jumlah operasi dasar.

Tiga cara menyatakan waktu asimtotik :

1. O(f(n)) : untuk batas atas laju kebutuhan waktu

2. Ω (g(n)) : untuk batas bawah laju kebutuhan waktu3. Ѳ (h(n)) : jika f(n)=g(n) (Ѳ=theta)




Perancangan Algoritma

Diluar negeri dikenal dengan (algorthm Design

Techniques)

Perancangan algoritmik : pendekatan umum untuk

memecahkan masalah secara algoritmis yang dapat

diterapkan pada beraneka ragam masalah guna

mencapai tujuan.

Perancangan algoritmik bertujuan mencari algoritma

yang mangkus untuk memecahkan masalah

Ukuran kemangkusan algoritma dinyatakan dengan

notasi O, Ω,Ѳ




2 alasan mempelajari

Memberikan panduan untuk merancang algoritma bagi

masalah baru.

Menklasifikasikan algoritma berdasarkan gagasanperancangan yang mendasarinya.




Klasifikasi Perancangan Algoritmik

Perancangan Solusi Langsung (direct solution

strategies)

1. Algoritma Brute Force

2. Algoritma Greedy

Perancangan berbasis pencarian pada ruang status

(state-space base strategies)

1. Algoritma Backtracking2. Algoritma Branch and Bound




Perancangan solusi atas-bawah (top-down solution

strategies )

- Algoritma Devide and Conquer

Perancangan solusi bawah atas (bottom up solutiion

strategies).

- Dynamic Ptogramming

Catatan : klasifikasi ini tidak kaku, bisa berbeda

bergantung pendekatan yang di gunakan.



Ek AB A li i d P Al it

Beberapa Masalah Klasik

Travelling salesperson Problem (TSP)

Knapsack (1/0)

Persoalan N-Ratu

Graf coloring

trivia dan penghantar

Documents