Quick Notes

Quick Notes

Asas Sains Komputer Chapter 3: Algoritma
3.1
 
3.1  Pembangunan Algoritma
 
Pengenalan kepada Algoritma
  • Algoritma ialah satu set langkah-langkah yang perlu dilaksanakan untuk menghasilkan output yang dikehendaki.
  • Algoritma digunakan oleh pengaturcara untuk membangunkan set atur cara yang telah dirancang.
  • Algoritma juga salah satu teknik penyelesaian masalah.
  • Algoritma boleh diwakili dengan pembinaan pseudokod dan carta alir.
  • Pembangunan algoritma merupakan satu teknik pengitlakan yang mengandungi langkah-langkah untuk menyelesaikan masalah.
  • Algoritma dibangunkan untuk membantu memahami  proses  yang  perlu  dilakukan  oleh  komputer, melakukan  penambahbaikkan kepada  algoritma dan menulis  algoritma  dengan  teratur, cekap  dan  mudah difahami.
  • Antara faedah yang diperoleh daripada kajian serta pembangunan algoritma yang dilakukan adalah seperti berikut:
    1. Memahami bagaimana komputer memproses urutan tindakan-tindakan yang perlu dilaksanakan.
    2. Mempelajari cara menulis algoritma yang teratur, mudah dibaca dan difahami.
    3. Mempelajari cara menulis algoritma dengan cekap.
    4. Mempelajari cara melakukan penambahbaikan pada algoritma.
 
3.1.1 Ciri-Ciri Search 
i. Search
  • Jenis Search adalah seperti berikut:
Linear Search Binary  Search
Satu teknik untuk mendapatkan item dalam satu senarai linear. Satu teknik yang menggunakan proses carian dwipilihan.
Pencarian bermula dari item pertama dan diikuti dengan item berikutnya. Item dalam senarai akan diisih dalam urutan menaik.
Sekiranya item yang dicari tiada dalam senarai, maka carian akan ditamatkan. Proses carian akan dimulai dari ditengah-tengah senarai item.
Item tidak perlu diisih mengikut urutan. Jika carian telah ditemui, maka proses carian akan ditamatkan.
Teknik ini kurang efesien. Teknik ini akan membandingkan item ditengah-tengah dengan item yang bersebelahan dengannya.
Teknik ini menggunakan masa yang panjang untuk memproses senarai yang panjang. Teknik ini lebih efesien kerana tidak perlu menyemak semua senarai dan sesuai untuk item yang banyak.
ii. Sort
  • Sort ialah proses mengisih atau menyusun item-item dalam suatu senarai linear mengikut urutan tertentu.
  • Dalam bidang perkomputeran, sort ialah teknik yang penting untuk mendapatkan maklumat dengan cepat dan tepat.
  • Antara contoh sort dalam kehidupan seharian ialah:
    • Mengisih surat-surat di pejabat pos mengikut negeri.
    • Menyusun senarai nama murid mengikut abjad.
    • Menyusun murid-murid ke dalam barisan mengikut rumah sukan.
  • Jenis Sort adalah seperti berikut:
Bubble Sort Bucket Sort
Teknik ini mengisihkan item-item mengikut urutan menaik atau menurun. Teknik ini mengasingkan item-item dalam senarai tertentu ke dalam baldi.
Teknik ini akan bermula dengan mengisihkan dua item pertama  dalam  senarai. Item-item di dalam baldi akan diisih.
Item pertama dan kedua akan bertukar tempat dan menyusunnya mengikut urutan menaik atau menurun. Item-item disusun semula ke dalam senarai.
Perbandingan dengan item bersebelahan akan berterusan sehingga satu set susunan akan dihasilkan samada secara menaik atau menurun. Bilangan baldi yang digunakan bergantung kepada bilangan pengaturcara dan bilangan item-item dalam senarai yang perlu  diisih.
Perbandingan antara Search dan Sort
  • Persamaan
    • Memerlukan senarai.
    • Memerlukan algoritma.
    • Linear search dan bubble sort sesuai digunakan untuk senarai item yang sedikit.
    • Binary search dan bucket sort sesuai untuk item yang banyak.
  • Perbezaan
    • Search - Mencari item tertentu dalam senarai.
    • Sort - Mengisih item-item dalam senarai mengikut urutan menaik atau menurun.
 
