Friday, November 15, 2019

Algo Desain Analisis

1. Menurut saya pentingnya analisis algoritma adalah sbb:
  • Algoritma membantu kita memahami skalabilitas program kita.
  • Performa terkadang menjadi pembeda antara yang mungkin dilakukan dan yang tidak mungkin dilakukan.
  • Analisa algoritma memberi gambaran informasi tentang ‘perilaku program’ kita.
  • Mempelajari bagaimana menerapkan algoritma yang baik untuk kasus tertentu membedakan profesi system analyst dan programmer.
2. Untuk yang perlu dipahami lebih baik lagi mungkin ini pak:
  • Kompleksitas waktu (Time Complexity)
  • Kompleksitas ruang (Space Complexity)
  • Kecenderungan saat ini:
  • Ruang (hard disk) semakin murah
  • Kapasitas data yang diproses semakin besar
  • Waktu pemrosesan harus semakin cepat
  • Kompleksitas waktu menjadi variabel yang sangat penting

3. Sebuah algoritma dikatakan telah benar jika algoritma tersebut dapat memberikan keluaran yang benar jika menerima masukan sesuai dengan definisi algoritma tersebut, dan algoritma tersebut terbukti akan selalu dapat diterminasi (berakhir). Fungsi matematis inilah yang memiliki sebuah pembuktian untuk membuktikan pernyataan atau proses yang melibatkan perhitungan bilangan asli yang berulang. Contoh dari rumus matematis yang dapat dibuktikan dengan menggunakan induksi matematika yaitu perhitungan deret aritmatika, deret geometris, ataupun sigma bilangan.
=======================================================
Berikut ini ada tiga program A, B dan C sebagai berikut :
---------------------------------------
Program A
for(int i=1; i<=6; i++){
   cout<<"Value of variable i is: "<<i<<endl;
   }
---------------------------------------
Program B
for(int i=1; i<=6; i++){
   cout<<"Value of variable i is: "<<i<<endl;
   }
for(int j=1; i<=6; i++){
   cout<<"Value of variable j is: "<<j<<endl;
   }
---------------------------------------
Program C
for(int i=1; i<=6; i++){
   cout<<"Value of variable i is: "<<i<<endl;
   for(int j=1; i<=6; i++){
       cout<<"Value of variable j is: "<<j<<endl;
       }
   }
--------------------------------------
Menurut anda program manakah yang kompleksitasnya paling besar (paling kompleks) berikan aladannya?
Jawab : Menurut saya yang kompleksitasnya paling besar adalah program C, karena terdapat nested loop atau loop di dalam loop, dan itu menyebabkan kompleksitasnya menjadi O(n²) sedangkan 2 program lainnya sama sama memiliki kompleksitas yang hanya O(n)
Big O adalah sebuah notasi yang berisi metrik yang digunakan untuk mengukur kompleksitas suatu algoritma. Dengan adanya metrik ini akan membantu proses analisa suatu algoritma. Terdapat beberapa jenis Big O diantaranya :
O(1) - Constant Time : banyaknya input yang diberikan kepada sebuah algoritma, tidak akan mempengaruhi waktu proses (runtime) dari algoritma tersebut.
O(Log n) - Logarithmic Time : ketika kita memberikan input sebesar n terhadap sebuah fungsi, jumlah tahapan yang dilakukan oleh fungsi tersebut berkurang berdasarkan suatu faktor. Salah satu contohnya adalah algoritma Binary Search.
O(n) - Linear Time : ketika runtime dari fungsi kita berbanding lurus dengan jumlah input yang diberikan.
O(n^2) - Quadratic Time : ketika runtime dari fungsi kita adalah sebesar n^2, dimana n adalah jumlah input dari fungsi tersebut.
O(2^n) - Exponential Time : umumnya digunakan dalam situasi dimana kita tidak terlalu tahu terhadap permasalahan yang dihadapi, sehingga mengharuskan kita mencoba setiap kombinasi dan permutasi dari semua kemungkinan.
Soft Computing adalah segolongan metoda yang mampu mengolah data dengan baik walaupun didalamnya terdapat ketidakpastian, ketidakakuratan maupun kebenaran parsial (Prof. Lotfi A Zadeh, 1992).
Soft Computing dicetus pertama kali pada tahun 1990 sehubungan dengan ide untuk mendirikan BISC (Berkeley Initiative in Soft Computer) oleh Prof. L.A.Zadeh dari BerkeleyUniversity. Soft computing, berbeda dengan conventional (hard) computing, memungkinkan toleransi terhadap input, proses dan output yang bersifat tidak akurat(imprecision), tidak pasti (uncertainty) dan setengah benar (partial truth).
Bagian-bagian dari Soft Computing sendiri adalah :
1. Fuzzy Logic
2. Neural Networks
3. Probabilistic Reasoning
Kompleksitasnya operasi perkalian matrik : O(n3)
perkalian matrix harus berbentuk mn x np = mp (kolom dan baris)
1 3 x 3 3 = 1 3
2 2 x 2 2 = 2 2
maka complexitynya adalah
O(m*p);
karena baris matrix suku ke 1 dikali kolom matrix suku ke 2 kemudian dijumlahkan (dengan menggunakan array maka complexity time penjumlahan tidak berpengaruh saat akses penjumlahan)
Menurut saya peng-index-an merupakan salah satu cara untuk mengoptimalkan suatu kompleksitas dan tingkat kompleksitas menurut saya bisa menentukan harga suatu software, semakin rendah tingkat complexitynya semakin mahal, karena bisa semakin cepat softwarenya
Knapsack Problem Menurut saya adalah di link itu menjelaskan cara menyelesaikan suatu masalah jika di berika beberapa set itmes, yang masing masingnya mempunyai berat dan nilainya, dan akan di tempatkan di suatu tempat yang mempunyai batasan untuk menampung beratnya, dan juga untuk menyelesaikan masalah tersebut harus mengoptimalkan barang nilai total yang bisa masuk ke tempat tersebut.
Metode Greedy Locally-optimal adalah suatu kondisi dimana pilihan terbaik / optimal dibuat pada saat itu tanpa memperhitungkan keadaan secara global.
#PROSES REKURSIF

