Struktur data heap adalah sebuah objek array yang dapat dengan mudah divisualisasikan sebagai complete tree. Ada korespondensi satu ke satu diantara elemen array dan node dari tree. Tree itu benar-benar penuh pada semua tingkatan kecuali mungkin yang terendah, yang diisi dari kiri sampai titik tertentu. Semua node dari heap juga memenuhi hubungan bahwa nilai kunci pada setiap node pada kurangnya sama besar dengan nilai pada anak-anaknya.

Ini dapat dilihat sebagai sebuah pohon biner dengan dua kendala tambahan:

a. Bentuk property : pohon itu adalah complete binary tree , yaitu semua tingkat tree, kecuali mungkin yang terakhir (paling dalam) sepenuhnya diisi, dan, jika tingkat terakhir tree itu tidak lengkap, maka node pada  tingkat itu diisi dari kiri ke kanan.

b. Sifat heap: setiap node lebih besar dari atau sama dengan masing-masing anak sesuai dengan perbandingan predikat yang ditetapkan untuk struktur data.

Jenis heap :    

Min Heap: setiap elemen node adalah lebih kecil daripada children nya.

Ini menunjukan  bahwa elemen terkecil terletak pada root dari tree.
Unsur terbesar adalah terletak di suatu tempat di salah satu node leaves.

Contoh Min Heap:

Max Heap: setiap elemen node adalah lebih besar daripada children nya.

Karena urutan sibling dalam heap tidak ditentukan oleh sifat heap, dua node tunggal anak-anak bisa secara bebas dipertukarkan kecuali melakukan hal itu melanggar properti bentuk.

Aplikasi Heap

•Priority Queue
  •Algoritma Selection (mencari min/max element, median, kth-largest element, dll).
  •Algoritma Dijkstra (mencari jalan terpendek di grafik)
  •Algoritma Prim (mencari pohon spanning minimum)
•Heap Sort
  •Sebuah algoritma O(n.lg(n)).

Array Implementation

•Heaps biasanya diimplementasikan pada sebuah array.
•Elemen-elemennya disimpan secara berurutan dari index 1 sampai N dari atas sampai bawah dan dari kiri sampai kanan node sebuah pohon.
•Root disimpan pada index 1 (kita membiarkan index 0 kosong, untuk tujuan tertentu).

Array Representation

Array Implementation

•Setiap node berhubungan dengan parentnya, child kiri dan child kanan pada sebuah implementasi array dapat dikomputasi dengan mudah.
•Let the current node’s index be x.
  •Parent(x)  = x / 2
  •Left-child(x)  = 2 * x
  •Right-child(x)  = 2 * x + 1

This is why we use index 1 as root, otherwise the relation will not appear as simple as this.

Heap operations

Insert

Untuk menambahkan sebuah element ke HEAP kita harus melakukan operasi up-heap (juga dikenal sebagai bubble-up, percolate-up, sift-up, heapify-up, atau cascade-up) untuk mengembalikan sifat heap. Kita dapat melakukan ini dalam O (log n) time, menggunakan binary heap, dengan mengikuti algoritma ini:

  1. Tambahkan elemen pada level bawah heap.
  2.  Bandingkan elemen yg  baru ditambahkan  dengan parentnya, jika mereka berada di urutan yang benar, berhenti.
  3. Jika tidak, swap elemen dengan parent  dan kembali ke langkah sebelumnya.

Kita melakukan ini maksimum sekali untuk masing-masing tingkat di ketinggian tree, yang adalah O (log n). Namun, karena sekitar 50% dari elemen adalah leaves dan 75% berada di dua level di bawah, kemungkinan bahwa unsur baru yang akan dimasukkan hanya akan berpindah beberapa level ke atas untuk mempertahankan heap. Dengan demikian, binary heap mendukung insertion rata-rata dalam waktu yang konsta, O (1).

Misalkan kita memiliki heap

dan kita ingin menambahkan nomor 15 ke heap. Pertama-tama kita tempatkan 15 di posisi yg ditandai dengan X. Namun, sifat heap dilanggar karena 15 lebih besar dari 8, jadi kita perlu menukar 15 dan 8. Jadi, kita memiliki heap yg tampak sebagai berikut setelah swap pertama:

Namun sifat heap masih dilanggar karena 15 lebih besar dari 11, jadi kita perlu swap lagi:

Ini adalah max-heap yang valid. Tidak perlu untuk memeriksa children setelah ini. Sebelum kita menempatkan 15 pada X, tumpukan ini valid, yang berarti 11 lebih besar dari 5. Jika 15 lebih besar dari 11, dan 11 lebih besar dari 5, maka 15 harus lebih besar dari 5, karena dari relasi transitif.

Remove

Prosedur untuk men-delete akar dari tumpukan dan restorasi disebut down-heap (juga dikenal sebagai bubble-down, percolate-down, sift-down, heapify-down, or cascade-down)

Ganti root heap dengan elemen terakhir pada level terakhir.

Bandingkan root baru dengan childrennya, jika mereka berada di urutan yang benar, berhenti.
Jika tidak, swap unsur dengan salah satu childrennya dan kembali ke langkah sebelumnya. (Swap dengan children yang lebih kecil di min-heap dan children yang lebih besar di max-heap.)

Jadi, jika kita memiliki max heap-sama seperti sebelumnya, kita menghapus 11 dan menggantinya dengan 4.

Sekarang sifat heap dilanggar karena 8 lebih besar dari 4. Dalam hal ini, menukar dua elemen 4 dan 8, sudah cukup untuk mengembalikan sifat heap dan kita tidak perlu swap elemen lebih lanjut:

Simpul di bawah node yang bergerak di-swap dengan semakin besar children dalam sebuah max-heap (dalam min-heap akan bertukar dengan children nya yang lebih kecil), sampai memenuhi sifat heap di posisi baru.

 

 

 

 

 

 

Advertisements

Pembelajaran tahap 1
7. Bahasa mesin.
Pertanyaan benar/salah
5. B
6. S

Pembelajaran tahap 2
4. Klarifikasi masalah, desain program, coding program, pengujian program, serta dokumentasi dan pemeliharaan program.
6. Investigasi awal, analisis sistem, desain sistem, pengembangan sistem, implementasi sistem, dan pemeliharaan sistem.
Pembelajaran tahap 3
Pengelompokan bahasa komputer :
– Generasi pertama : bahasa mesin
– Generasi kedua : bahasa asembli
– Generasi ketiga : bahasa level tinggi, misalnya : FORTRAN, COBOL, BASIC, C, dan C++.
– Generasi keempat : bahasa level sangat tinggi, misalnya : SQL, Intellect, NOMAD, FOCUS.
– Generasi kelima : bahasa alami.

Pembelajaran tahap 1
2. Unix
3. Pemrograman visual
4. Programmer
5. Algoritma
Pilihan Ganda
3. D
Pertanyaan benar/salah
1. B

Pembelajaran tahap 2
4. Klarifikasi masalah, desain program, coding program, pengujian program, serta dokumentasi dan pemeliharaan program.
6. Investigasi awal, analisis sistem, desain sistem, pengembangan sistem, implementasi sistem, dan pemeliharaan sistem.
Pembelajaran tahap 3
Pengetahuan praktis
5. Ya, saya tertarik. Saya mempelajari bahasa C, karena bahasa C dapat digunakan sebagai bahasa dasar untuk mempelajari bahasa pemrograman lain nya.

Algoritma kekampus:
Bangun -beres2 kamar – mandi – berpakaian- berangkat

Pembelajaran tahap 1
1. SDLC
6. Sistem
Pilihan Ganda
1. C
2. A
Pertanyaan benar/salah
2. S
3. B
4. S

Pembelajaran tahap 2
1. Argumen manusia jerami : salah mempresentasikan posisi musuh anda agar ia lebih mudah diserang, atau anda menyerang posisi yang lebih lemah dan mengabaikan yang kuat.
2. Analisis sistem : melakukan analisis, desain, dan implementasi sistem.
3. Implementasi langsung, paralel, bertahap, pilot.
5. Investigasi awal, analisis sistem, desain sistem, pengembangan sistem, implementasi sistem, dan pemeliharaan sistem.
7. Prototipe : sistem dengan kerja terbatas, atau bagian dari sistem yang telah dikembangkan untuk menguji konsep-konsep desain.
Pembelajaran tahap 3
Pengetahuan praktis
1. All aspects of the software development life cycle can be supported by software tools, and so the use of tools from across the spectrum can, arguably, be described as CASE; from project management software through tools for business and functional analysis, system design, code storage, compilers, translation tools, test software, and so on.
However, it is the tools that are concerned with analysis and design, and with using design information to create parts (or all) of the software product, that are most frequently thought of as CASE tools. CASE applied, for instance, to a database software product, might normally involve:
• Modelling business / real world processes and data flow
• Development of data models in the form of entity-relationship diagrams
• Development of process and function descriptions
• Production of database creation SQL and stored procedures