3.1.2 Menulis Pseudokod dan Melukis Carta Alir bagi Linear Search dan Binary Search
Simbol-Simbol bagi Carta Alir

   

 
Linear Search
  • Algoritma ialah satu set langkah yang teratur untuk dilakukan bagi mencapai sesuatu hasil.
  • Algoritma  boleh  diwakili  oleh pseudokod dan carta alir.
  • Pseudokod ialah perwakilan algoritma dalam bahasa yang boleh difahami.
  • Carta alir adalah perwakilan algoritma dalam bentuk grafik.
  • Algoritma memudahkan seseorang untuk mengesan ralat yang ada pada output yang diperoleh dan dapat memastikan output yang dihasilkan adalah output yang diingini.
  • Algoritma bagi proses linear search dirumuskan seperti berikut:

Imej ini menunjukkan carta alir bagi proses algoritma carian linear. Terdapat lima langkah yang dijelaskan dalam kotak berwarna biru dan hijau. - **Langkah 1:** Mula dengan item pertama dalam senarai. - **Langkah 2:** Bandingkan item carian dengan item pertama. - **Langkah 3:** Jika nilai item carian sama dengan nilai item pertama, carian dihentikan. - **Langkah 4:** Jika nilai item carian tidak sama dengan nilai item pertama, ulang Langkah 2. - **Langkah 5:** Carian tamat apabila item carian diperoleh atau apabila semua item telah disemak. Di bahagian bawah imej terdapat logo
  • Pseudokod bagi proses linear search adalah seperti berikut:
       

1. Mula

2. Setkan senarai L = [15, 44, 100, 42, 99]

3. Isytihar pemboleh ubah i, n, T

4. Setkan n = 5

5. Setkan i = 0

6. Masukkan nilai carian T

7. for i

     7.1 Jika Li == T

           7.1.1 Papar "Item ada dalam senarai"

           7.1.2 Langkau ke Langkah 9

7.2 Jika tidak

      7.2.1 Kira i = i+1

   
  • Carta alir bagi bagi proses linear search adalah seperti berikut:
        
Binary Search
  • Algoritma perlu dibina bagi memudahkan proses binary search.
  • Algoritma bagi binary search adalah seperti berikut:

Gambar ini menunjukkan aliran kerja dalam bentuk carta alir untuk mencari item dalam senarai. Terdapat tujuh kotak berwarna biru dengan teks putih yang mengandungi langkah-langkah berikut: 1. Pastikan item-item dalam senarai yang diberi telah diisi mengikut urutan menaik. 2. Lihat item yang berada di tengah senarai. 3. Bandingkan item carian dengan item yang berada di tengah senarai. 4. Jika nilai item carian sama dengan item yang berada di tengah senarai, carian selesai. 5. Jika nilai item carian kurang daripada nilai item yang berada di tengah senarai, abaikan item di tengah dan item-item selepasnya.
  • Pseudokod bagi proses binary search adalah seperti berikut:
       

1. Mula

2. Setkan senarai L = [P, Q, R, S, T]

3. Isytihar pemboleh ubah n, i, j, m, b

4. Setkan n = 5

5. Setkan i = 0

6. Setkan j=n-1

7. Masukkan satu nilai carian b

8. while i < j

    8.1 Setkan m = (i + j) /2

    8.2 Jika b == Lm

       8.2.1 Papar "item ada dalam senarai"

       8.2.2 Keluar gelung

    
  • Carta alir bagi bagi proses binary search adalah seperti berikut:
       
 
3.1.3 Menulis Pseudokod dan Melukis Carta Alir bagi Bubble Sort dan Bucket Sort
Bubble Sort
  • Penyusunan data seperti nama, nombor, rekod dan fail dalam tertib tertentu.
  • Data yang telah diisih menjadikan carian lebih cekap, percantuman lebih efisien dan  memudahkan pemprosesan data dalam susunan yang dikehendaki.
  • Proses carian akan menjadi dengan adanya penghapusan  dan  pencatuman  data  yang  berulang.
  • Algoritma bagi bubble sort menggunakan struktur kawalan ulangan untuk memproses setiap item.
  • Algoritma bagi bubble sort adalah seperti berikut:

