IKG2A3/ Pemrograman Terstruktur 2 ZK Abdurahman Baizal KK Algoritma dan Komputasi
Mesin Abstrak
1
8/25/2015
Mesin Abstrak Definisi: mesin yang dianggap ada, dan diasumsikan mampu melakukan mekanisme yang didefinisikan untuk mesin tersebut. Mesin abstrak memungkinkan programmer untuk melakukan pemecahan masalah secara bertahap Mendefinisikan mesin abstrak berarti mendefinisikan: – sekumpulan state yang mungkin – sekumpulan aksi primitif 2
8/25/2015
IKG2A3 Pemrograman Terstruktur 2
Macam Mesin Abstrak yang Akan Dibahas Mesin Karakter Mesin Couple Mesin Kata
3
8/25/2015
Me-reuse primitive pada mesin karakter
MESIN KARAKTER
4
8/25/2015
Mesin Karakter Pita berisi deret karakter, yang diakhiri dengan ‘.’ (titik), pita yang hanya berisi ‘.’ disebut sebagai pita kosong Tombol START, ADV Sebuah lampu EOP (End Of Pita) “Jendela” yang ukurannya sebesar satu karakter. karakter yang sedang pada jendela dinamakan CC (Current Character) 5
8/25/2015
Mesin Karakter (lanjutan) Lampu EOP menyala jika CC = ‘.’ Tombol START dan ADV digunakan untuk mengubah state mesin Mesin hanya dapat dioperasikan jika EOP tidak menyala E
Start Adv 6
8/25/2015
eof
Primitive untuk Merubah Posisi Pita Procedure START {Mesin siap dioperasikan. Pita disiapkan untuk dibaca. Karakter pertama yang ada pada pita posisinya adalah pada jendela I.S. : Sembarang F.S. : CC adalah karakter pertama pada pita, Jika CC ≠ ‘.’ maka EOP akan padam (false) Jika CC = ‘.’ maka EOP akan menyala (true) }
7
8/25/2015
Primitive untuk Merubah Posisi Pita Procedure ADV {Pita dimajukan satu karakter I.S. : karakter pada jendela = CC, CC ≠ ‘.’ F.S. : CC adalah karakter berikutnya dari CC yang lama, CC mungkin = ‘.’ jika CC = ‘.’ maka EOP akan menyala (true) }
8
8/25/2015
Menghitung jumlah huruf pada pita Program COUNTHURUF {SKEMA PEMROSESAN DENGAN MARK} Kamus : Algoritma : RESET {Inisialisasi, CI = 0} START {First_Elmt} while (CC ≠ ‘.’} do {not EOP} INCR {Proses : CI=CI+1} ADV ← {Next_Elmt} {CC = “.”} Output (CI) {Terminasi} 9
8/25/2015
Program COUNT_A {SKEMA PEMROSESAN DENGAN MARK:Menghitung banyaknya huruf A pada pita karakter} Kamus : Algoritma : RESET {Inisialisasi, CI = 0} START {First_Elmt} while (CC ≠ ‘.’} do {not EOP} depend on CC {Proses} CC = ‘A’ : INCR CC ≠ ‘A’ : ADV {Next_Elmt} {CC = “.”} Output (CI) {Terminasi}
10
8/25/2015
Program COUNT_A-2 {SKEMA PEMROSESAN dengan penanganan kasus kosong} Kamus : Algoritma : START {First_Elmt} depend on CC CC = ‘.’ : Output (‘Pita kosong’} CC ≠ ‘.’ : RESET {Inisialisasi, CI = 0} repeat depend on CC {Proses} CC = ‘A’ : INCR CC ≠ ‘A’ : ADV {Next_Elmt} until CC =’.’ Output (CI) {Terminasi}
11
8/25/2015
Menghitung frekuensi huruf ‘a’ Program FREKA-1 {SKEMA PEMROSESAN DENGAN MARK, tanpa penanganan kasus kosong} Kamus : Algoritma : CPT_KAR ← 0 {Inisialisasi} CPTA ← 0 {Inisialisasi} START {First_Elmt} while (CC ≠ ‘.’) do CPT_KAR ← CPT_KAR + 1 depend on CC CC = ‘A’ : CPTA ← CPTA + 1 CC ≠ ‘A’ : ADV {Next_Elmt} {CC = ‘.’ : semua karakter pada pita sudah dibaca, mungkin CPT_KAR = 0} {Terminasi} depend on CPT_KAR CPT_KAR ≠ 0 : Output (CPT_A/CPT_KAR) CPT_KAR = 0 : Output (‘Frekuensi tidak terdefinisi’)
12
8/25/2015
Program FREKA-2 {SKEMA PEMROSESAN DENGAN MARK, dengan penanganan kasus kosong Kamus : CPT-KAR : Integer {banyaknya karakter pada pita yang sudah dibaca} CPTA : Integer {banyaknya huruf A yang muncul pada bagian pita yang sudah dibaca} Algoritma : START {First_Elmt} if CC = ‘.’ then output (‘Pita kosong’) else {CC ≠ ‘.’) CPT_KAR ← 0 {Inisialisasi} CPTA ← 0 {Inisialisasi} repeat CPT_KAR ← CPT_KAR + 1 if (CC = ‘A’) then CPTA ← CPTA + 1 {else (CC ≠ ‘.’) → do nothing} ADV {Next_Elmt} until (CC = ‘.’) output (CPTA/CPT_KAR) {Terminasi, CPT_KAR pasti tidak nol) 13
8/25/2015
Kasus Diberikan sebuah mesin karakter dengan pita berisi karakter (mungkin kosong). Buatlah algoritma untuk menghitung banyaknya pasangan dua huruf ‘LE’ yang ada pada pita tersebut HITUNG-LE, versi 2 : – Ide → mengingat-ingat jika menemukan ‘L’, dan memeriksa karakter selanjutnya – Realisasi menggunakan mesin karakter
14
8/25/2015
Program COUNTLE-2 {SKEMA PEMROSESAN DENGAN MARK} {Solusi 2: Memorisasi satu karakter sebelum karakter yang ada di jendela} Kamus : CPTLE : Integer {banyaknya ‘LE’ pada bagian pita yang sudah dibaca} Prec-Is-L : boolean {true jika karakter sebelum CC adalah ‘L’} Algoritma : Prec-Is-L ← false {inisialisasi} CPTLE ← 0 {inisialisasi} START {First_Elmt} while CC ≠ ‘.’ do Prec-Is-L ← CC = ‘L’ ADV {Next_Elmt} if CC = ‘E’ and Prec-Is-L then CPTLE = CPTLE + 1 Output (CPTLE) {Terminasi} 15
8/25/2015
Program COUNTLE-3 {SKEMA PEMROSESAN DENGAN MARK} {Solusi 3: majukan pita sampai ketemu ‘L’, periksa karakter berikutnya. Proses ini diulang sampai seluruh karakter selesai diproses}: Kamus : CPTLE : Integer {banyaknya ‘LE’ pada bagian pita yang sudah dibaca} Algoritma : CPTLE ← 0 START {First_Elmt} while (CC ≠ ‘.’) do {Cari sampai ketemu ‘L’, namun mungkin ketemu ‘.’} while (CC ≠ ‘L’) and (CC ≠ ‘.’) do ADV {CC = ‘L’ or CC = ‘.’} if (CC = ‘L’ and CC = ‘.’) then ADV {Boleh ADV, karena CC bukan‘.’} if CC = ‘E’ then CPTLE ← CPTLE + 1 {else : CC ≠ ‘L’ : -} {CC = ‘.’, seluruh karakter pada pita sudah dibaca} Output (CPTLE) {Terminasi} 16
8/25/2015
HITUNG-LE versi-3 : – Ide → maju terus sampai menemukan ‘L’, dan memeriksa karakter berikutnya – Realisasi menggunakan Mesin Karakter
17
8/25/2015
MESIN COUPLE
18
8/25/2015
Kembali ke kasus hitung LE : – Diberikan sebuah mesin karakter dengan pita berisi karakter (mungkin kosong). Buatlah algoritma untuk menghitung banyaknya pasangan dua huruf ‘LE’ yang ada pada pita tersebut
HITUNG-LE Versi 3 : – Realisasi dengan membuat mesin couple : mesin yang mampu untuk menampilkan dua karakter sekaligus berdasarkan mesin karakter.
19
8/25/2015
Program COUNTLE-1 {SKEMA PEMROSESAN DENGAN MARK} {Solusi 1: Mesin COUPLE}: Kamus : CPTLE : Integer {banyaknya ‘LE’ pada bagian pita yang sudah dibaca} C1, C2 : character {C1, C2 adalah Couple} procedure START-COUPLE {mendapatkan couple yang pertama} {I.S. : sembarang } {F.S. : Couple pertama terbentuk : C1 = ‘ ‘, C2 = CC, CC mungkin = ‘.’} procedure ADV-COUPLE {next-couple} {I.S. : C1 dan C2, C2 ≠ ‘.’} {F.S. : C1 = C2, C2 = CC, CC mungkin = ‘.’} Algoritma : START-COUPLE {First_Elmt} CPTLE ← 0 while (CC ≠ ‘.’) do {not End-Couple} if (C1 = ‘L’ and C2 = ‘E’) then CPTLE ← CPTLE + 1 {couple ‘LE’} {else : C1 ≠ ‘L’ or C2 ≠ ‘E’ : -} ADV-COUPLE {Next_Elmt} Output (CPTLE) {Terminasi}
20
8/25/2015
Primitive pada Mesin Couple Procedure START-COUPLE {SKEMA PEMROSESAN DENGAN MARK, Solusi 1 : mesin COUPLE}: {I.S. : sembarang } {F.S. : Couple pertama terbentuk : C1 = ‘ ‘, C2 = CC, CC mungkin = ‘.’} Kamus : Algoritma : C1 ← ‘ ‘ {karena yang dicari adalah ‘LE’, Bagaimana jika yang dicari pasangan lain?} START C2 ← CC
21
8/25/2015
Primitive pada Mesin Couple procedure ADV-COUPLE {SKEMA PEMROSESAN DENGAN MARK, Solusi 1 : mesin COUPLE}: {I.S. : C1 dan C2, C2 ≠ ‘.’} {F.S. : C1 = C2, C2 = CC, CC mungkin = ‘.’} Kamus : Algoritma : C1← C2 ADV C2 ← CC 22
8/25/2015
MESIN KATA
23
8/25/2015
Mesin Kata Dari primitif-primitif mesin karakter, dapat dibuat mesin kata yang melakukan pemrosesan terhadap pita karakter dengan anggapan tiap elemen yang diakuisisi berupa kata. Definisi kata : sederetan karakter suksesif pada pita larakter yang merupakan karakter bukan blank
24
8/25/2015
Kemungkinan isi dari pita karakter : hanya mengandung titik (pita kosong)
. hanya mengandung blank diakhiri titik _______________
.
mengandung blank di awal dan di akhir pita
25
8/25/2015
Kemungkinan isi dari pita karakter :
26
-
tidak mengandung blank di awal dan di akhir pita
-
mengandung blank di akhir pita
-
mengandung blank di awal pita
8/25/2015
Model Akuisisi Berikut ini beberapa contoh model akuisisi kata pada pita karakter dengan kasus menghitung panjang rata- rata kata pada sebuah pita karakter. Versi 1
Akhir proses adalah sebuah Boolean, berisi true jika kata terakhir telah diakusisi. Kata diakuisisi mulai dari karakter pertama sesudah akhir kata. Akuisisi kata terakhir menghasilkan kata kosong. 27
8/25/2015
Model Akuisisi Versi 1 Program PANJANG_RATA_KATA1 { algoritma menghitung panjang rata-rata kata pada pita karakter } { Versi 1 : Skema pemrosesan tanpa penanganan kasus kosong } Kamus Constant Mark : character = ‘.’ Constant Blank : character = ‘ ’ Lkata : integer {panjang kata terakhir yang sudah diakuisisi} NbKata : integer {jumlah kata pada pita} LTotal : integer {akumulasi panjang kata} EndKata : boolean {true jika kata terakhir sudah diakusisi}
28
8/25/2015
Lanjutan Kamus
Procedure Ignore_Blank {mengabaikan satu atau beberapa blank} {I.S : CC sembarang} {F.S : CC Blank, atau CC = mark} Procedure Hitung_Panjang {menghitung panjang kata} {I.S : CC adalah karakter pertama dari kata } {F.S : CC = Blank atau CC = mark, CC adalah karakter pertama sesudah huruf terkahir kata yang diakuisisi; Lkata berisi panjang kata yang sudah diakuisisi} 29
8/25/2015
Lanjutan Kamus Procedure START_KATA {mengabaikan satu atau beberapa blank} {I.S : CC sembarang} {F.S : Endkata true dan CC = mark atau EndKata false, Lkata adalah panjang kata yang sudah diakuisisi, CC karakter pertama sesudah karakter terakhir kata} Procedure ADVKATA {mengabaikan satu atau beberapa blank} {I.S : EndKata false; CC adalah karakter sesudah karakter terakhir dari kata yang sudah diakuisisi} {F.S : Endkata true dan CC = mark atau EndKata false, Lkata adalah panjang kata yang sudah diakuisisi, CC karakter pertama sesudah karakter terakhir kata} 30
8/25/2015
Algoritma : LTotal 0 NbKata 0 STARTKATA While not EndKata do LTotal LTotal + LKata NbKata NbKata + 1 ADVKATA {Endkata=true} depend on NbKata NbKata 0 : Output (LTotal/NbKata) NbKata = 0 : Output (‘Pita tidak mengandung kata’) 31
8/25/2015
Procedure Ignore_Blank {mengabaikan satu atau beberapa Blank} {I.S : CC sembarang} {F.S : CC Blank atau CC = Mark} Kamus Algoritma while (CC = Blank) and (CC Mark) do ADV {CC Blank OR CC = Mark}
32
8/25/2015
Procedure Hitung_Panjang {menghitung panjang kata} {I.S : CC adalah karakter pertama dari kata, CC Blank dan CC Mark } {F.S : CC = Blank atau CC = Mark; CC adalah karakter sesudah huruf terakhir kata yang diakuisisi; Lkata berisi panjang kata yang sudah diakuisisi} Kamus Algoritma Lkata 1 {karena berada pada karakter pertama pita} iterate ADV Stop ((CC = Mark) or (CC = Blank)) Lkata Lkata + 1 {(CC = Mark) or (CC = Blank); Lkata = # karakter kata yang diakuisisi} 33
8/25/2015
Procedure START_KATA {mengabaikan satu atau beberapa Blank} {I.S : CC sembarang } {F.S : Endkata True dan CC = Mark atau EndKata = False; Lkata adalah panjang kata yang sudah diakuisisi; CC karakter pertama sesudah karakter terakhir kata} Kamus Algoritma START Ignore_blank depend on CC CC = Mark : EndKata true CC Mark : EndKata false Hitung_Panjang 34
8/25/2015
Procedure ADVKATA {mengabaikan satu atau beberapa Blank} {I.S : EndKata = false; CC adalah karakter sesudah karakter terakhir kata yang sudah diakusisi } {F.S : Endkata True dan CC = Mark atau EndKata = False; Lkata adalah panjang kata yang sudah diakuisisi; CC karakter pertama sesudah karakter terakhir kata} Kamus Algoritma Ignore_blank depend on CC CC = Mark : EndKata true CC Mark : Hitung_Panjang 35
8/25/2015
Model Akuisisi Versi 2
Akhir dari proses adalah sebuah kata kosong, yaitu kata dengan panjang nol. Model akuisisi kata sama dengan Versi 1
36
8/25/2015
Model Akuisisi Versi 2 Program PANJANG_RATA_KATA2 { algoritma menghitung panjang rata-rata kata pada pita karakter } Kamus Constant Mark : character = ‘.’ Constant Blank : character = ‘ ’ Lkata : integer {panjang kata terakhir yang sudah diakuisisi} NbKata : integer {jumlah kata pada pita} LTotal : integer {akumulasi panjang kata}
37
8/25/2015
Procedure Ignore_Blank {mengabaikan satu atau beberapa blank} {I.S : CC sembarang} {F.S : CC Blank, atau CC = mark} Procedure Hitung_Panjang {menghitung panjang kata} {I.S : CC adalah karakter pertama dari kata } {F.S : CC = Blank atau CC = mark, CC adalah karakter pertama sesudah huruf terkahir kata yang diakuisisi; Lkata berisi panjang kata yang sudah diakuisisi} 38
8/25/2015
Procedure START_KATA {mengabaikan satu atau beberapa blank} {I.S : CC sembarang} {F.S : Lkata = 0, dan CC = Mark; atau Lkata 0; Lkata adalah panjang kata yang sudah diakuisisi, CC karakter pertama sesudah karakter terakhir kata} Procedure ADVKATA {mengabaikan satu atau beberapa blank} {I.S : Lkata = 0; CC adalah karakter sesudah karakter terakhir dari kata yang sudah diakuisisi} {F.S : Lkata = 0, dan CC = Mark; atau Lkata 0; Lkata adalah panjang kata yang sudah diakuisisi, CC karakter pertama sesudah karakter terakhir kata} 39
8/25/2015
Algoritma : NbKata 0 {belum ada kata diakuisisi} LTotal 0 {belum ada kata diakuisisi, #Kata = 0} STARTKATA While (Lkata 0 ) do LTotal LTotal + LKata NbKata NbKata + 1 ADVKata {Lkata = 0 ketemu Mark} depend on NbKata NbKata 0 : Output (LTotal/NbKata) NbKata = 0 : Output (‘Pita tidak mengandung kata’) 40
8/25/2015
Procedure Ignore_Blank {mengabaikan satu atau beberapa Blank} {I.S : CC sembarang} {F.S : CC Blank atau CC = Mark} Kamus Algoritma {I.S CC sembarang} while (CC = Blank) and (CC Mark) do ADV {F.S : CC Blank or CC = Mark}
41
8/25/2015
Procedure Hitung_Panjang {menghitung panjang kata} {I.S : CC adalah karakter pertama dari kata, CC Blank dan CC Mark } {F.S : CC = Blank atau CC = Mark; CC adalah karakter sesudah huruf terakhir kata yang diakuisisi; Lkata berisi panjang kata yang sudah diakuisisi} Kamus Algoritma Lkata 0 While (CC Mark) and (CC Blank) do Lkata Lkata + 1 ADV {(CC = Mark) or (CC = Blank) 42
8/25/2015
Procedure START_KATA {mengabaikan satu atau beberapa Blank} {I.S : CC sembarang } {F.S : Lkata = 0 dan CC = Mark; Lkata 0, Lkata adalah panjang kata yang sudah diakuisisi; CC karakter pertama sesudah karakter terakhir kata} Kamus Algoritma START Ignore_blank Hitung_Panjang
43
8/25/2015
Procedure ADVKATA {mengabaikan satu atau beberapa Blank} {I.S : Lkata 0 ; CC adalah karakter sesudah karakter terahir kata yang sudah diakusisi } {F.S : Lkata = 0 dan CC = Mark; atau Lkata 0; Lkata adalah panjang kata yang sudah diakuisisi; CC karakter pertama sesudah karakter terakhir kata} Kamus Algoritma Ignore_Blank Hitung_Panjang
44
8/25/2015
Model Akuisisi Versi 3 Mengabaikan blank di awal pita, dan memproses sisanya. Versi ini merupakan model akuisisi tanpa Mark, artinya kata yang diakuisisi tidak pernah kata kosong. Akuisisi dimulai dari karakter pertama suatu kata sampai karakter kata pertama dari kata berikutnya (atau titik jika merupakan kata terakhir). Model ini mengharuskan adanya prosedur initakses untuk memposisikan CC pada karakter pertama.
initakses
45
8/25/2015
Model Akuisisi Versi 3 Program PANJANG_RATA_KATA3 { algoritma menghitung panjang rata-rata kata pada pita karakter } { Versi3 : Skema Pemrosesan Tanpa Mark} Kamus Constant Mark : character = ‘.’ Constant Blank : character = ‘ ’ Lkata : integer {panjang kata terakhir yang sudah diakuisisi} NbKata : integer {jumlah kata pada pita} LTotal : integer {akumulasi panjang kata}
46
8/25/2015
Lanjutan Kamus Procedure Ignore_Blank {mengabaikan satu atau beberapa blank} {I.S : CC sembarang} {F.S : CC Blank, atau CC = mark} Procedure Hitung_Panjang {menghitung panjang kata} {I.S : CC adalah karakter pertama dari kata } {F.S : CC = Blank atau CC = mark, CC adalah karakter pertama sesudah huruf terkahir kata yang diakuisisi; Lkata berisi panjang kata yang sudah diakuisisi} 47
8/25/2015
Lanjutan Kamus Procedure INITAKSES {mengabaikan satu atau beberapa blank pada awal pita} {I.S : CC sembarang} {F.S : CC = Mark; atau CC karakter pertama dari kata yang akan diakuisisi} Procedure ADVKATA {mengabaikan satu atau beberapa blank} {I.S : CC adalah karakter pertama dari kata yang akan diakuisisi} {F.S : Lkata adalah panjang kata yang sudah diakuisisi; CC karakter pertama kata berikutnya, mungkin Mark}
48
8/25/2015
Algoritma : INITAKSES LTotal 0 NbKata 0 While (CC Mark ) do ADVKata LTotal LTotal + LKata NbKata NbKata + 1 {CC = Mark } depend on NbKata NbKata 0 : Output (LTotal/NbKata) NbKata = 0 : Output (‘Pita tidak mengandung kata’) 49
8/25/2015
Procedure Ignore_Blank {mengabaikan satu atau beberapa Blank} {I.S : CC sembarang} {F.S : CC Blank atau CC = Mark} Kamus Algoritma {I.S CC sembarang} while (CC = Blank) and (CC Mark) do ADV {F.S : CC Blank atau CC = Mark}
50
8/25/2015
Procedure Hitung_Panjang {menghitung panjang kata} {I.S : CC adalah karakter pertama dari kata, CC Blank dan CC Mark } {F.S : CC = Blank atau CC = Mark; CC adalah karakter sesudah huruf terakhir kata yang diakuisisi; Lkata berisi panjang kata yang sudah diakuisisi} Kamus Algoritma Lkata 1 {CC adalah karakter pertama pita} Iterate ADV Stop ((CC = Mark) or (CC = Blank)) Lkata Lkata + 1 (CC = Mark) or (CC = Blank) 51
8/25/2015
Procedure INITAKSES {mengabaikan satu atau beberapa Blank pada awal pita} {I.S : CC sembarang } {F.S : CC = Mark atau CC = karakter pertama dari kata yang akan diakuisisi} Kamus Algoritma START Ignore_blank
52
8/25/2015
Procedure ADVKATA {mengabaikan satu atau beberapa Blank} {I.S : CC = karakter pertama dari kata yang akan diakuisisi} {F.S : Lkata adalah panjang kata yang sudah diakuisisi; CC karakter pertama kata berikutnya, CC mungkin = Mark} Kamus Algoritma Hitung_Panjang Ignore_blank
53
8/25/2015
Soal Latihan 1.
Diberikan sebuah mesin karakter dengan pita berisi karakter (mungkin kosong), hitunglah : - banyaknya kemunculan huruf hidup yang muncul pada pita tersebut. - frekuensi huruf hidup - banyaknya kemunculan setiap huruf hidup Definisikanlah dengan jelas apa yang dimaksud dengan huruf hidup.
54
8/25/2015
Referensi Diktat Kuliah IF2181 Struktur Data, Inggriani Liem, ITB, 2003.
55
8/25/2015
THANK YOU 8/25/2015 56
