algoritma
Post on 17-Jan-2016
43 Views
Preview:
DESCRIPTION
TRANSCRIPT
ALGORITMA
Pertemuan Ke-3
Sejarah AlgoritmaAsal kata Algoritma berasal dari nama Abu Ja’far
Mohammed Ibnu Musa al-Khowarizmi, ilmuan Persia yang menulis kitab al jabr w’al-muqabala (rules of
restoration and reduction) sekitar tahun 825 M
Definisi Algoritma
• Urutan langkah-langkah untuk memecahkan masalah
• Urutan logis pengambilan keputusan untuk memecahkan masalah– urutan langkah logis, berarti algoritma harus mengikuti suatu urutan
tertentu, tidak boleh melompat-lompat.
• Alur pemikiran dalam menyelesaikan suatu pekerjaan yang dituangkan secara tertulis.– alur pikiran, yang artinya algoritma seseorang dapat berbeda dari
algoritma orang lain. – tertulis, yang artinya dapat berupa kalimat, gambar, atau tabel tertentu.
• 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.
• Algoritma di butuhkan untuk memerintah komputer mengambil langkah-langkah tertentu untuk menyelesaikan masalah
• Algoritma Pemrograman Program• Agar algoritma dapat memerintah (diproses)
komputer, maka dirubah menjadi bentuk program (melalui proses pemrograman).
Tahap Penyelesaian
Masalah
Masalah
Model
Algoritma
Program
Eksekusi
Hasil
Data
analisis
analisis
analisis
Kriteria Pemilihan Algoritma
1. Ada Output2. Efektifitas dan Efisiensi3. Jumlah Langkahnya Berhingga4. Berakhir 5. Terstruktur
Suatu Algoritma yg terbaik (The Best): “Suatu algoritma harus menghasilkan output yg tepat
guna (efektif) dlm waktu yg relatif singkat & penggunaan memori yg relatif sedikit (efesien)
dgn langkah yg berhingga & prosedurnya berakhir baik dlm keadaan diperoleh suatu
solusi ataupun tdk ada solusinya.“
Contoh:Sebuah prosedur ketika akan mengirimkan surat kepada teman:
1. Tulis surat pada secarik kertas surat2. Ambil sampul surat atau amplop3. Masukkan surat ke dalam amplop4. Tutup amplop surat dengan lem perekat5. Tulis alamat surat yg dituju, jika tdk ingat, lebih
dahulu ambil buku alamat & cari alamat yg dituju, lalu tulis alamat tsb pd amplop surat.
6. Tempelkan perangko pada amplop surat7. Bawa surat ke kantor pos utk diserahkan pd
pegawai pos atau menuju ke bis surat untuk memasukkan surat ke dlm kotak/bis surat.
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
Penulisan Algoritma
• Menggunakan bahasa natural (Bahasa manusia: Indonesia, Inggris)
Kelemahannya masih sering membingungkan (ambigu) / sulit dipahami.
• Menggunakan FlowchartBaik karena alur algoritma dapat dilihat secara visual, tetapi repot pembuatannya jika algoritma panjang
• Menggunakan PseudocodeSudah dekat dengan bahasa pemrograman, tetapi sulit dimengerti oleh orang yang belum tahu pemrograman
– Dengan flowchart / diagram alir
Program Flowchart, yaitu bagan yang menggambar-kan urutan logika dari suatu prosedur pemecahan masalah.
Start
Phi = 3.14
Input(diameter)
Radius = diameter/2Luas = phi * radius * radius
OutputLuas
Stop
12
Flowchart (Diagram Alur)
13
Flowchart
• Bagan-bagan yang mempunyai arus• Menggambarkan langkah-langkah
penyelesaian suatu masalah• Merupakan salah satu cara penyajian
algoritma
14
Tujuan
• Menggambarkan suatu tahapan penyelesaian masalah
• Secara sederhana, terurai, rapi dan jelas• Menggunakan simbol-simbol standar
15
Model / Jenis Flowchart
• System Flowchart• Program Flowchart
16
System Flowchart
• Menggambarkan suatu sistem peralatan komputer yang digunakan dalam proses pengolahan data serta hubungan antar peralatan tersebut
• Tidak digunakan untuk menggambarkan urutan langkah untuk memecahkan masalah
• Hanya untuk menggambarkan prosedur dalam sistem yang dibentuk
17
Keyboard
CPU Disket
VDU
Contoh penggunaan system flowchart
18
Program Flowchart
• Menggambarkan urutan logika dari suatu prosedur pemecahan masalah
• Dua jenis metode penggambaran program flowchart :– Conceptual flowchart, menggambarkan alur
pemecahan masalah secara global– Detail flowchart, menggambarkan alur
pemecahan masalah secara rinci
19
Start
Input
Proses
Output
End
Start
End
Input “Berapa data” ; N
Jml = 0
Input Bil
For K = 1 to N
Print “Jumlah = “; Jml
Jml = Jml + Bil
K=N
20
Simbol-simbol Flowchart
• Flow direction symbols– Digunakan untuk menghubungkan simbol satu dengan
yang lain– Disebut juga connecting line
• Processing symbols– Menunjukan jenis operasi pengolahan dalam suatu
proses / prosedur• Input / Output symbols
– Menunjukkan jenis peralatan yang digunakan sebagai media input atau output
21
Flow Direction Symbols
• Simbol arus / flow– Menyatakan jalannya arus suatu proses
• Simbol communication link– Menyatakan transmisi data dari satu lokasi ke lokasi lain
• Simbol connector– Menyatakan sambungan dari proses ke proses lainnya
dalam halaman yang sama
• Simbol offline connector– Menyatakan sambungan dari proses ke proses lainnya
dalam halaman yang berbeda
22
Processing Symbols
• Simbol process– Menyatakan suatu tindakan (proses) yang dilakukan
oleh komputer• Simbol manual
– Menyatakan suatu tindakan (proses) yang tidak dilakukan oleh komputer
• Simbol decision– Menujukkan suatu kondisi tertentu yang akan
menghasilkan dua kemungkinan jawaban : ya / tidak • Simbol predefined process
– Menyatakan penyediaan tempat penyimpanan suatu pengolahan untuk memberi harga awal
• Simbol terminal– Menyatakan permulaan atau akhir suatu program
23
Processing Symbols
• Simbol keying operation– Menyatakan segal jenis operasi yang
diproses dengan menggunakan suatu mesin yang mempunyai keyboard
• Simbol offline-storage– Menunjukkan bahwa data dalam simbol
ini akan disimpan ke suatu media tertentu
• Simbol manual input– Memasukkan data secara manual dengan
menggunakan online keyboard
24
Input / Output Symbols
• Simbol input/output– Menyatakan proses input atau output tanpa
tergantung jenis peralatannya• Simbol punched card
– Menyatakan input berasal dari kartu atau output ditulis ke kartu
• Simbol magnetic tape– Menyatakan input berasal dari pita magnetis
atau output disimpan ke pita magnetis• Simbol disk storage
– Menyatakan input berasal dari dari disk atau output disimpan ke disk
25
Input / Output Symbols
• Simbol document– Mencetak keluaran dalam bentuk
dokumen (melalui printer)
• Simbol display– Mencetak keluaran dalam layar
monitor
26
Contoh System Flowchart
Data jawaban ujian
Koreksi
Daftar Koreksi Data File
utama ujian
Periksa Ujian
Tabel Siswa
File siswa lulus
Laporan Hasil Ujian
27
Kaidah Pembuatan Flowchart
Start
Input
Proses
Output
End
28
Pengolahan data
START
READ
HABIS ?
PROCESS
WRITE
END
Tidak
Ya
29
Input lebar
Menghitung luas persegi panjang
Start
End
Input panjang
Luas panjang * lebar
Print Luas
Bagaimana menyatakan suatu algoritma (menulis algoritma)– Dengan psudocode
Suatu cara penulisan algoritma agar ide dan logika dari algoritma dapat disampaikan/diekspresikan menggunakan gaya bahasa pemrograman tertentu.
Phi 3.14Input (diameter)Radius diameter / 2Luar phi * radius * radiusOutput (Luas)End
Tahap Analisa Algoritma
1. Bagaimana merencanakan algoritma 2. Bagaimana menyatakan suatu algoritma (menulis
algoritma)3. Bagaimana validitas suatu algoritma.4. Bagaimana Menganalisa suatu Algoritma.5. Bagaimana Menguji Program dari suatu Algoritma
Bagaimana merencanakan algoritma
Dengan Mendefinisikan masalah.
Contoh : Permasalahan menghitung luas lingkaran, dengan data yang diketahui adalah diameter lingkaran.
Rumus : ∏ . r2 dengan Phi = 3.14 atau 22/7.
Tahap Proses Uji Algoritma
1. Pengujian Tahap DebugingUntuk mengecek kesalahan program, Baik sintaksis maupun logika.
2. Pengujian Tahap ProfilingUntuk menentukan waktu tempuh dan banyak nya memori program yang digunakan.
Analisis Suatu Algoritma
Untuk melihat effisiensi dan efektifitas dari suatu algoritma, dapat dilihat dari:
1. Waktu Tempuh dari Suatu Algoritma2. Jumlah memori yang digunakan
Hal-hal yang dapat mempengaruhi waktu tempuh adalah :1. Banyaknya langkah.2. Besar dan jenis input data.3. Jenis Operasi.4. Komputer dan kompilator
Sifat - Sifat Algoritma
Aspek Penting Algoritma :• Finite algoritma harus berhenti setelah
mengerjakan sejumlah langkah terbatas• Definite setiap langkah didefinisikan secara tepat,
tidak boleh membingungkan (ambigu)• Input sebuah algoritma memiliki nol/lebih input
sebelum dijalankan• Output algoritma memiliki satu/lebih output, yang
biasanya bergantung kepada input• Effective setiap algoritma diharapkan memiliki sifat
efektif. (setiap langkah harus sederhana dan sehingga dapat dikerjakan dalam waktu yang masuk akal)
Algoritma TUKAR ISI BEJANADiberikan dua buah bejana A dan B, bejana A berisilarutan berwarna merah, bejana B berisi larutanberwarna biru. Pertukarkan isi kedua bejana itusedemikian sehingga bejana A berisi larutanberwarna biru dan bejana B berisi larutan berwarnamerah.DESKRIPSI :– Tuangkan larutan dari bejana A ke dalam bejana B– Tuangkan larutan dari bejana B ke dalam bejana A.Benar ??
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.
Langkah-langkah yang membentuk suatu algoritma dapat dibagi menjadi 3 kelompok proses:
1. Sequence Process instruksi dikerjakan secara berurutan satu persatu dimulai dari langkah pertama sampai terakhir.
2. Selection Process instruksi pemilihan proses (percabangan), sehingga apabila memenuhi persyaratan tertentu maka instruksi akan dikerjakan.Contoh : jika pembayaran tunai diberi diskon 10%Jika dilakukan secara kredit maka diskon 0 %.(dalam pernyataan diatas, hanya boleh melakukan 1 instruksi dari 2 alternatif instruksi.
3. Iteration Process suatu instruksi yang dikerjakan berulang-ulang selama beberapa kali selama masih memenuhi suatu kondisi.
SEQUENCE
• Sebuah runtutan terdiri dari satu atau lebih intruksi.
• Intruksi dilaksanakan setelah intruksi sebelumnya dilaksanakan.
• Urutan intruksi menentukan keadaan akhir algoritma.
1 2 3 4A1 A2 A3 A4
SELECTION
Berlaku untuk suatu kasus yang disertai syarat tertentu.
- If kondisi then aksi- If kondisi then aksi 1 else aksi 2
Contoh: Buat sebuah algoritma untuk memilih bilangan terbesar dari 3 buah bilangan
Penyelesaian:
Maks = bilangan pertama If x > y then if x> y then tulis x sebagai bilangan terbesar
else tulis y sebgai bilangan terbesar
Else if y> z then tulis y sebagai bilangan terbesar else tulis z sebagai bilangan terbesar
REPETITION
Kondisi yang dilaksanakan secara berulang-ulang.1. For …….. Do
for kondisi do aksi
Contoh:Buatlah algoritma untuk memunculkan tulisan “ saya siswa SMA 1 Yogyakarta” sebanyak 700 kali.
Algoritma menulis_700 kalimat Menulis kalimat saya siswa SMA 1 Yogyakarta sebanyak 700
kali
Deskripsi:1.Tulis kalimat “saya siswa SMA 1 Yogyakarta”2.Tulis kalimat “saya siswa SMA 1 Yogyakarta”3.Tulis kalimat “saya siswa SMA 1 Yogyakarta”..699. Tulis kalimat “saya siswa SMA 1 Yogyakarta”700. Tulis kalimat “saya siswa SMA 1 Yogyakarta”
Algoritma menulis_700 kalimat Menulis kalimat saya siswa SMA 1 Yogyakarta sebanyak 700
kali
Deskripsi:
for I dari 1 to 700 dotulis kalimat “saya siswa SMA 1 Yogyakarta”
selesai
2. Repeat … untilrepeat
aksiuntil kondisi
Contoh:Pencarian data dalam tabelNis Nama Telepon12345 Hardian 0812xxxxxx12346 Ananto 0818xxxxxx12347 Ahmad 0899xxxxxx … …… ………….12500 Widuri 081321xxxx
Algoritma Pencarian data dalam tabelSebuah tabel berisi nis, nama dan telepon siswa. Carilah dalam tabel alamat seorang siswa dengan nis = x.diasumsikan tabel berisi minimal satu entry.
Deskripsi:tinjau entry pertama tabelrepeat
if nis pada entry tabel=nis yang dicari thenambil data nomor telepon dari nis tersebut
else tinjau entry berikutnya dalam tabelUntil nis yang dicari ditemukan atau akhir tabel sudah
terlampaui
3. While …. Dowhile kondisi do
aksi
Algoritma Pencarian data dalam tabelSebuah tabel berisi nis, nama dan telepon siswa. Carilah dalam tabel alamat seorang siswa dengan nis = x.diasumsikan tabel berisi minimal satu entry.
Deskripsi:tinjau entry pertama tabelwhile nis yang dicari belum ditemukan dan akhir tabel berlum terlampaui do
if nis pada entry tabel=nis yang dicari thenambil data nomor telepon dari nis tersebut
else tinjau entry berikutnya dalam tabel
Latihan
• Buatlah algoritma dengan menggunakan bahasa natural (bahasa sehari-hari / pseudocode )
1. Buat langkah untuk melakukan penggantian ban mobil yang pecah ( tanpa ada masalah / syarat ).
2. Dari Soal diatas dikembangkan kembali, mis : bila ban serep kempes atau ban serep bocor.
Latihan cont
• Buatlah algoritma (dengan bahasa natural):
1. Menampilkan bilangan ganjil dari 1 sampai dengan 10.
2. Menghitung jumlah deret : 1 + 2 + 3 + 4 + .... + NN = jumlah maksimum suatu nilai yang dimasukkan.
3. Buatlah algoritma sebuah lampu pengatur lalu lintas.
ATURAN PENULISAN ALGORITMA
a. Kepala Program : Judul Algoritmab. Deklarasic. Deskripsi
Struktur Badan Algoritma
• Kepala Program– Berisi judul program dan keterangan tentang
program– Bahasa Algoritma : Algoritma judul_program
• Ex. Algoritma menghitung_luas_segitiga • Ex. Algoritma MenghitungLuasSegitiga
– Bisa ditambahkan komentar tentang program dengan menggunakan operator “{ }”
Struktur Badan Algoritma (2)
• Deklarasi– Berisi variabel yang digunakan dalam program– Bahasa Algoritma : nama_variabel : Tipe Data
• Ex. AlasSegitiga : integer• Ex. TinggiSegitiga : integer• Ex. LuasSegitiga : integer
Struktur Badan Algoritma (3)
• Deskripsi– Berisi uraian langkah penyelesaian– Example:
read(PanjangSegitiga)read(LebarSegitiga)LuasSegitiga ← ½ * PanjangSegitiga * LebarSegitigawrite(LuasSegitiga)
Struktur Badan Algoritma (4)Algoritma menghitung_luas_segitiga{menghitung luas segitiga dengan inputan alas dan tinggi segitiga berasal dari keyboard}
DEKLARASIAlasSegitiga : IntegerTinggiSegitiga : IntegerLuasSegitiga : Integer
DESKRIPSIread(AlasSegitiga)read(TinggiSegitiga)
LuasSegitiga ← ½ * AlasSegitiga * TinggiSegitiga
write(LuasSegitiga)
Program menghitung_nilai_rata_rata;
Var x:integer;N:integer;K:integer;jumlah:integer;rata:real;
Beginwrite(‘masukan jumlah data: ‘); readln(N);k:=1;jumlah:=0;while k<= N do
begin write(x= ?); readln(x); jumlah:=jumlah + x; k:=k+1;end;
rata:=jumlah/N;writeln(‘rata-rata seluruh data= ‘, rata);
End.
Kasus
• Deklarasi data untuk mobil – Merk : String {Contoh: Honda}– NoKendaraan : String {Contoh: KH1A}– TahunProduksi : Integer {Contoh: 2007}
• Deklarasi data untuk Mata kuliah• Deklarasi data untuk Waktu
• Deklarasi data untuk Alamat Rumah• Deklarasi data untuk Data Pribadi <min 6
variabel>
TIPE, NAMA, DAN NILAI
Tipe DataTipe data terdiri dari tipe:• Tipe dasar
– Tipe yang dapat langsung dipakai (disediakan oleh bahasa pemrograman)
– Contoh: boolean, integer, real, char, string (?)• Tipe bentukan
– Tipe yang didefinisikan sendiri oleh pemrogram– Tipe yang dibentuk dari tipe dasar atau dari tipe bentukan
lain yang sudah didefinisikan– Contoh: tipe dasar yang diberi nama tipe baru, record
Tipe Data(2)
Empat hal yang harus diperhatikan dalam pendefinisian tipe:
• Nama• Domain harga (nilai)• Konstanta• Operator
Tipe Data(3)
Tipe Bentukan• Tipe dasar yang diberi nama tipe baru
– Nama baru untuk tipe dasar menggunakan kata kunci type– Domain nilai, cara menulis konstanta, dan operasi-operasi yang dapat
dijalankan pada tipe baru tersebut tidak berubah, sama seperti tipe dasarnya.
– Contoh: type BilanganBulat: integer• Rekaman (record)
– Rekaman disusun atas satu atau lebih field– Tipe field menyimpan data dan tipe dasar tertentu atau dari tipe
bentukan lain yang sudah didefinisikan sebelumnya– Nama rekaman ditentukan oleh pemrogram– Rekaman disebut juga tipe terstruktur
Contoh RecordDEKLARASItype MataKuliah : record <KodeMK : string, {kode matakuliah}
NamaMK : string, {nama matakuliah} Nilai : char {indeks nilai}>
type Mahasiswa : record <NIM : integer, {nomor mhs} NamaMhs : string, {nama mhs} MK : array[1..4] of MataKuliah>
LarikMhs : array[1..100] of Mahasiswa
Nama• Untuk mengidentifikasikan dan membedakan obyek• Unik dan tidak boleh sama• Dalam algoritma nama diberikan pada:
– Variabel• Tempat penyimpanan data/informasi di memori yang nilainya dapat
diubah selama pelaksanaan program– Konstanta
• Tempat penyimpanan di memori yang nilainya tidak dapat diubah selama pelaksanaan program
– Tipe bentukan• Tipe data baru yang didefinisikan oleh program dari tipe data yang sudah
ada– Prosedur
• Modul program (sederetan instruksi) yang ditulis terpisah dari badan program utamadan dapat dipanggil berulang dari program utama
– Fungsi• Prosedur yang mengembalikan suatu nilai dengan tipe data sederhana
Aturan Penulisan Nama• Harus dimulai dengan huruf alfabet, tidak boleh dimulai
dengan angka, spasi, atau karakter khusus lainnya.• Tidak case sensitif (beda dengan bahasa pemrograman)• Karakter penyusun nama hanya boleh: huruf alfabet, angka
dan “_” (underscore)• Tidak boleh dipisahkan dengan spasi• Panjang nama tidak terbatas• Semua nama yang dipakai harus dideklarasikan dulu pada
bagian deklarasi
Contoh Penamaan• SALAH
– 6titik {dimulai dg angka}– nilai ujian {dipisahkan spasi}– PT-1 {mengandung operator kurang}– hari! {mengandung karakter khusus}
• BENAR– titik6 atau titik_6– nilai_ujian atau nilaiUjian– PT_1 atau PT1– hari
Nilai• Merupakan besaran dari tipe data yang sudah didefinisikan
(tipe dasar maupun tipe bentukan)• Nilai dapat berupa:
– Isi variabel atau konstanta– Nilai dari hasil perhitungan– Nilai yang dihasilkan oleh fungsi
• Nilai yang disimpan di variabel dimanipulasi dengan cara:– Mengisikan ke variabel lain yang bertipe sama– Dipakai untuk perhitungan– Dituliskan ke piranti keluaran
Nilai(2)Pengisian nilai ke variabel:• Pengisian nilai secara langsung(assignment)
– Memasukkan sebuah nilai ke dalam nama variabel langsung di dalma teks algoritma
– Syaratnya nilai yang didisikan harus bertipe sama dengan tipe peubah– Notasi: – Contoh:
variabel konstanta NoMhs 1234
variabel1 variabel2 Nil_prev Nil_cur
variabel ekspresi Luas 0.5 * p * l
Nilai(3)
• Pembacaan nilai dari piranti masukan– Nilai untuk nama variabel dapt diisi dari piranti
masukan, misalnya dari keyboard.– Dinamakan dengan operasi pembacaan data– Notasi dalam teks algoritma: read– Contoh:
• read (nama1, nama2,…namaN)
Ekspresi• Ekspresi terdiri atas: operand dan operator• Operand adalah nilai yang dioperasikan dengan
operator tertentu• Operand dapat berupa konstanta, nama variabel,
nama konstanta, atau hasil suatu fungsi• Hasil evaluasi dari sebuah ekspresi adalah nilai di
dalam domain yang sesuai dengan tipe operand yang dipakai, ada tiga macam: ekspresi aritmetik, ekspresi relasional, ekspresi string.
Ekspresi(2)• Ekspresi Aritmetika
– Ekspresi yang baik operand dan hasilnya berupa numerik– (ingat: tingkat prioritas operator)
i. / , div, modii. *iii.+, -
• Ekspresi relasional– Ekspresi dengan operator <,≤,>,≥,=,≠, not, and, or, dan xor– Hasil evaluasi adalah nilai bertipe boolean– Ekspresi string
Ekspresi (3)
• Ekspresi string• Ekspresi dengan operator
penyambungan/concatenation “+”.
Menuliskan Nilai ke Piranti Keluaran (monitor/printer)
• Dilakukan dengan notasi write• Contoh:
– write (nama1, nama2, …, namaN)
Contoh AlgoritmaAlgoritma Hello_World{mencetak string Hello World diikuti nama orang. Nama orang diinputkan
dari piranti masukan}
DEKLARASIconst ucapan = ‘Hello World’
namaUser : string
DESKRIPSIread(namaUser)write(ucapan + ‘ ‘ + namaUser)
BAHASA PEMROGRAMAN
• Program harus ditulis dalam suatu bahasa yang dimengerti oleh komputer yaitu dalam Bahasa pemrogram dibedakan menjadi : – Bahasa tingkat rendah (low level language) : bahasa yang berorientasi ke mesin. – Bahasa tingkat tinggi (high level language) : bahasa yang berorientasi ke manusia (seperti bahasa inggris) contoh bahasa Pascal, bahasa C dll.
BAHASA PEMROGRAMAN• Program yang ditulis dalam bahasa pemrograman akan diterjemahkan ke dalam bahasa mesin (kenal dengan biner digit) dengan menggunakan penterjemah. Penterjemah : – Interpreter : menterjemahkan baris per baris instruksi. Contoh bahasa Basic. – Compiler : menterjamahkan setelah seluruh instruksi ditulis. Contoh bahasa Pascal, C, C++, dll.
TERIMAKASIH
top related