int fib(int n)
{
        if (n<-1)
                return n;
        return fib(n-1) _fib(n-2);
}

#PEMROGRAMAN DINAMIS

f[0] = 0;
f[1] = 1;

for (i=2; i <- n; i++)
{
        f[i] = f[i-1] + f[i=2];
}
return f[n];
Dari hasil percobaan saya memberikan nilai n yang berbeda pada kedua fungsi, pemrograman dinamis dapat memproses eksekusi lebih cepat dibanding metode rekursif terutama saat return dari fungsi menghasilkan data yang besar.

Saya ingin mempermudah sedikit sehingga tidak sulit untuk mempelajarinya, TSP

Step I
AB = 12
AC = 11
AD = 16
Paling pendek adalah AC = 11

Step II
Untuk ke B:
CB + AC = 14 + 11 = 25 (A-C-B)
DB + AD = 11 + 16 = 27 (A-D-B)

Untuk ke C:
BC + AB = 15 + 12 = 27 (A-B-C)
DC + AD = 17 + 16 = 33 (A-D-C)

Untuk ke D:
BD + AB = 10 + 12 = 22 (A-B-D)
CD + AC = 18 + 11 = 29 (A-C-D)

Paling pendek adalah ABD = 22
Simpan paling pendek kedua ACB = 25

Step III
Untuk ke B:
CB + (A-D-C) | DB + (A-C-D)
14 + 33 | 11 + 29
47 | 40
Paling pendek ACDB = 40

Untuk ke C:
BC + (A-D-B) | DC + (A-B-D)
15 + 27 | 17 + 22
42 | 39
Paling pendek adalah ABDC = 39

Untuk ke D:
BD + (A-C-B) | CD + (A-B-C)
10 + 25 | 18 + 27
35 | 45
Paling pendek adalah ACBD = 35

Jadi paling pendek dari ketiga ini adalah ACBD = 35 sehingga step sebelumnya  ABD = 22 tidak berlaku dan yang dipakai adalah ACB = 25.

Step IV
Untuk A:
BA + ACDB | CA + ABDC | DA + ACBD
15 + 40 | 8 +39 | 9 + 35
55 | 47 | 44

Jadi jarak paling terpendek adalah ACBDA = 44.
Bagaimana cara mengekspresikan skema Travelling Salesman Problem menjadi sebuah matrik TSP?
Caranya adalah dengan kita meletakkan satu per satu, dimana:

1.Dimulai dari node A
Node A menuju ke node A maka nilainya " ∞ ", mengapa? karena kembali ke dirinya sendiri. 
Node A menuju ke node B maka nilainya 12.
Node A menuju ke node C maka nilainya 11.
Node A menuju ke node D maka nilainya 16.

