RUMUSAN MASALAH YANG EKUIVALEN

RUMUSAN MASALAH YANG EKUIVALEN

Rumusan masalah yang ekuivalen, yaitu:

1.    Idompoten: p Ú p ≋ p atau p Ù p ≋ p

2.    Komutatif: p Ú q ≋ q Ú p atau p Ù q ≋ q Ù p

3.    Assosiatif: (p Ú q) Ú r ≋ p Ú (q Ú r) atau (p Ù q) Ù r ≋ p Ù (q Ù r)

4.    Distributif: p Ú (q Ù r) ≋ (p Ú q) Ù (p Ú r) atau p Ù (q Ú r) ≋ (p Ù q) Ú (p Ù r)

5.    De morgan:  ≋ Ù  atau  ≋  Ú

6.    Tautologi: p Ú  ≋ B

7.    Kontradiktif: p Ù   ≋ S

8.    Material implikasi: p Þ q ≋ Ú q

9.    Material ekivalensi: p Û q ≋ (p Þ q) Ù (q Þ p) ≋ (Ù q) Ú ()

ALGORITMA DJIKSTRA

ALGORITMA DJIKSTRA

Algoritma Djikstra digunakan untuk menentukan lintasan terpendek pada graph bobot.

Input   : Graph bobot G dengan s, t ∈ v(G)

Step 1  : Label titik s dengan ⋋(s) = 0 dan  verteks v ∈ G – {s} diberi label ⋋(v) = ∞.

            Tulis T = v(G).

Step 2  : Misalkan u ∈ T dengan ⋋(u) minimum.

Setp 3  : Jika u = t maka STOP dan beri pesan “:p lintasan terpendek dari s ke t adalah ⋋(t)”

Step 4  :  edge e=(u , v), ganti label v dengan ⋋(v) = min {⋋(v) , ⋋(u) + W(u , v)}

Step 5 : Tulis T = T – {u} dan pergi ke step 2.

Himpunan

 Himpunan

Himpunan H adalah kumpulan objek-objek yang telah didefenisikan:

v   Objek itu di sebut anggota atau elemen himpunan (notasi є ).

v   Banyaknya elemen sebuah himpunan disebut bilangan cardinal n(H).

Contoh:

Jika himpunan H (1,3,5), maka n(H) = 3

Beberapa jenis himpunan:

·                Himpunan semesta S adalah himpuan yang memuat semua elemen yang dibicarakan.

·                Himpunan kosong  ={ } adalah himpunan yang tidak memilki elemen.

·                Himpuna  bagian (Subset) , himpunan A merupakan himpunan bagian B bila setiap anggota A juga merupakan anggota B. disimbolkan dengan A  B.Banyaknya himpuan bagian dari B yang beranggotakan k anggota: c(n,k) = n!/k!(n-k)! ; k ≤ n.

·                Himpunan kuasa (Power set). Himpuan  kuasa dari hinpunan S adalah himpunan yang anggotanya seluruh himpuan bagian S. Di notasikan dengan 2^s.

·                Himpunan ekivalen. Himpunan A ekivalen dengan B (A=B), bila bilangan kardianal A samadengan bilangan B. n(A) = n(B).

·                Himpunan berpotongan. Himpunan A dan B berpotonagn, bila A dan B memiliki anggota persekutuan dan masing-masing memilki anggota yang bukan persekutuan.

·                Himpunan lepas. Himpian A dan B dikatakan lepas (di tulis A // B), apabila antara A dan B tidak mempunyai anggota persekutuan.