halo halo semuanya Selamat datang di kuliah desain dan analisis algoritma di video ini saya akan menjelaskan tentang algorithm correctness atau kebenaran dari algoritma Bagaimana cara kita tahu suatu algoritma itu benar-benar hai Sebelumnya saya ingin menjelaskan terlebih dahulu Apa itu sedot karena kebanyakan agusnadi kuliah ini akan kita jelaskan dengan menggunakan sudah kok Sudah kota ini sebenarnya adalah bahasa manusia ia menyerupai kode ya Sesuai dengan arti kata sedoyo itu Serupa tapi tak sama Nah kita akan menggunakan bahasa Indonesia atau bahasa Inggris tapi kita pinjam ya primitif atau konsep pemograman dari bahasa si atau Java seperti Saiman variabel atau for-loop we look if else dan beberapa lainnya tapi kita tidak peduli dengan tatabahasa sih atau siapa ya tadi kita tetap menggunakan bahasa manusia owner Nah kita sering akan menggunakan kalimat yang paling jelas paling singkat untuk mendeskripsikan satu langkah diawetkan kita detail implementasi akan sering kita abaikan demi menyampaikan esensi dari algoritmanya misalnya kalau saya mau menukar isi dua variabel x dan y cukup bilang tukar reaksi ya teman-teman mungkin tahu bahwa detail implementasi Bagaimana cara menukar isi dua variabel x dan y itu sedikit lebih ribet dari hanya kata-kata tukar extend a good me pertama yang kita bahas adalah yang sensor instructions or ini adalah algoritma bisa kita gunakan untuk mengurutkan data di sebuah les atau Arai urutan disini maksudnya urutannya naik ya Nah itu sensor ini efisien untuk juga datang kecil kalau besar mungkin kita gunakan agoritma lainnya lebih efisien kata2 properti atau sifat dari investor yang ingin saya Mansion di sini pertama dia seperti Black artinya data itu terurut diinput arah yang sama jadi kita nggak perlu Arai tambahan untuk mengurutkan data disetiap langkah Kalaupun kita harus menyimpan datanya di luar Arai hanya sejumlah konstan dari mereka yang perlu disimpan Selain itu sifat dari ekstensor adalah dia Stable artinya urutan relatif dan data-data duplikat atau data yang sama itu enggak berubah dalam hasil akhirnya dalam arah yang perutnya karena di sini kan ada duplikasi dua sebanyak tiga buah dan duplikasi tiga Nah urutan relatif mereka itu enggak berubah Kau temannya di sini angka 2nya itu ada warna biru merah kuning di hasil urut di hasil akhirnya yang terurut itu Hai tetap urutannya biru merah kuning untuk data yang sama yaitu dua disini begitu juga dengan 33 hitam dan 3 hijau urutan mereka tidak berubah di hasil akhir Hai arahnya sekarang saya akan menjelaskan algoritma insertion sort menggunakan sedot yang pertama sini ada nama algoritmanya isu sensor kemudian saya sekilas inputnya dalam hal ini adalah sebuah array yang bernama ah kemudian ada for-loop nih ya ini kita meniru gaya penulisan bahasa pemrograman dan apa yang dilakukan di setiap produk itu kita spesifikasi agak menjorok ya jadi jelas itu apa yang diulang ini sekelompok kode ini dari baris 2-9 kemudian fourlook nya memiliki satu variabel J yang nilainya dari 23456 dan seterusnya sampai panjang ayat ini nilainya di-update atau ditambahkan di setiap iterasi jadinya meleleh tua kita sedikitnya tiga kita sih berikutnya fat dancenya sampai panjangnya berapa Hai kemudian saya punya satu variabel disekresi sayap buat satu variabel King yang nilainya adalah AJ jadi saya mengambil elemen keji dari kemudian saya di sini ada komentarnya katanya Insert AJ yg ntu the short sekuens 11@gmail.com Artinya apa itu saya berarti ingin mencoba memasukkan ajak ke supari disebelah kirinya tapi kita di sini ada klien katanya A1 sampai ajarin satu terurut Nah mungkin bentuk memasukkan AJ dalam asal sampai dia minta tuh kita perlu mematikan pemasukannya masih sesuai urutan ya Jadi tidak merusak ke urutan dari A1 sampai Aji yang saya lakukan untuk mencapai itu pertama saya siapkan satu variabel yang nilainya adalah jamin satu seperti ini semacam menunjuk elemen nanti menunjuk elemen di sebelah kiri Aceh Hai nah saya lakukan we look ini ada we look yang dilakukan selama ingat besar dari nol dan airnya besar dari Gigi Hai artinya kalau ini an0 kita keluar dari loop dan kalau airnya kurang dari sama dengan key atau elemen kunci tadi airnya itu besar kurang Desmond kita juga keluar dari Nah kalau seandainya belum tercapai itu kita lakukan aib satu sama dengan air ini kan mesin Aik ke dalam air persatu atau sebelah kanannya jadi ini sebenarnya yang akan adalah geser iklan ke Hai yang lalu kalau sudah digeser raikkonen itu kita akan ininya ingin satu berdirinya geser kekiri nya jadi kita menggeser elemen-elemen yang lebih besar dari ikan kalau seandainya elemen tersebut sudah kurang dari semua rezeki kita Biarkan kita lanjut yang kita lakukan adalah atau kalau ia sudah nol kita juga keluar dari grup ya kita lakukan adalah masukkan Ki disebelah kanan kirinya jadi epl1 itu isynergy saya akan berikan Hai lupa Arai 41253 hanya Disini di awal upnya dua berpikir saya adalah Oh ya kakinya saya satu saya memperhatikan Arai sebelah kiri satu ya Pak ini ada terlalu tempat yang Salahkanlah periksa Apakah ya Iya kan satu ya karena jahenya dua Iya satu awalnya ininya satu saya cek Apakah ia sadari q4 besar Enggak dari Q1 Iya nabati empatnya Sagita tekanan kemudian Iya saya geser jadi satu dikurang satu jadi nol karena ia sudah nol Saya keluar dari grup ya keluar dari yuk ip1 yaitu A1 saya isi dengan kiri satu saya jadi saya dapatkan sekitar aksi pertama Arai berupa 1425 akhir-akhir Moreno Hai selanjutnya saya lanjut ke jne-nya tiga berpikirnya disini adalah dua kalau punya dua batin saya akan memasukkan dua ke dalam sup Arai 214 ya Vatikan bawah iya mulai dari dua kemudian empat itu kan besar dari dua berarti saya geser 4 n Hai kemudian ingat satu A1 yaitu satu itu ternyata lebih kecil dari dua ya berarti saya keluar dari lux nih Saya enggak geser kekanan pizza ya memasukkan ia akan satu setia dua saya masukan keyboard yg disini aduannya 2-nya saya masukkan ke A22 lalu disini satu ya satunya dibiarkan tidak ada perubahan 53 juga tidak ada perubahan Hai kemudian saya lanjut ke J = 4 Y = 4 itu saya kirinya adalah lima ya ini J2 j3 smg4 Q5 itu batin saya mengertikan mint masukkan dia ke Subway 124 perhatikan nih arahnya terurut ya 24 Tapi saat ingat sama dengan 3.5 tak airnya yaitu empat itu sudah kurang dari 5 jadi saya keluar dari fourlook saat keluar dari for looking akan tiga batin saya masukkan A4 dengan lima jadi tidak ada perubahan Parai 10 Kita cuman menulis ulang Linux ke tempat yang sama dengan posisi awalnya terakhir jne-nya adalah panjang dari arahnya yaitu lima ini terakhir tersakiti saya adalah Oke saya ingin masukkan tiga dalam suara ini yang sangat lelah 5 itu saya geser ke kanan ya 5 karena 50034 saya geser kekanan juga ya dua itu karena tiga mati selesai saya masukkan ke a33w layar21 nah saya dapatkan Arai yang terurut sekarang oke Hai dari contoh eksekusi insertion sort algoritma sebelumnya kita melihat pola nih bahwa elemen-elemen A1 sampai aja minta to itu elemen-elemen yang sama pada posisi 1-1 di Arai awal kita hanya saja mereka sudah turun naik dari observasi ini kita pengen buat sebuah pernyataan formal yang kita sebut sebagai lebih varian lu pencarian adalah suatu pernyataan formal yang membantu kita memahami mengapa sebuah algoritma iterative itu benar-benar algoritmanya benar saat dia memberikan output yang sesuai dengan harapan kita nggak Hai invariant disini artinya tidak berubah yang tidak berubah dari pernyataan ini adalah kebenarannya artinya pernyataan ini harus benar sebelum setiap sebuah iterasi dijalankan dari hidup tersebut Lupin varian dari hidrasi yang ada di Instagram kita adalah sebagai berikut d'sub Arai A1 sampai jamin satu consists of the Elements originally In A 1 sampai jamin 1.bab in short order Hai kau teman-teman ingin membuktikan keberhasilan Wagon menggunakan doping varian ada tiga hal yang perlu teman-teman buktikan terkait varian tersebut tinggal tersebut biasanya disebut initialization maintenance dan juga termination ini season bilang it is through prayer to diversity of Prayer in sebelum jadi teman-teman harus buktikan bahwa invariant teman-teman itu benar sebelum itu masih pertama dari lu punya dijalankan ya ini biasanya dilakukan dengan memperhatikan nilai-nilai yang desain ke variabel sebelumnya dijalankan selanjutnya maintenance maintenance Villa if it is true bivora nutrition of the IT reminds ruby for the next perhatikan bahwa pernyataan jika maka ya Hai jadi dalam bahasa yang lebih matematis maintenance bilang jika Lupin varian itu benar tepat sebelum iterasi kekal Hai maka Lupin varian juga benar tepat sebelum iterasi ke flash satu ini artinya iterasi kekal tidak mengubah nilai kebenaran dari lebih Faranita makanya namanya Medan Hai Houdini ada termination termination bilang saat klubnya terminal Hai invariant kita memberikan informasi yang berguna untuk menjelaskan Kenapa algoritmanya benar tidak semua invariant itu bermanfaat ya Misalnya tautologi goreng sapi atau Novi ini adalah suatu pernyataan yang benar baik di ini solution m dan tapi dia tidak menceritakan apa-apa tentang algoritma kita jadi Pilihlah pilihlah lebih varian yang ia mengatakan sesuatu tentang apa yang aku teman-teman lakukan hal berikutnya ingin saya jelaskan adalah bahwa Lupin varian Hai tidak digunakan untuk membuktikan apakah suatu algoritma itu akhir-akhir minat atau tidak yo yah lu invariant hanya bisa digunakan untuk membuktikan kebenaran dari algoritma yaitu output yang dihasilkan algoritma itu sesuai dengan harapan kita dengan asumsi bahwa klubnya termini untuk membuktikan dunia terminated teman nanti perlu teknik lain saya Coba refresh pernyataan sebelumnya tiga hal yang perlu dibuktikan terkait looking varian ke dalam pertanyaan sebagai berikut jadi ini adalah pertanyaan-pertanyaan itu perlu teman-teman jawab gitu ya terkait kebenaran lebih varian initialization failed ruby forever station Apakah lo iparnya teman-teman itu benar sebelum iterasi pertama dimulai itu coba menjelaskan berikutnya maintenance sweety Strawberry Shortcake Interaction of the body needs to be true before the key person asumsikan teman-teman benar sebelum terus teman-teman lihat tuh bodynya ngapain aja lalu cek lebih parahnya benar sebelum iterasi ke kabel 1 Hai selanjutnya termination pertanyaannya adalah sebagai gua asumsi lupa minus jadi kita saksikan lognya termini Apakah is the invariant useful and showing the design atau movie algorithm jadi apa kalau Ivan kita tuh menjelaskan bahwa algoritma kita benar ini perlu teman-teman Jelaskan juga ya sebagaimana Saya bilang tadi perhatikan bahwa kita mengasumsikan bahwa klubnya term ini halo halo teman-teman ingin membuktikan blognya terminated kita perlu teknik lainnya tidak menggunakan looping varian Lupin parents kita adalah Desa Parai A1 sampai jamin satu berisi elemen-elemen original dia 1-1 hanya saja dalam urutan naik Ayo kita menjawab pertanyaan berikut untuk membuktikan kebenarannya pada inisialisasi apakah pernyataan kita ini Lupin varian kita ini benar sebelum Itachi pertama dimulai Hai sebelum iterasi pertama dimulai yaitu Saat dirinya Hai sub area 1-2 min 1 maka berisi hanya satu elemen yaitu A1 hai subarea satu ini tentu berisi hanya elemen original satu itu sendiri Hai Selain itu asupan arah yang sepanjang satu ini tentu sudah terurut karena hanya berisi satu elemen Hai di pernyataan kita benar kita inisialisasi selanjutnya saya akan coba menjelaskan kebenaran lebih varian kita pada maintenance pertanyaan adalah Apakah iterasinya atau body luknya mempertahankan kebenaran dari tempat yang kita sendiri pertama klubnya kita itu kan menggunakan variabel J jadi atasi kantuk 1J dopin varian kita benar jadi 1-1 benar dia berisi elemen-elemen original padahal jebmen satu posisi pertama arah input dan juga dia turun naik oke nah body dari Lupita tadi itu kita pahami dia bekerja dengan memindahkan ajimin satu Haji min 2 dan seterusnya ya ini elemen-elemen di sebelah kiri aja itu dipindahkan satu persatu kekanan sebesar satu posisinya hingga nanti posisi dari ac-nya ditemukan Oh iya posisi yang tepat untuk aja ya ditemukan itu dikerjakan oleh baris 5-8 ini ada lupa lagi tapi kita mencoba memahami apa Mami apa yang dilakukan oleh baris 5-8 tuh dengan kata-kata saja ya selanjutnya kalau sudah ditemukan posisi yang tepat untuk AJ ya itu kita Hai melakukan inversion ya kita masukkan aja itu ke posisi yang tepat itu dengan aseman air + 1 = Q Maka kalau kita lihat Apa yang dilakukan produknya menggunakan asumsi bahwa A1 sampai aja in 1 itu sudah turun naik ya maka proses tadi proses iterasi tadi itu juga akan mempertahankan kebenaran dari lebih parah kita tapi sekarang untuk A1 sampai je ya jadi A1 sampai je itu berisi Jln pertama dari Arai awal kita dan mereka dalam posisi terurut Kenapa posisi terburuk karena ac-nya kita letakkan di posisi dimana dia lebih besar dari semua elemen di sebelah kirinya Hai dan dia lebih kecil dari elemen disebelah kanannya terakhir correctness determination ketika klubnya terminated Apakah invariant kita membuktikan bahwa algoritmanya Ayo kita lihat apa yang terjadi saat dunia terminated ketika Loop berakhir Hai yaitu Saat dirinya lebih dari n di sini kita saksikan enaklah panjang dari H maka nilai J saat luknya berakhir adalah N + 1 kalau kita subtitusikan N + 1 ke dalam J di dalam statement looping varian Oh ya Ayo kita akan mendapatkan pernyataan bahwa A1 sampai aaa1 sampai n berisi elemen-elemen original diatur MPM ini narya namun dalam urutan terurut namun area 1-6 adalah seluruh arah yang ini kita Urutkan maka seluruh arah kita berhasil di Khan yang artinya algoritma kita Hai benar sebelum kita lanjut dengan jantung berikutnya Saya ingin menciptakan sedikit terkait asumsi akan kita ambil bahasa programan itu memberikan kita banyak cara untuk membuat lupa terhidrasi ditanya dengan we look for lu repeat until up sebagainya tapi kita akan fokus pada wailu teknik-teknik membuat blueprint varian pada wailu klub-klub lain selalu dapat kita buat dengan menggunakan Woi lu jadi tidak ada kemampuan komputasi yang terhilang kan disini dengan melapisi bahwa kita hanya fokus pada kebenaran dari program yang menggunakan File template dari lup yang kita gunakan adalah seperti sebagai berikut The Blues n dimana Duos gila compuland statement yang dilakukan disetiap kasih dan e adalah suatu kondisi ekspresi Eh ada dikepala wilux itu merupakan suatu kondisi yang biasa kita Nyatakan sebagai sebuah ekspresi boolean jadi layer protocols ekspresi ini nanti akan menentukan apakah blog kita akan mengeksekusi iterasi berikutnya atau keluar dari Nuh eh juga kita sebut sebagai klub atau penjaga dari kalau Lupita dieksekusi pada suatu state yang mengakibatkan kita bernilai false maka lupakan langsung berhenti tanpa mengubah kondisi program kita Nah kalau lu punya dieksekusi pada substrates yang mana Kayaknya bernilai true Hai maka Loop akan mengeksekusi barisan statement es yang ada di Badan lu dimana kita akan mendapatkan step baru nanti setelah barisan feat mannie diskusi semuanya kita akan berada pada subset baru kita sebut set baru itu essence kalau udah dapat set baru essence kita mungkin bisa lanjutkan ke eksekusi Club berikutnya Hai eksekusi dari Loop jadi bisa saja melalui beberapa state ya SS saxon dan seterusnya Hai ada kemungkinan untuk kita itu enggak pernah berhenti loh karena eh kita atau guard kita itu bernilai true untuk setiap step saat dia dicek maka kita sebagai programmer in perlu membuktikan bahwa lalu kita pasti berhenti saat ia butuhkan like Sekarang kita akan belajar algoritma yang bisa digunakan untuk mengalirkan dua buah bilangan asli A dan B yang dinamakan rasio multiplication jadi inputnya adalah dua buah bilangan a dan b outputnya adalah a * b Ayo kita bisa visualisasikan algoritma ini dengan dua buah kolom yang berisi bilangan-bilangan kolom pertama diawali dengan A dan kolom kedua diawali dengan B di kolom pertama kita melakukan pembagian dengan dua berkali-kali kalau perlu dengan pembulatan ke bawah Ayo kita lakukan sampai didapatkan no pada kolom kedua kita cukup kalikan dengan dua berkali-kali jika sudah selesai semua baris gimana bilangan di kolom pertamanya itu merupakan bilangan genap itu kita hapus atau abaikan kalau sudah semua bilangan di kolom kedua kita jumlahkan dan kita akan dapatkan hasil kali ada Berikut adalah contoh racing modification dari 57 dan 43 pertama kita buat bilangan 57435 sih kolom di kolom pertama kecelakaan pembagian2 berkali-kali kalau perlu dengan pemberatan jadi 57 kita bagi dua dapatkan 2828 kita dapatkan 14 kemudian 731 dan ini udah selesai karena satu dibagi dua kita dapat ini kemudian di kolom kedua setelah kalikan dengan dua berkali-kali 4386 10 besok 4608 dan 1376 kemudian kita hapus baris-baris Dimana bilangan di kolom pertamanya merupakan bilangan genap jadi kita tersisa dengan empat baris kita tinggal jumlahkan bilangan-bilangan yang ada di keempat baris sisanya kita dapatkan 2441 Ayo kita akan masker cerita Si Rasya notification algorithm dengan sebuah lu kita siapkan sebuah variabel total yang menampung awalnya nilai-nilai dan diakhir lu kita harapkan akan mengandung hasil kali dari a&b cce kita juga memiliki variabel x dan y yang akan kita gunakan untuk fun nilai-nilai di kolom pertama dan kolom kedua berturut-turut klubnya adalah sebagai berikut x diawali dengan a&y diawali dengan b dan total diawali dengan kita lakukan ini selama esnya besar darimu kalau bilangan di kolom pertama yaitu eksitu bernilai ganjil kita tambahkan y dalam total Hai jadi ini hanya dilakukan kalau FC ganjil kalau esnya biar genap kita tidak melakukan apa-apa setelahnya kita hitung bilangan pada baris berikutnya yaitu dengan melakukan x = x2 ini kita asumsikan sebagian dengan 2-nya merupakan floor yang menggunakan yups lantai dan y = y kali dua kita kalikan bilangan di kolom kedua dengan 2 Hai cukup hanya menspesifikasi instruksi-instruksi yang harus kita ikuti namun tidak ada penjelasan Kenapa mengikuti instruksi-instruksi tersebut akan memberikan kita hasil yang kita inginkan atau dengan kata lain tidak ada penjelasan Kenapa gold map mengetahui Mengapa algoritma benar itu sama aja dengan mengetahui pemeriksa Apakah hasil yang kita inginkan tersebut tercapai postcondition postcondition adalah sebuah statement yang menceritakan atau mendiskusikan hasil yang kita inginkan dari sebuah algoritma biasanya pakai di sini juga kita bisa katakan sebagai sebuah requirements nah tahu sarat yang ingin dipenuhi oleh sebuah algoritma-algoritma itu benar jika pos kondisinya kita biasa dengan P kondisinya itu benar-benar Hai pada akhir eksekusi algoritma postcondition bisa dinyatakan dengan kata-kata atau bisa juga dengan menyatakan nilai yang terkandung dalam suatu variabel sebagai contoh rasio notification kita mengharapkan postcondition adalah variabel total mengandung nilai hasil Kaliadem B pada akhir eksekusinya sehingga kita bisa mengembalikan nilai total sebagai jawaban dari algoritmanya saya akan coba visualisasikan apa yang terjadi saat kita mengeksekusi sebuah lup menggunakan step-step itu bisa teman-teman bayangkan Sebagai kondisi dari program saat itu atau bisa juga dibayangkan sebagai tabel yang berisi daftar variabel dan nilai yang dikandungnya pada Hai saat itu kita mulai dengan set awal kita sebut esmo Hai guys sakit ama eksekusi sebuah lup yang pertama kita lakukan adalah cek Apakah gardunya troops kalau tuh kita akan mengeksekusi body dari hidupnya yaitu es untuk mendapatkan fake baru kita sebut S1 dari S1 kita lanjutkan lagi kita periksa Apakah gardunya benar atau salah karena kalau true kita eksekusi body hidupnya untuk mendapatkan state lain S2 ini kita lakukan terus menerus hingga kita mendapatkan Satu Tetes F yang mana Hai jika grupnya diperiksa kita mendapatkan nilai pos dan karena kita hanya memeriksa di step ini statenya tidak berubah akan sangat-sangat bagi kita untuk mendeskripsikan cara sederhana Apa hubungan s0 yaitu step awal dengan SF itu step akhir dari sebuah lup tapi kita bisa melihat hubungan antara dua state berturutan s0 dan S1 dihubungkan oleh SS1 dan SS2 dihubungkan oleh es juga wujud Lupin varian Itu adalah sebuah predikat yang bisa mengandung variabel artinya the variable of Hai itu akan menentukan nilai kebenaran dari predikat kita variabel disini misalnya adalah variabel Loop pengen jadi Lupin varian Itu adalah sebuah pernyataan Hai yang mungkin mengandung variabel didalamnya namun Upin varian itu memiliki sifat khusus terhadap klub tersebut yaitu ia benar di setiap step yaitu s012 hingga SM jadi itu varian itu benar-benar oh yes no S1 S2 S3 sampai SF Hai langkah ini solution kita membuktikan Ih benar di is0 langkah maintenance adalah langkah induktif jadi kita buktikan jika es benar diet nol maka ini juga benar di S1 Hai jika yg benar di S1 maka ini juga benar di S2 dan seterusnya hingga yg benar di SF Hai langkah termination Ayo kita diminta untuk membuktikan bahwa jika yg ber sama-sama dengan informasi bahwa klubnya terminated kita bisa menimbulkan postcondition I hope berikut adalah visualisasinya dalam gambar yang lebih kompleks Oh iya adalah sebuah pernyataan yang benar di awal Loop sebelumnya mulai lalu kita cek Apakah Kenya benar bersamanya Kalau benar lanjut ke s s ini akan menghasilkan kondisi program yang mana ia juga benar Hai jika enya salah Ayo kita akan keluar dari loop dan bersama-sama dengan Lupin varian Idan Legacy e-akademik kan kita pos conditions hai magazine kembali kerasan multiplication problem kita tahu bahwa postcondition kita inginkan dari algoritma kita adalah variabel total pada akhirnya bernilai a * b the lounge Hai kemudian kita tahu ini sosok dari algoritma kita kita punya tiga variabel x y dan total dimana x nilainya a ya inilah GB atau Neneng Enno di awal program Hai untuk buktikan algoritma kita benar kita perlu buat sebuah pernyataan terbuka atau predikat artinya Ia adalah suatu kalimat yang mungkin punya variabel dan nilai kebenarannya tergantung variabelnya Nah kita inginkan agar ini predikat kita ini produk invariant kita ini benar diset Hai kemudian dia dipertahankan kebenarannya oleh satu kali eksekusi body Loop S Hai dan juga eh ini dia memberikan kita kesimpulan pos kondisinya terpenuhi yaitu total = a * b saat X besar dari nolnya Fals Hai salah satu invariant yang ber-bhinneka digunakan disini adalah total tambah x * y = a * b dan juga X100 ini dan pastikan bahwa Lupin varian kita melibatkan tiga variabel total X dan y a dan b kita atas sebagai konstanta karena ini tidak berubah selama lupa Hai sekarang saya akan Coba jelaskan kenapa racun multiplication benar menggunakan Lupin varian ini perhatikan bahwa ada tiga variabel disini yaitu total X dan Y dan kebenaran dari pernyataan ini bergantung pada nilai total x y saat itu nah diinisialisasi on kita tahu bahwa nilai x nya adalah a y nya awalnya adalah B dan total awalnya adalah Nah kita periksa kebenaran pernyataan kita dengan maksud sushi nilai x y dan total itu variabel-variabelnya dengan pada lebih parah kita yaitu 0 plus a * b = a * b karena total Enno xch dan ytde dan kita lihat begitu juga karena hanya besar = bilangan asli ini juga jadi lebih parah kita benar di di awal atau di sebelum eksekusi Lupi jalankan selanjutnya maintenance dimainin seperti kan bahwa kita berada pada iterasi berikutnya hanya kalau get looknya yaitu enya benar artinya karena gardu kita adalah x besar dari nol ini Benar Jadi ini otomatis narya Hai yang kita perlu khawatir karena dua Apakah persamaan ini tetap benar setelah melalui satu iterasi asumsikan total X dan Y adalah variabel yang lama variabel yang baru setelah melalui satu iterasi kita sebut total aksen-aksen dan ya apa yang didapatkan oleh variabel baru ini total aksen setelah menjalani operasi pada kasus X2 itu tidak ada perubahan sama sekali Hai karena kita hanya melakukan penambahan y pada total itu kalau X ganjil kemudian X saxon itu kita melakukan pembagian dengan dua pada X dan Y aksen kita melakukan perkalian dengan dua pada Idih yang perlu kita periksa adalah kalau seandainya total X dan Y memenuhi persamaan Apakah total X dan Y yang baru akan mendapatkan akan tetap membuat pesawat kita Ayo kita bisa periksa total aksen kan total Hai exsence nex2 dan hiasan adalah 2y dan kok kita teruskan ini sesuai dengan total tambah x * y karena expert dua kali dua kali adalah aksi dan kita tahu karena ini yang lama ya ini = ab jadi benar bahwa total Saint tambah X aksen kali itu tetap nilainya sama dengan bagaimana kalau esnya ganjil kalau saya ganjil nilai total yang baru adalah total tambahi total yang lama ditambah X yang baru itu adalah X2 di Flores dan teman-teman bisa verifikasi bahwa ekspor dua difluoride u = x min 1/2 kalau adzim Hai dan Y aksen itu adalah 2y Nah sekarang kita tinggal periksa total aksen tambah x aksen-aksen sama dengan total yang lama ditambah y ditambah kan xx yang baru yaitu x12 lalu dikalikan dengan 2 Nah dari sini kita teruskan jadinya total tambah y 2-nya boleh kita coret X1 * itu adalah kyj dan kita lihat bahwa ternyata ekspresi pada variabel baru ini ternyata nilainya akan sama dengan total Hai tambah edan nilainya adalah = AB juga jadi nilai total X dan Y pada iterasi pada akhir iterasi tetap memenuhi rutin varian kita Hai terakhir termination termination terjadi saat Kenya Fals Hai Regita adalah x sandrino jadi dia Fals maka berarti kalau Anya Fool itu adalah x-nya kurang dari tapi kita tahu bahwa esnya besar sama dengan nol adalah lebih kalian dia benar di akhir Nu ya jadinya x = 0 dan X Kresno ini berakibat X = jadi kita tahu bahwa aksinya nol di akhir Club karena Ayo kita punyai bahwa total Hai tambah nol kali G apapun lainnya itu = a * b dan kita dapatkan bahwa total di akhir Loop nilainya akan sama dengan akal ide yaitu postcondition yang kita inginkan Hai Bisa ini saya menunjukkan cara menulis bukti yang ada di slide sebelumnya secara lebih formal kita bisa lihat bahwa invariant itu memang terpenuhi di setiap iterasi berikut adalah visualisasinya yo yo ini kita hanya menggunakan looping varian untuk menganalisis atau menjelaskan kebenaran algoritma di video ini saya akan mencoba menjelaskan Bagaimana kita bisa menggunakan Lupin varian untuk membuat algoritma kita sendiri jadi Ih celana kita tahu pos kondisinya apa kita bisa merancang Lupin variannya kemudian kita bisa merancang algoritma iterative dari lebih parents itu pertama ingat bahwa kebenaran dari suatu interaksi atau lu masyarakan bahwa Lupin variannya saat keluar dari lu memberikan kita postcondition draw Lupin varian ini akan membimbing kita apa yang harus di jaga untuk benar hingga akhirnya kita mendapatkan pos kondisinya diinginkan yaitu teknik Hai yang digunakan Salah satunya adalah memperolehi terlebih dahulu dengan melemahkan P melemahkan packaging nya yg akan benar lebih banyak daripada I Luph ini Hai harus berhenti ketika [Musik] hal ini berakibat kayaknya benar dan ini akan kita gunakan untuk merancang agar truknya kalau cara untuk melemahkan P demi mendapatkan ini adalah dengan mengganti konstan dengan variabel kyb kalau kita tahu Koston SMP kita bisa melemahkannya dengan mengganti kemunculan konstan pada pos kondisi itu dengan sebuah variabel sebutlah J dengan demikian saat jahenya itu nanti sama dengan konstannya kita akan mendapatkan p = i artinya tutupin variannya bernilai postcondition dalam kasus ini get Loop yang sesuai adalah J tidak = n jadi kita melakukan lux lamaze tidak = n i Indonesia hai ketika klubnya berarti guard nya akan bernilai false jadi kita dapatkan I con jungsi atau bersama dengan j = n akan memberikan kita sekarang saya akan coba berikan contoh perancangan algoritma menggunakan bantuan booking varian misalnya kita punya sebuah Arai Aa yang panjangnya n dan kita ingin menjumlahkan elemen-elemen dari Aa perhatikan bahwa begitu aa diberikan raia diberikan maka N bukan lagi variabel tapi merupakan sebuah konstanta postcondition itu tujuan dari agar Makita tentu adalah majemukan elemen-elemennya dan mungkin kita bisa bayangkan hal ini bisa direalisasikan dengan menyimpan hasil jumlah tersebut pada sebuah variabel sebut aja namanya Rizal ya diposkan disita adalah Rizal = a 21 tambah dua sampai tambah n selanjutnya kita ingin mencari lebih varian lebih varian bisa dicari dengan melemahkan postcondition b satu caranya adalah mengganti kemunculan konstanta yang ada di pn8 satu variabel j&j ini nanti akan menjadi variabel blog kita jadi ide akan berbentuk Rizal sama dengan salah satu tambah H2 sampai tambah AJ kita fokus pada JNE yang berupa integer saja Gar dari Lupita adalah J tidak = n tujuannya adalah agar jika kita keluar dari lu berarti negatif dari grupnya itu benar artinya j = n bersama-sama dengan lebih varian IJ j&j semena-mena akan memberikan kita pernyataan in jadiin benar ia dibaca Rizal sama dengan aa1 tambah H2 sampai tambah Aa Rizal = A1 sampai tambahan itu sendiri merupakan postcondition jadi lebih varian kita bersama-sama dengan negatif dari God akan langsung memberikan kita pos condition yaitu hasil yang kita inginkan sekarang perhatikan login varian kita Dia memiliki variabel J dan juga kita menampung Rhizopus = A1 tambah dua sampai tambah Haji bagaimana bentuknya kita bisa menyiapkan satu variabel Rizal = 0 dan J = hai lalu guard kita kita ikuti panduan tadi yaitu J tidak = n Ayo kita bisa meng-update jne-nya satu persatu dari 1 2 3 dan seterusnya dengan melakukan implement penambahan dalam atraksinya jadi Jazz ama dengan j1dan Setiap kali kita menambah jne-nya kita juga menambahkan Rizal sama dengan Rizal tambah aaaj Hai kawan cerewet sebagai latihan coba teman-teman rancang sebuah algoritma untuk masalah yang sama tapi dengan Lupin varian IG jadi dia tetap punya variabel Uje Dan kita punya variabel Rizal = a AJ tambah haji plus satu sampai tambahan perhatikan bahwa dhoifa Reni diperoleh dengan mengganti konstanta satu dengan J cara berikutnya untuk mendapatkan lebih varian dengan melemahkan P adalah dengan menghapus sebuah konjat Hai goncang itu apa konjan adalah anak kalimat dari sebuah kalimat besar atau majemuk yang dihubungkan dengan operasi konjungsi jadi misalnya saya punya kalimat A dan B dan C maka ABC tuh disebut konjac sponge Hai jika suatu postcondition mengandung beberapa konjungsi maka kita bisa melemahkannya dengan menghapus satu atau beberapa gonjang-ganjing Hai predikat yang dihasilkan atau kalimat yang dihasilkan akan benar di lebih dari di lebih banyak daripada P itu sendiri Hai jadi dia bisa menjadi kandidat yang cocok untuk Lupin varian I Luph dari God dari hidupnya dalam kasus ini akan menjadi negosiasi dari The Conjuring yang kita hapus ya Jadi kalau seandainya kita menghapus gonjang C maka ini akan jadi ada deh nah logatnya itu adalah negasi dari cinta Kenapa supaya nanti Ida negatif ini itu kan sama dengan apa a&b dan negatif dari negasi Hai dan kita dapatkan a dan b dan c dan ini sendiri adalah pos kondisi itu sendiri Hai berikut adalah contohnya itu justeru air dari sebuah bilangan asli n adalah bilangan bulat terbesar yang kuadratnya tidak lebih dari hand Misalnya ini justeru dari 20 itu adalah empat karena 4 kuadrat itu masih kurang dari sama dengan 20 tapi lima kuadrat sudah besar 20 di dalam bahasa yang lebih persis ya kita dapatkan er itu harus memenuhi x kuadrat kurang n&n kurang dari R21 kuadrat perhatikan bahwa ini adalah dua konjungsi dari dua pernyataan kalau kita hapus pernyataan yang kedua yaitu n kurang dari Rp10 the kita akan dapatkan konjungtiva Edward kurir suratnya Nah kita bisa ambil ini sebagai lebih varian dimana R adalah variabel webnya jadi er kita adalah er kuadrat kurang disemen Hai perhatikan bahwa ini benar ketika airnya no Hai jadi ini sorted dari duduknya bisa dengan mudah didapatkan kalau kita file-nya awalnya nomor my god dari duduknya adalah negatif dari konjungsi yang kita lihat perhatikan bahwa migrasi dari n kurang dari er plus satu kuadrat lawannya adalah tentu Rp10 adanya kurang dari sama dengan one3 kita dapatkan Kayaknya seperti ini Hai Nah kita bisa tinggal manfaatkan body dari duduknya dengan mengimplementasi er dengan bantuan lebih varian tadi kita secara otomatis dapat memperoleh algoritma berikut airnya kita ASEAN dengan nol ini langsung menjamin kebenaran cukup varian di awal selanjutnya selama er persatu kuadrat kurang sekarang energi negatifnya kita cukup tambahin er dengan air bersatu kita selesaikan Hai misalnya kita ingin menghitung faktorial dari sebuah bilangan asli n faktorial adalah satu kali dua sampai klien perhatikan algoritma berikut faktor l n jika N 1 kembalikan satu jika tidak kembalikan n Ali faktorial N1 Bagaimana cara membuktikan kebenaran dari algoritma ini saya nyatakan teorema sebagai berikut faktorial Halo berhenti mengembalikan satu kali dua sampai kalian Buktinya adalah sebagai berikut pertama kita periksa kasus dasar abc's kasus Dasar adalah kasus gimana tidak terjadi pemanggilan faktorial lagi Hai untuk SMAN 1 waktu 01 akan mengembalikan satu sesuai definisinya artinya ini benarkan karena satu faktor sendiri Memang Hai selanjutnya rekursif cake untuk rekursif Chase kita asumsikan setiap pemanggilan faktorial di dalam bodi dari fungsi kita itu mengembalikan hasil yang sama di sini pemanggilan faktorial di dalam boardingnya hanya terjadi pada faktorial N1 asumsikan ini mengembalikan output yang benar-benar Hai akut yang benar dari faktor ln1 adalah satu kali dua sampai kalian satu jadi asumsikan satu membalikkan satu kali dua kali maka fakturnya kita akan mengembalikan n dikalikan hasilnya tadi dari faktor jadi fungsi utama kita faktor enakan mengembalikan n kali satu kali dua sampai kalian 11 kali dua kali terbukti namun perhatikan bahwa kita tetap perlu menjelaskan Kenapa faktorial itu berhenti Nda Bagaimana cara menjelaskannya ini kita akan Coba buktikan kebenaran algoritma rekursif plastik yang digunakan untuk memanfaatkan bilangan eksponensial teks Comment di sini kita asumsikan X adalah bilangan real positif Hai dan n adalah bilangan cacah Hai jika enokitake American satu jika Nia bilangan genap kita kembalikan eksponensi at x kuadrat koma n berdua Dan jika ngene ganjil kita kembalikan x * experienced x kuadrat khomaeni 1/2 untuk pembuktiannya kita Tuliskan lu nyatanya yang kita butuhkan yaitu eksponensi Ed Nexcom Hai ini mengembalikan Hai x pangkat n i Hai terminated the Hai pembuktiannya adalah sebagai berikut yang pertama adalah besskey yaitu kasus dimana tidak ada pemanggilan X manusia ini terjadi saat terjadi saat Hai NY sama dengan perhatikan bahwa eksponensi at the ex0 itu akan mengembalikan Hai namun Ayo kita tahu Hai x pangkat nol itu adalah satu menjadi ini benar ya selanjutnya rekursif case Hai dengan ya untuk rekursif Guys kita asumsikan Hai setiap pemanggilan Aa eksponensi at&t Oh ya ah Hai di dalam the lounge e-body Loop Hai termini dan memberikan Hai hasil ini memang yang benar Hai maka ada dua kasus Hai jika n genap Hai maka kita mengembalikan eksponensi Ed the lounge hai Hai ini akan sama dengan Hai eksponensi Ed the lounge Hai x kuadrat koma 42 Namun kita akan mengasumsikan pemanggilan ini mengembalikan hasil yang benar jadi hasilnya adalah kwadran dipangkatkan mp2 dan kita tahu ini hasilnya adalah x pangkat n ketikan bahwa dari sini ke sini kita gunakan Hai revisinya ngomong i Hai selanjutnya jika enak ganjil Hai maka eksponensi Ed KYT X koma n akan mengembalikan X dikalikan dengan Hai eksponensi Ed Hai x kuadrat koma n 1/2 dari sini kita lihat bahwa dengan asumsi induksi atau sisir eksklusifnya expansion x kuadrat ns2 akan bernilai x kuadrat pangkat n 1/2 dari sini kita dapatkan hasilnya 2x kalikan dengan x pangkat N 1 dan hasilnya adalah x pangkat n Hai jadi pada setiap kasus skornya Zyrex comment akan memberikan x pangkat n ada juga yang namanya rekursif invariant nah jika kita tahu bunga rekursif dari sebuah permasalahan Kita juga bisa merancang algoritma rekursif nya kita akan melihat ini di beberapa minggu kedepan materi dari kuliah ini diadaptasi dari slide Bapak lem Jones Stefanus slide iki 30-180 100 desain dan analisis algoritma d