2.Dimulai dari node B
Node B menuju ke node A maka nilainya 15.
Node B menuju ke node B maka nilainya " ∞ ", mengapa? karena kembali ke dirinya sendiri.
Node B menuju ke node C maka nilainya 15.
Node B menuju ke node D maka nilainya 10.

3.Dimulai dari node C
Node C menuju ke node A maka nilainya 8.
Node C menuju ke node B maka nilainya 14.
Node C menuju ke node C maka nilainya " ∞ ", mengapa? karena kembali ke dirinya sendiri.
Node C menuju ke node D maka nilainya 18.

4.Dimulai dari node D
Node D menuju ke node A maka nilainya 9.
Node D menuju ke node B maka nilainya 11.
Node D menuju ke node C maka nilainya 17.
Node D menuju ke node D maka nilainya " ∞ ", mengapa? karena kembali ke dirinya sendiri.

Sehingga saya menyimpulkan dan ingin menambahkan kekurangan pada gambar matriks itu sehingga mungkin bisa memudahkan bagi rekan-rekan semuanya.

Matrix TSP

       A        B        C        D
A     ∞       12      11      16

B    15       ∞       15      10

C    8        14       ∞      18

D    9        11      17       ∞
Forward Method Jarak Terpanjang

Step I
Level V4
IL = 7
JL = 8
KL = 11
Paling panjang KL = 11

Step II
Level V3
Untuk F:
3F = FI + IL | FJ + JL
3F = 12 + 7 | 9 + 8
3F = 19 | 17
Paling panjang FIL = 19

Untuk G:
3G = GI + IL | GJ + JL
3G = 5 + 7 | 7 + 8
3G = 12 | 15
Paling panjang GJL = 15

Untuk H:
3H = HJ + JL | HK + KL
3H = 10 + 8 | 8 + 11
3H = 18 | 19
Paling panjang HKL = 19
Jadi paling panjangdari ketiga ini adalah  HKL = 19 karena lanjutan step I terpanjang KL = 11

Step III
Level V2
Untuk B:
2B = BF + FIL | BG + GJL | BH + HKL
2B = 4 + 19 | 8 + 15 | 11 + 19
2B = 23 | 23 | 30
Paling panjang BHKL = 30

Untuk C:
2C = CF + FIL | CG + GJL
2C = 10 + 19 | 3 + 15
2C = 29 | 18
Paling panjang CFIL = 29

Untuk D:
2D = DH + HKL
2D = 9 + 19
2D = 28
Paling panjang DHKL = 28

Untuk E:
2E = EG + GJL | EH + HKL
2E = 6 + 15 | 12 + 19
2E = 21 | 31
Paling panjang EHKL = 31
Jadi paling panjang dari keempat ini adalah EHKL = 31

Step IV
Level V1

1A = AB + BHKL | AC + CFIL | AD + DHKL + AE + EHKL
1A = 7 + 30 | 6 + 29 | 5 + 28 | 9 + 31
1A = 37 | 35 | 33 | 40

Jadi jalur paling terpanjang dari A menuju ke L adalah AEHKL = 40.
Backward Method Jarak Terpanjang

Step I
AB = 7
AC = 6
AD = 5
AE = 9
Paling panjang AE = 9

Step II
Level V3
Untuk F:
3F = BF + AB | CF + AC
3F = 4 + 7 | 10 + 6
3F = 11 | 16
Paling Panjang ACF = 16

Untuk G:
3G = BG + AB | CG + AC | EG + AE
3G = 8 + 7 | 3 + 6 | 6 + 9
3G = 15 | 9 | 15
Paling panjang AEG = 15 dan bisa juga ABG = 15

Untuk H:
3H = BH + AB | DH + AD | EH + AE
3H = 11 + 7 | 9 + 5 | 12 + 9
3H = 18 | 14 | 21
Paling panjang AEH = 21

Jadi paling panjang dari ketiga ini adalah AEH = 21

Step III
Level V4

Untuk I:
4I = FI + ACF | GI + AEG
4I = 12 + 16 | 5 + 15
4I = 28 | 20
Paling panjang ACFI = 28

Untuk J:
4J = FJ + ACF | GJ + AEG | HJ + AEH
4J = 9 + 16 | 7 + 15 | 10 + 21
4j = 25 | 22 | 31
Paling panjang AEHJ = 31

Untuk K:
4K = HK + AEH
4K = 8 + 21
4K = 29
Paling panjang AEHK = 29