Imej ini menunjukkan langkah-langkah algoritma bagi Bubble Sort dalam bahasa Melayu. Terdapat enam bulatan bernombor dari 1 hingga 6 yang disusun secara mendatar. Setiap bulatan mempunyai penerangan di bawahnya: 1. Semak item pertama dengan item kedua dalam senarai. 2. Bandingkan kedua-dua item tersebut. 3. Jika kedua-dua item tersebut tidak mengikut turutan, tukarkan kedudukan kedua-duanya. 4. Ulang langkah 2 hingga langkah 3 dengan item ketiga, kemudian item ketiga dengan item keempat dan seterusnya sehingga ke item terakhir. 5. Semak senarai untuk melihat sama ada semua item berada pada kedudukan yang betul

 
  • Pseudokod bagi proses bubble sort adalah seperti berikut:
       

1. Mula

2. Setkan senarai L = [27, 26, 23, 28, 30]

3. Isytihar pemboleh ubah i, j, n, temp

4. Setkan n = 5

5. Setkan i = 0

6. Setkan temp = 0

7. for i

    7.1 Setkan j=0

    7.2 for j

         7.2.1 Jika Lj. Lj + 1

        7.2.1.1 temp = Lj

        7.2.1.2 Lj = Lj + 1

   
  • Carta alir bagi bagi proses binary search adalah seperti berikut:
      
Bucket Sort
  • Algoritma bagi bucket sort ialah suatu isihan yang menyusun item-item dalam suatu senarai mengikut kategori dan menyusunnya semula mengikut susunan yang betul.
  • Item-item dalam senarai akan diisih sebanyak dua kali supaya item-item berada dalam urutan yang betul.
  • Isihan pertama dibuat apabila item-item dalam senarai diisih mengikut saiz baldi.
  • Isihan kedua dibuat apabila item-item dalam setiap baldi diisih  mengikut urutan.
  • Algoritma bagi bucket sort adalah seperti berikut:

Imej ini menunjukkan algoritma bagi kaedah pengisihan ‘Bucket Sort’ dalam bentuk carta alir. Terdapat lima langkah yang diterangkan secara berurutan: 1. Julat bagi setiap baldi ditentukan supaya item-item dapat dimasukkan ke dalam baldi. 2. Beberapa buah baldi diwujudkan untuk menyimpan item-item daripada senarai untuk sementara. 3. Setiap item dimasukkan secara sementara ke dalam baldi berdasarkan julat yang ditetapkan. 4. Item-item di dalam baldi diisihkan. 5. Apabila item-item dalam semua baldi diisi, item-item tersebut dicantumkan dan dimasukkan ke dalam senarai
  • Pseudokod bagi proses bucket sort adalah seperti berikut:
       

1. Mula

2. Setkan senarai L = [A, B, C, ..., H]

3. Setkan senarai baharu []

4. Isytihar pemboleh ubah i, j, n, nB

5. Setkan n = 8

6. Setkan nB = bilangan baldi

7. Wujudkan baldi kosong

8. Masukkan item ke dalam baldi

9. Setkan i = 0

10. for i < n

     10.1 Masukkan senarai [i] ke dalam Baldi

     10.2 Kira i = i +1 11. Setkanj = 0

    
  • Carta alir bagi bagi proses bucket sort adalah seperti berikut:
       
 
3.1.4 Mengesan dan Membaiki Ralat dalam Pseudokod dan Melukis Carta Alir 
  • Apabila terdapat ralat dalam suatu algoritma, ia akan menyebabkan atur cara yang dibangunkan itu tidak dapat menghasilkan output yang dikehendaki.
  • Pengesanan ralat dalam algoritma adalah penting supaya proses pembaikian kod atur cara dapat dilakukan.
  • Semakan meja dan semakan  langkah demi langkah merupakan dua jenis pengesanan ralat dalam algoritma.
Pengesanan Ralat melalui Semakan Meja
  • Output perlu bergantung kepada pemboleh ubah semasa algoritma papar dipanggil.
  • Kesahihan output algoritma ditentukan dengan membandingkan output dijangka.
  • Output dijangka ditentukan dengan hitungan manual.
  • Output akan bersamaan dengan output algoritma jika algoritma adalah betul.
