Struktur data dan algoritma [English]

                                                                                               

Kemungkinan-kemungkinan rujukan:

• J. Morris, http://docs.linux.cz/programming/algorithms/Algorithms-Morris/
• M. Elson, Concepts of Programming Languages (SRA Inc) [Bab 8]
• R. Sedgewick, Algorithms in C (Addison-Wesley)

 

Objektif topik: Pelajar harus memahami struktur data yang asas, dan beberapa algoritma utama. Konsep kekompleksan algortimaan juga harus difahami, dan anggaran kekompleksan bagi kes-kes mudah harus dapat dibuat.

 

Struktur data – bentuk-bentuk organisasi data, biasanya berkaitan dengan jenis data Algoritma – satu tatacara yang dispesifikasikan secara tepat, bagi menyelesaikan suatu masalah

 

Pemodularan

perlu cara formal membina aturcara secara cekap dan boleharap.

- boleh dilakukan dgn memecahkan suatu aturcara kpd modul-modul kecil yg bersesuaian, yg tiap-tiapnya boleh ditulis dan diuji sebelum dimasukkan ke dalam modul yg lebih besar, yg seterusnya dibina dan diuji

kod spageti – panjang dan berlingkar-lingkar

 

Peniskalaan

pandangan aras tinggi bagi objek atau fungsi di mana butiran aras rendah boleh diabaikan.

- membolehkan telatah utama objek atau fungsi dipertimbangkan dalam menyelesaikan masalah tanpa dirumitkan butiran-butiran.

Peniskalaan fungsi – spesifikasikan fungsi bagi suatu modul

Peniskalaan struktur (orientasi objek - OO) – bina model perisian untuk telatah barang-barang dunia sebenar

 

Jenis data – struktur data dan himpunan fungsi atau tatacara yang mengolah struktur data tersebut

Jenis data niskala – jenis data yg hanya boleh dicapai menerusi suatu antaramuka

Aturcara yg menggunakan suatu jenis data niskala: pelanggan

Aturcara yg menspesifikasikan jenis data niskala tersebut: implementasi

 

 

Beberapa struktur data asas dan beberapa operasi berkaitan:

vektor set teratur unsur-unsur data	pengindeksan hasiltambah vektor, dsb
rentetan vektor dgn panjang yg bolehubah	penjeraitan
tatasusunan tatasusunan berdimensi n ialah vektor dgn unsur-unsurnya tatasusunan berdimensi n-1 dgn set-set indeks yg sepadan (tatasusunan berdimensi 0 adalah skalar)	pelinearan (menulis unsur-unsur sebagai aturan linear dimensi 1)
pepohon suatu unsur data sebagai akar dan beberapa (mungkin 0) ranting yang terdiri dari (sub)pepohon	tuding ke akar ranting anak pertama kembalian unsur akar ranting anak pertama tuding ke akar ranting seterusnya kembalian unsur akar ranting seterusnya
senarai berpaut ke hadapan unsur-unsur setiapnya dgn pautan kpd unsur seterusnya, diakhiri pautan nol	awalkan tuding ke unsur pertama kembalian unsur pertama tuding ke unsur seterusnya kembalian unsur seterusnya kembalian unsur terakhir masukkan unsur hapuskan unsur ujian samada senarai kosong
senarai berpaut dwiarah spt senarai berpaut ke hadapan tapi dgn pautan ke belakang juga	tuding ke unsur sebelumnya kembalian unsur sebelumnya
senarai membulat senarai berpaut ke hadapan dgn unsur terakhir terpaut ke unsur pertama	kembalian saiz senarai
baris gilir senarai unsur-unsur data utk mana masukan unsur di buat di satu hujung dan penghapusan di satu lagi (senarai FIFO)	masukan unsur baru keluaran (kembalian & penghapusan) unsur ujian samada baris gilir kosong
tindan spt baris gilir, tapi masukan dan penghapusan di buat di hujung yang sama (senarai LIFO)	tolak (masukan unsur baru) pop (keluaran unsur) ujian kekosongan
graf struktur spt pepohon tetapi lebih am: suatu unsur mungkin komponen lebih dari satu substruktur -         terarah: setiap unsur punyai kepala (kecuali akar) dan ekor (mungkin nol) -         terakar: satu unsur akar yg tak berkepala -         tersambung: mana dua unsur punyai sekurangnya satu pendahulu bersama -         tak membulat: tiada unsur yg mendahului dirinya
gelang struktur berhierarki di mana set komponen suatu unsur dipaut sbg senarai membulat
timbunan baris gilir di atas pepohon dedua lengkap di mana unsur di suatu nod adalah lebih terkemudian menurut tertib berbanding unsur-unsur di nod ranting; masukan ialah pada sebelah paling kiri di aras ranting terbawah	masukan unsur  (tertib perlu diabadikan dgn cara tukarganti, jika perlu, nod anak dan ibu berkenaan ke atas sehingga ke akar)   penghapusan unsur akar (pengabadian tertib dgn tukarganti ke bawah ke ranting terendah; pertimbangkan nod anak yg lebih terkemudian menurut tertib)

 

 