Jadi paling panjang dari ketiga ini adalah AEHJ = 31
Simpan paling panjang kedua AEHK = 29

Step IV
Level V5

5L = IL + ACFI | JL + AEHJ | KL + AEHK
5L = 7 + 28 | 8 + 31 | 11 + 29
5L = 35 | 39 | 40

Jadi paling panjang AEHKL = 40, maka step III AEHJ tidak berlaku tapi yang dipakai AEHK = 29.
Forward Method Terpendek

Mari kita jelaskan satu per satu, pertama kita jangan mulai dari depan/node awal tetapi mulai dari node akhir/node tujuan dimana L adalah node akhir.

Step I
Level V4
IL = 7
JL = 8
KL = 11
Jadi yang paling pendek adalah IL = 7

Step II
Level V3
Cek satu per satu,
Untuk F:
3F = FI + IL | FJ + JL
3F = 12 + 7 | 9 + 8
3F = 19 + 17
Paling pendek FJL = 17

Untuk G:
3G = GI + IL | GJ + JL
3G = 5 + 7 | 7 + 8
3G = 12 | 15
Paling pendek GIL = 12

Untuk H:
3H = HJ + JL | HK + KL
3H = 10 + 8 | 8 + 11
3H = 18 | 19
Paling pendek HJL = 18

Jadi dari ketiga ini pada level V3 paling pendek adalah GIL = 12

Step III
Level V2
Cek satu per satu,
Untuk B:
2B = BF + FJL | BG + GIL | BH + HJL
2B = 4 + 17 | 8 + 12 | 11 + 18
2B = 21 | 20 | 29
Paling pendek BGIL = 20

Untuk C:
2C = CF + FJL | CG + GIL
2C = 10 + 17 | 3 + 12
2C = 27 | 15
Paling pendek CGIL = 15

Untuk D:
2D = DH + HJL
2D = 9 | 18 = 27, maka paling pendek DHJL = 27

Untuk E:
2E = EG + GIL | EH + HJL
2E = 6 + 12 | 12 + 18
2E = 18 | 30
Paling pendek adalah EGIL = 18

Jadi dari keempat ini pada level V2 paling pendek adalah CGIL = 15

Step IV
Level V1

1A = AB + BGIL | AC + CGIL | AD + DHJL | AE + EGIL
1A = 7 + 20 | 6 + 15 | 5 + 27 | 9 + 18
1A = 27 | 21 | 32 | 27

Jadi jalur paling terpendek dari A menuju ke L adalah ACGIL = 21
Backward Method Terpendek

Step I
Level V2

AB = 7
AC = 6
AD = 5
AE = 9

Paling pendek AD = 5
Simpan paling pendek kedua AC = 6

Step II
Level V3
Untuk F:
3F = BF + AB | CF + AC
3F = 4 + 7 | 10 + 6
3F = 11 | 16
Paling pendek ABF = 11

Untuk G:
3G = BG + AB | CG + AC | EG + AE
3G = 8 + 7 | 3 + 6 | 6 + 9
3G = 15 | 9 | 15
Paling pendek adalah ACG = 9

Untuk H:
3H = BH + AB | DH + AD | EH + AE
3H = 11 + 7 | 9 + 5 | 12 + 9
3H = 18 | 14 | 21
Paling pendek adalah ADH = 14
Jadi dari ketiga ini pada level V3 paling pendek adalah ACG = 9 sehingga pada step I tidak berlaku AD = 5 tapi yang dipakai AC = 6.

Step III
Level V4
Untuk I:
4I = FI + ABF | GI + ACG
4I = 12 + 11 | 5 + 9
4I = 23 | 14
Paling pendek adalah ACGI = 14

Untuk J:
4J = FJ + ABF | GJ + ACG | HJ + ADH
4J = 9 + 11 | 7 + 9 | 10 + 14
4J = 20 | 16 | 24
Paling pendek adalah ACGJ = 16

Untuk K:
4K = HK + ADH
4K = 8 + 14
4K = 22, maka paling pendek ADHK = 22

Jadi dari ketiga ini pada level V4 paling pendek adalah ACGI = 14

Step IV
Level V5

5L = IL + ACGI | JL + ACGJ | KL + ADHK
5L = 7 + 14 | 8 + 16 | 11 + 22
5L = 21 | 24 | 33