Pengesanan Ralat melalui Langkah Demi Langkah 
  • Jadual pemboleh ubah boleh digunakan untuk mengesan perubahan algoritma yang mengumpuk dan mengubah nilai pemboleh ubah.
  • Perubahan pada pemboleh ubah mungkin berlaku pada setiap baris algoritma.
Tujuan Pengujian dan Pembaikan Ralat
  • Untuk pembaikian algoritma.
  • Memastikan algoritma betul sebelum ditulis sebagai kod komputer.
  • Untuk memastikan logik algoritma adalah betul supaya pembaikiannya lebih senang.
Ciri-Ciri Ralat Algoritma
  • Berfungsi dan menjimatkan proses pengekodan.
  • Mudah difahami.
  • Berdasarkan kriteria reka bentuk.
  • Memenuhi  keperluan untuk menyelesaikan masalah.
Dua Jenis Ralat dalam Algoritma
  • Ralat  Logik
    • Output yang  dihasilkan adalah tidak tepat sebagaimana yang sepatutnya akibat kesilapan menulis formula, jenis data yang tidak sesuai atau nilai umpukan yang tidak betul.
  • Ralat Sintaks
    • Tidak ada semasa penulisan algoritma kerana ia hanya wujud jika ada kesilapan semasa menggunakan bahasa pengaturcaraan.
Langkah-Langkah Pengujian Ralat dalam Algoritma 

Imej ini menunjukkan langkah-langkah pengujian ralat dalam algoritma. Terdapat empat langkah yang digambarkan dalam bentuk grafik: 1. Kenalpasti output yang dijangka. 2. Kenalpasti output yang diperolehi. 3. Bandingkan output yang dijangka dan diperolehi. 4. Laksanakan penambahbaikan kepada algoritma. Setiap langkah ditunjukkan dalam bentuk bulatan atau bujur dengan nombor langkah yang sesuai. Di bahagian bawah imej, terdapat logo ‘Pandai’.
 
3.1.5 Membandingkan Algoritma Search dan Sort melalui Pengecaman Corak
  • Pengecaman corak adalah penting dalam proses pembangunan algoritma kerana para pengatur cara boleh mengenal pasti dan memahami corak masalah yang harus diselesaikan.
  • Pengecaman corak merupakan salah satu teknik untuk mengenal pasti ciri-ciri, struktur, bentuk input serta output yang terdapat dalam sesuatu masalah algoritma.
  • Kaedah  pengecaman corak  boleh digunakan untuk membandingkan masalah-masalah yang  hendak diselesaikan dengan masalah-masalah lain yang seiras  dan  telah  mendapat  penyelesaiannya.
  • Jika corak masalahnya adalah seiras,  maka pengaturcara boleh menggunakan bentuk penyelesaian sedia ada untuk membina algoritma penyelesaian bagi masalah yang hendak diselesaikan.
Persamaan dan Perbezaan di antara Ciri-Ciri Algoritma Search dan Sort
 
Algoritma Search Algoritma Sort
Persamaan
Menggunakan senarai.
Menggunakan gelung.
Perbezaan
Membandingkan item carian dengan item tertentu dalam  senarai. Isihan akan tamat jika semua item berada dalam urutan yang betul.
Mencari suatu item dalam senarai. Mengisih item-item dalam senarai mengikut urutan menaik atau menurun.
Boleh digunakan untuk senarai yang telah diisih atau belum. Digunakan untuk senarai yang belum diisih.
 
3.1.6 Algoritma bagi Gabungan Search dan Sort
  • Gabungan algoritma search dan sort diperlukan untuk mempercepatkan dan memudahkan proses penyelesaian sesuatu masalah.
  • Selain itu, gabungan juga boleh dibuat diantara algoritma jenis search iaitu linear search dan binary search atau bubble sort dan bucket sort.
  • Gabungan teknik search dan sort akan membantu pengaturcara untuk menyelesaikan sesuatu masalah dengan mudah.
  • Selain itu, ia juga membolehkan pengaturcara mendapat output yang dikehendaki.
 
3.1.7 Algoritma bagi Gabungan Search atau Sort
  • Selain menggabungkan teknik search dengan teknik sort, gabungan satu teknik carian dengan teknik carian yang lain dan gabungan satu teknik isihan dengan teknik isihan yang lain sering dilakukan untuk menyelesaikan pelbagai jenis masalah dalam kehidupan seharian.