Analisis algoritma

-         utk membandingkan algoritma berlainan utk  tugasan sama

-         utk meramalkan prestasi algoritma dlm persekitaran baharu

-         utk menetapkan nilai parameter-parameter algoritma

-         dll

 

kekompleksan – anggaran (peringkat) bilangan pengiraan yg perlu dibuat terhadap suatu parameter utama N apabila N besar

 

 

beberapa algoritma biasa:

 

pengisihan

 

♠ isihan gelembung –  unsur-unsur dalam suatu vektor: bandingkan dua unsur berjiranan; tukarganti jika perlu, menurut tertib; imbas seluruh vektor – kalau ada N unsur, setiap imbasan perlukan N operasi bandingan, dan dlm kes terburuk perlukan N pusingan imbasan ⇒ kekompleksan ~ N×N ataupun O(N²)

 

♠ isihan timbunan – unsur-unsur dimasukkan ke dalam timbunan dan dikeluarkan dari akar – pengabadian tertib dalam timbunan memerlukan ~ log₂ N operasi ⇒ kekompleksan O(log N)

 

♠ isihan cepat –  unsur-unsur dalam suatu vektor: gunakan rekursi: bahagikan vektor asal kpd 2 bahagian yg diatur semula unsurnya, dan isih bahagian-bahagian ini secara rekursi; pembahagian dibuat spt berikut: pilih suatu unsur, imbas dari satu hujung vektor sehingga bertemu unsur yg tertibnya terkemudian dari unsur pilihan dan dari hujung yg satu lagi sehingga bertemu unsur yg tertibnya terdahulu dari unsur pilihan, tukarganti unsur yg ditemui ini, dan teruskan imbasan sebegini sehingga bertemu, di pertemuan itulah letakkan unsur pilihan tadi – kes terburuk bila vektor sudah tertertib & pembahagian dibuat N kali & bilangan bandingan = N+(N-1)+(N-2)+…+2+1 = (N+1)N/2; secara purata, pembahagian ialah kpd 2 bahagian bersaiz lebih-kurang sama, jadi kekompleksan C_N = 2C_N/2+N  ~ O(N log N)

 

♠ isih-cantum –  unsur-unsur dalam suatu vektor: gunakan rekursi: bahagikan vektor asal kpd 2 bahagian yg setiapnya dikenakan isih-cantum berasingan, kemudian dicantum semula, dengan cantuman menghormati tertib – pembahagian dibuat log N kali & pada cantuman memerlukan N operasi kesemuanya pada aras ke-α (α cantuman setiapnya dengan vektor panjang N/α), jadi kekompleksan  ~ O(N log N)

 

♠ dll

 

 

penggelintaran

 

♠ berjujukan – unsur-unsur dalam suatu vektor: cari unsur yg dikehendaki dgn meneliti unsur-unsur satu-persatu – kekompleksan O(N)

 

♠ deduaan – unsur-unsur dalam suatu vektor secara bertertib: bahagikan vektor kpd 2; tentukan di bahagian mana unsur dicari patut berada; bahagikan pula bahagian ini; dan seterusnya, hingga ditemui – vektor panjang N boleh dibahagi sebegitu log₂ N kali ⇒ kekompleksan O(log N)

 

♠ pepohonan – gunakan pepohon dedua gelintaran (pepohon dedua tertertib: subpepohon kiri mempunyai akar terdahulu dalam tertib kepada nod akar dan subpepohon kanan punyai akar tertib terkemudian, dan setiap subpepohon juga tertertib); gelintar dalam subpepohon berkenaan – kekompleksan O(log N)

 

♠ fungsi cincangan / jadual cincangan – tertib unsur diwakilkan oleh kunci; cincangan mentransformasikan kunci ini kepada alamat lokasi dalam jadual – kekompleksan O(1)

 

♠ dll

 

masalah grafan:

pepohon rentang minimum (sambung N pulau secara termurah), jurujual jalanan (lawat N tempat dgn perjalanan terpendek)

 

Ο algoritma tamak – gerakan dibuat berdasarkan hanya maklumat yg ada ketika gerakan itu hendak dibuat; biasanya suboptimum

 

♠ algoritma Kruskal – utk pepohon rentang minimum: tambah tepi termurah jika tidak hasilkan kitar

 

♠ algoritma Djikstra – utk mencari jejak terpendek dari satu bucu ke bucu-bucu lain: jika S set bucu yg telah didapati jejak terdekat dan V-S bagi yg baki, isih bucu dlm V-S menurut anggaran terbaik semasa bagi panjang jejak, tambahkan bucu dgn jejak terdekat u, dan kemaskini kos semua bucu v yg tersambung kpd u jika anggaran terbaik jejak terpendek ke v boleh diperbaiki dgn memasukkan tepi (u,v) dlm jejak ke v. 

 

♠ dll