4. Yang paling menarik adalah tahap analisis sistem, karena tahap ini tidak bisa sembarangan dikerjakan.
Latihan web
1. mengubah data menjadi tidak bisa dibaca, untuk membaca nya di butuhkan desription. Browser saya sudah saya lengkapi dengan enkripsi
2. metode ilmiah lebih rumit dan mengharuskan pengguna nya berpikir sendiri, sedangkan SDLC dibantu pleh software tertentu.

Pembelajaran tahap 1
1. Manusia, prosedur,software, elektromagnetis, ”data kotor”
2. Salah ketik, salah data
3. Enkripsi
4. Data kotor
5. Kesalahan prosedural.
6. Computer emergency response team
7. Bajakan
Pilihan Ganda
1. C
2. C
3. E
Pertanyaan benar/salah
1. S
2. B
3. B
4. S
5. B

Pembelajaran tahap 2
1. Hacker : menunjuk kepada kejahatan terhadap data-data dan perusakan sistem.
Cracker : menunjuk kepada kejahatan seperi pembajakan program.
2. Database elektronik.
3. Enkripsi mengubah data yang bisa dibaca ke dalam bentuk yang tidak bisa dibaca.
4. Kesalahan prosedural : kesalahan yang terjadi karena tidak mengikuti prosedur yang benar.
5. Kesalahan dan kecelakaan, bencana alam, kejahatan komputer, dan pelaku kejahatan komputer.
6. – Tindakan melanggar hukum yang dilakukan pada komputer dan telekomunikasi
– Penggunaan komputer atau telekomunikasi untuk melakukan tindakan yang melanggar hukum
7. Phishing : mengirimkan email palsu yang mengarahkan penerima email untuk berkunjung ke tiruan halaman web yang asli.
8. Identitas diri.
9. a. Apa yang anda miliki-kartu,kunci, tanda tangan, kartu identitas
b. Apa yang anda ketahui-pin, password
c. Siapa anda – ciri-ciri fisik
10. Akibat sampingan dari manufakturing, akibat sampingan dari limbah, kerusakan lingkungan, dan risiko teknologi nano.
11. Pembagian digital : pembagian teknologi dalam jangka panjang yang akan memberikan manfaat bagi semua orang.

Pembelajaran tahap 3
Pengetahuan praktis
1. Keugian pada kesehatan. Untuk menyelesaikannya adalah dengan mengurangi penggunaan komputer.
2. Tidak banyak forum-forum yang membicarakan hal apa saja, tanpa mensensor nya. Dengan mensensor sesuatu itu sama saja membunuh kebebasan berbicara seseorang
Latihan web
3. Saya tidak punya masalah dengan internet. Saya bisa mengatur cara penggunaan internet saya sendiri
4. Itu sebenar nya tegantung dari tujuan dari si pengguna nya. Jika memang pengguna nya di tuntut untuk selalu berada di depan komputer bukan lah suatu kesalahan, lain hal nya kalau ia yang memang lebih suka di depan computer dari pada hidup bermasyarakat.

Pembelajaran tahap 1
11. Robotika
12. Pemroses bahasa alami
13. Kecerdasan tiruan
14.
16. Pencurian identitas
17. SQL
Pilihan ganda
6. C
7. C
Pembelajaran tahap 2
6. Kegunaan sistem pakar : membantu pengguna memecahkan masalah-masalah yang tidak membutuhkan pendampingan dari pakar manusia.
11. Agen cerdas : mengawasi bagaimana tugas-tugas dikerjakan, mengajukan pertanyaan, dan melakukan tugas-tugas.
12. Perangkat lunak dan head gear khusus.
13. AI lemah : mensimulasikan kesadaran manusia
AI kuat : berpikir pada tingkat tertentu yang setidaknya sama seperti manusia dan bahkan sadar akan dirinya.
14. Sistem pakar, pemroses bahasa alami, agen cerdas, pengenal pola, fuzzy logic, realitas virtual dan perangkat simulasi, robotika.
15. DSS : mendukung keputusan-keputusan dalam industri khusus.
ESS : mendukung pengambilan keputusan strategis.

Pembelajaran tahap 3
Pengetahuan praktis
4. Jenis robot industri. Robot tersebut dapat merakit berbagai barang-barang elektronik hingga kendaraan bermotor.
5.

1. Pembelajaran Tahap 2 (Soal no.8)