Jadi jalur terpendek dari A menuju ke L adalah ACGIL = 21
Baca dan pelajari LN tentang Huffman Code, kemudian : Buat tabel frekuensi, Huffman Tree, dan Huffman Code untuk mengkompres serta Total Compression Rate untuk kalimat  DESIGN AND ANALYSIS OF ALGORITHMS

Tabel Frekuensi

-Tabel frekuensi dibentuk dari frekuensi kemunculan karakter dalam sebuah file.

D  E  S  I  G  N  A  L  Y  O  F  R  T  H  M

2  1  4   3  2  3   4  2  1   2  1   1  1  1   1

Hasil tersebut nantinya diurutkan menjadi:

E  Y  F  R  T  H  M  D  G  L  O  I  N  S  A

1  1  1   1  1   1   1   2   2  2  2  3  3  4  4

Pembentukan ini melihat urutan kemunculan kata
Huffman Code

Pembentukan Huffman Code akan menggantikan nilai bit ASCII dari masing-masing karakter dimana pemberian nilai akan dilihat dari jalur tree ke node tersebut, kiri bernilai nol dan kanan bernilai 1.

Character                   Huffman Code                         Huffman Bit

        E                             010101                                  6 Bit

        Y                             110101                                  6 Bit

        F                              011001                                  6 Bit

       R                              111001                                  6 Bit

       T                               010001                                 6 Bit

       H                              110001                                  6 Bit

       M                              00001                                   5 Bit

       D                              01001                                    5 Bit

       G                              00101                                    5 Bit

        L                              01101                                    5 Bit

       O                              11101                                     5 Bit

       S                               011                                        3 Bit

       A                               111                                         3 Bit

       I                                 00                                          2 Bit

      N                                10                                          2 Bit

Bagaimana Algoritma graph coloring ?
Apakah graph coloring merupakan NP complete?
Aplikasi apa yang dapat diselesaikan dengan graph coloring ?
Apakah graph coloring termasuk discrete mathematics?
Berapa banyak warna yang dibutuhkan untuk mewarnai peta?
Apakah tiga warna cukup untuk masalah graph coloring?

1.Mencatat simpul yang bertetanggaan,mewarnai simpul dengan titik bertetangga paling banyak,melihat simpul yang tidak bertetangga dan mewarnai simpul itu,kembali ke step 2
2.sepertinya tidak menurut wikipedia np complete harus bisa di solve dengan menggunakan serangkaian algoritma brute forces search sedangkan welsh powell terlihat seperti dynamic programming
3.penjadwalan (ujian,shift,dsb),travelling salesman problem,stained glass,warna pada peta.
4.iya termasuk discrete mathematic karena discrete mathematic adalah cabang matematika yang menyelesaikan hal" yang berkaitan informasi seperti ini
5.n warna yang penting liat saja adj matrixnya dan mensolve dengan cara no 1
6.tergantung graphnya kalau graph complete dengan n>3 pasti pewarnaanya berjumlah n, saya hanya bisa memberikan contoh ini maaf

Pengodean Huffman adalah teknik paling populer untuk menghasilkan kode tanpa awalan. Algoritma ini sangat efisien di bidang pengkodean karena menghasilkan jumlah simbol kode terendah dari satu simbol sumber. Pengodean Huffman adalah teknik kompresi lossless yang paling banyak digunakan. Namun, ada beberapa batasan yang muncul dalam pengkodean Huffman. Metode ini menghasilkan kode beberapa bit untuk suatu simbol yang memiliki probabilitas kemunculan yang tinggi dan sejumlah besar bit untuk suatu simbol yang memiliki probabilitas kejadian yang rendah. Dalam Double Huffman Coding ketika kata kode dari simbol telah dihasilkan akan dikompresi berdasarkan binerm hasilnya menjadi lebih baik.(Arshad, 2017)

Backtracking 5-Queen


Breadth-first search adalah algoritma yang melakukan pencarian secara melebar yang mengunjungi simpul secara preorder yaitu mengunjungi suatu simpul kemudian mengunjungi semua simpul yang bertetangga dengan simpul tersebut terlebih dahulu.

DFS (Depth-First-Search) adalah salah satu algoritma penelusuran struktur graf / pohon berdasarkan kedalaman. Simpul ditelusuri dari root kemudian ke salah satu simpul anaknya ( misalnya prioritas penelusuran berdasarkan anak pertama [simpul sebelah kiri] ), maka penelusuran dilakukan terus melalui simpul anak pertama dari simpul anak pertama level sebelumnya hingga mencapai level terdalam.




















Top