8. e-commerce: electronic commerce; pembelian produk dan jasa melalui jaringan computer.
e-commerce: adalah penyebaran, pembelian, penjualan, pemasaran barang dan jasa melalui sistem elektronik seperti internet atau televisi, atau jaringan komputer lainnya. E-commerce dapat melibatkan transfer dana elektronik, pertukaran data elektronik, sistem manajemen inventori otomatis, dan sistem pengumpulan data otomatis.

2. Pembelajaran Tahap 3 (Pengetahuan Praktis soal no.6, dan no.7; Latihan web no.1)

Pengetahuan praktis:
6. harus, karena mau bagaimana pun semua barang yang di jual di e-commerce di lindungi oleh Negara dimana ia bertempat, oleh karena itu tidak lah suatu yang aneh jika Negara meminta pajak dari e-commerce.

7. saya tidak setuju dengan orng seperti itu, kenapa? Karena seperti yang kita ketahui di jaman modern seperti sekarang ini hampir semua aktivitas manusia tidak bisa lepas dari computer, yang memudahkan kita dalam menyelesaikan tugas kita. Sesuatu yang patut disayangkan juga kemudahan itu tidak di pergunakan. Computer mampu menyimpan semua record yang kita masukan, sungguh sesuatu yang sangat memudahkan kita dalam pengesian database.

Latihan web:
1. Iya karena dengan menggunakan pay-pal sangat memudahkan kita jika kita ingin membeli barang yang di tawarkan di internet. Dengan pay-pal kita seakan-akan mempunyai “bank” baru yang bisa di gunakan di untuk membeli barang secara credit yang di akui di seluruh dunia. Inilah keuntungan nya yang bisa kita dapatkan. Membuat semua transaksi menjadi memungkinkan.

Pembelajaran tahap 1
1. File
2. Record
3. Administrator database
4.
5. Hierarkis, jaringan, relasional, berorientasi objek, dan multidimensional.
6. Program, data
7. Kompresi
8. Karakter/byte
9. Database
10. Record
11. Robotika
12. Pemroses bahasa alami
13. Kecerdasan tiruan
14.
15. Pencurian identitas
16. Penelitian dan pengembangan, produksi (operasi), pemasaran dan penjualan, akuntansi dan keuangan, SDM, dan SI.
17. SQL

Pertanyaan pilihan ganda
1. C
2. C
3. B
4. E
5. D
6. C
7. C

Pertanyaan benar/salah
1. B
2. S
3. B
4. S
5. B
6. S
7. B
8. S
9. S
10. S
11. S
12. S

Pembelajaran tahap 2
1. Tugas adiministrator database : menentukan hak akses pengguna, membantu membuat prioritas permintaan, mengembangkan dokumentasi dan prosedur input.
2. Data mining : proses penyaringan dengan menggunakan komputer, dengan cara menganalisis sejumlah besar data untuk mendapatkan pola-pola dan makna tersembunyi dan untukmenemukan pengetahuan baru.
3. Data warehouse : database yang memuat data dan metadata yang telah dibersihkan, yang disimpan dengan menggunakan teknologi penyimpan disk berkapasitas tinggi.
4. Pengulangan data berkurang, integritas data meningkat, keamanan meningkat, dan kemudahan memelihara data.
5. File data berisi data-data, sedangkan file program berisi instruksi-instruksi.
6. Kegunaan sistem pakar : membantu pengguna memecahkan masalah-masalah yang tidak membutuhkan pendampingan dari pakar manusia.
7. SQL : bahasa standar yang digunakan untuk membuat, memodifikasi, mendapatkan, dan melakukan query database relasional.
QBE : fitur program bahasa query dimana pengguna bisa meminta informasi dalam suatu database dengan menggunakan record sampel untuk menentukan kualifikasi yang ia inginkan untuk record-record yang terpilih.
9. Sampaikan keluhan ke pihak yang terkait untuk mendaftarkan pencurian identitas Anda.
10. Daya tahan media penyimpanan yang terbatas.

Pembelajaran tahap 3
Pengetahuan praktis
1.
2. Tentu saja tidak nyaman, karena bisa saja terjadi pencurian data dan identitas.
Latihan web
5.

Pembelajaran tahap 1
1. Konvergensi
2. Podcast
3. Switched-network
4. Megapiksel
5. Multitasking
6. PDA
7. MP3
8. Ripping
9. HDTV
10. Point and shoot

Pertanyaan pilihan ganda
1. B
2. B
3. D
4. E
5. D

Pertanyaan benar/salah
1. B
2. S
3. S
4. S
5. B
6. S
7. S
8. S

Pembelajaran tahap 2
1. Cara kerja radio satelit : satelit yang mengorbit mengelilingi bumi mengirimkan sinyal ke para pelanggan yang memiliki radio khusus yang mampu menerjemahkan sinyal terenkripsi.
Keuntungan radio satelit : tidak ada iklan dan lebih banyak acara dibandingkan radio AM/FM.
2. Manfaat mash-up : seseorang dapat mengetahui keadaan ataupun berbagai hal lainnya yang sedang berlangsung atau terjadi pada suatu tempat kapan saja.
3. Karena file MP3 merupakan file audio dari CD yang sudah dikompresi menjadi ukuran yang lebih kecil.
4. Untuk berbagi (share) foto-foto yang ada serta sebagai sarana penyimpanan foto secara online.
5. Semakin besar sampling rate, semakin besar pula ukuran sebuah file audio.
6. Radio satelit menggunakan sinyal digital,sedangkan radio high-definition menggunakan sinyal digital dan analog.
7. Kamera single-lens reflex, karena kualitas hasil fotonya lebih bagus.

Pembelajaran tahap 3
Pengetahuan praktis
3. Pertanyaan mengenai kualitas hasil fotonya, fitur-fitur kameranya, bagaimana dengan kualitas dari aftersalesnya, dll.
4. Kamera digital dihubungkan dengan komputer melalui kabel USB, lalu setelah terdeteksi oleh komputer foto-foto dari kamera dapat langsung ditransfer.
Latihan web
1. Hal ini memang sudah seharusnya dilarang, karena pemakaian ponsel di dalam pesawat dapat menggangu sistem navigasi pesawat sehingga dapat membahayakan penerbangan.

Pembelajaran tahap 1
1. Modem
2. WAN
3. Serat optik
4. Analog, digital
5. VPN
6. Server
7.
8. Modulator demodulator
9. Bluetooth, LAN
10. Firewall
11. Node
12. Protokol

Pertanyaan pilihan ganda
1. C
2. E
3. D
4. B
5. B
6. C
7. E

Pertanyaan benar/salah
1. B
2. B
3. B
4. B
5. B
6. S
7. S
8. S
9. B
10. S

Pembelajaran tahap 2
1. Intranet : jaringan privat internal dalam sebuah organisasi yang menggunakan infrastruktur dan standar dari internet dan web.
Ekstranet : intranet privat yang tidak hanya menghubungkan personel internal,tetapi juga pemasok terpilih dan pihak-pihak lain yang dipandang strategis.
2. WAN : cakupannya area geografis yang sangat luas, misalnya pada sebuah negara sedangkan LAN : cakupan geografisnya terbatas, misalnya hanya pada satu kantor.
3. Semakin besar bandwith sebuah media, maka transmisi pun bisa berlangsung semakin cepat.
4. Firewall : sistem perangkat keras dan atau perangkat lunak yang melindungi sebuah komputer atau jaringan dari penyusup.
5. 2G : layanan nirkabel digital yang menggunakan jaringan dari menara-menara sel untuk mengirim komunikasi suara dan data melalui gelombang udara dalam bentuk digital.
3G : teknologi broadband berbasis standar GSM AS dan mendukung piranti agar selalu on, mampu membawa data dengan kecepatan tinggi (144 Kbps – 2 Mbps).
6. Jaringan ring : semua node terhubung dalam loop yang kontinu.
Jaringan bus : semua node terhubung ke kabel yang sama (bus) dan memiliki 2 titik ujung.
Jaringan star : semua node terhubung langsung ke server pusat.
7. Spektrum elektromagnetik : dasar untuk semua sinyal telekomunikasi, baik yang dibawa oleh media kabel maupun nirkabel.
8. Protokol mengatur pertukaran data antarkomponen perangkat keras dan atau perangkat lunak dalam jaringan komunikasi.
9. Jangan memberitahukan username dan password Anda kepada siapapun, jangan menggunakan password yang mudah ditebak, dan hindari kata-kata yang mungkin muncul di kamus.
10. Manfaat enkripsi : untuk mencegah akses dari orang yang tidak berhak.

Pembelajaran tahap 3
Pengetahuan praktis
2. Ya, di masa depan saya akan memanfaatkan kabel modem.
6. Ya, karena ”telecommuting” lebih efisien.
Latihan web
3. Sistem GPS : rangkaian 24 satelit yang secara kontinu mentransmisikan sinyal radio yang dapat dipakai untuk mengidentifikasikan lokasi-lokasi di bumi.