Algoritma Greedy - Berpikir Komputasional | Informatika XI
Summary
TLDRThis educational video script introduces the concept of '3D' algorithms in computer science, which stands for 'Greedy' strategies used for optimization problems. It illustrates the application of the Greedy algorithm through two examples: maximizing the number of fish Budi can carry and ensuring Cici completes the most homework within a time limit. The script also covers a practical scenario of currency exchange, aiming to minimize the number of banknotes used to make a transaction. The lesson concludes with reflective questions to deepen understanding and encourages students to apply the Greedy algorithm to real-life optimization problems.
Takeaways
- đ The term '3D' in computational context stands for 'Greedy', a strategy for problem-solving that is useful in designing algorithms for computational problems.
- đ '3D' technique is a common approach used to solve optimization problems, where the goal is to calculate the best possible outcome from a given process.
- đ An example of applying the 3D algorithm is illustrated by a scenario where a character named Budi needs to maximize the number of fish he can carry in a limited number of bags.
- đą The script explains the importance of sorting data in ascending or descending order to apply the 3D algorithm effectively, as seen in the fish carrying example.
- đ The script introduces a problem-solving scenario where a character named Cici has to prioritize homework assignments based on the time required to complete them within a limited timeframe.
- đ Another example provided is about optimizing the number of animal shows Dina can watch in a day at a zoo, given that she can only watch one show at a time.
- đ” The script discusses a practical everyday problem of currency exchange, where the challenge is to use the least number of banknotes to make up a certain amount of money.
- 𧩠The script suggests that the 3D algorithm can be applied to various everyday optimization problems, such as choosing the best combination of banknotes to minimize the total number of notes used.
- đ€ The script encourages critical thinking by asking reflective questions about the applicability of the 3D algorithm to different optimization problems and whether it always yields the most optimal solution.
- đ The script concludes with a call to action for students to practice the discussed concepts and reflect on the most effective learnings from the exercise.
Q & A
What does the term '3D' stand for in the context of computational problem-solving?
-In the context of computational problem-solving, '3D' stands for 'Greedy', which is a strategy for solving problems that can be useful in designing an algorithm or solution for a computational problem.
What is the meaning of 'optimization problem' in the script?
-An 'optimization problem' refers to a problem where one seeks to calculate the best result from a certain process, which can mean the smallest or largest value depending on the nature of the problem.
How does the 3D algorithm apply to the problem of Budi carrying fish in plastic bags?
-The 3D algorithm applies by sorting the bags from the one with the most fish to the one with the least, and then selecting the bags with the most fish first until the car's capacity is reached, to carry the maximum number of fish possible.
What is the total number of fish Budi can carry if he takes the first four bags as per the 3D algorithm?
-If Budi takes the first four bags sorted by the 3D algorithm, the total number of fish he can carry is 25.
How does the 3D algorithm help in solving the problem of carrying at least 15 fish in the second example?
-The 3D algorithm helps by selecting the bags with the most fish first, ensuring that the minimum number of bags needed to carry at least 15 fish is chosen.
What is the minimum number of bags Budi needs to carry to have at least 15 fish in the second example?
-Budi needs to carry 3 bags to have at least 15 fish in the second example.
What is the importance of sorting data in the context of the 3D algorithm?
-Sorting data is important in the context of the 3D algorithm because it allows for a series of 3D steps to be taken on the sorted data, which is a common pattern used in solving optimization problems.
What is the task Cici has to prioritize in the homework assignment scenario?
-Cici has to prioritize which homework assignments (PR) to complete first, considering she only has 8 hours before they are due, and she wants to maximize the total value of the completed assignments.
How does the 3D algorithm apply to Dina's problem of watching as many animal shows as possible in one day?
-The 3D algorithm can be applied by selecting the shows that start first and have the longest duration, ensuring that Dina can watch the maximum number of shows within the day.
What is the main challenge in the currency exchange problem presented in the script?
-The main challenge in the currency exchange problem is to determine how to use the available denominations of currency to produce a specific amount of money with the minimum number of bills.
Can the 3D algorithm always find the most optimal solution for currency exchange problems?
-The 3D algorithm may not always find the most optimal solution for currency exchange problems, as it depends on the available denominations and the specific amount to be exchanged.
What is an example of an optimization problem in everyday life that is not mentioned in the script?
-An example of an optimization problem in everyday life that is not mentioned in the script could be planning a route for a delivery truck to minimize travel distance while maximizing the number of deliveries.
Outlines
đ Greedy Algorithm in Computational Problem Solving
This paragraph introduces the concept of the Greedy algorithm in the context of computer science, specifically within the field of computational thinking and algorithm design. It contrasts the negative connotations of 'greedy' in everyday language with its technical meaning as a problem-solving strategy. The Greedy algorithm is used to design solutions for optimization problems, aiming to calculate the best possible outcome from a given process. The example of Budi choosing the most fish from a set of bags with varying numbers of fish is used to illustrate how the Greedy algorithm can be applied. The strategy involves sorting the bags by the number of fish they contain and then selecting the bags with the most fish first until a certain limit is reached. This approach is shown to be effective for both maximizing the total number of fish and meeting a minimum requirement.
đ Applying the Greedy Algorithm to Homework Prioritization
The second paragraph presents a scenario where the Greedy algorithm can be used to solve a real-life problem. Cici, a student, has to complete 10 pieces of homework (PR) with varying estimated completion times but only has 8 hours available. The paragraph outlines the time required for each PR and asks how Cici should prioritize her tasks to maximize the total value of completed homework within the time constraint. The Greedy algorithm is suggested as a method to solve this problem by sorting the PRs based on their estimated completion times and selecting the ones that can be completed within the given time frame.
đȘ Maximizing Zoo Attractions with the Greedy Strategy
This paragraph discusses another application of the Greedy algorithm, this time in the context of planning a visit to a zoo with multiple scheduled animal shows. Dina wants to watch as many shows as possible within a day, but each show is at a specific time, and she can only attend one at a time. The paragraph lists the various shows and their timings, posing the question of how Dina can maximize the number of shows she watches. The Greedy algorithm is hinted at as a potential strategy for solving this problem, possibly by selecting shows that are closest together in time or that have the most appealing content.
đ” Optimal Currency Exchange Using the Greedy Approach
The final paragraph explores the application of the Greedy algorithm in currency exchange. It describes a scenario where one needs to make change for a specific amount using the least number of banknotes. The Indonesian Rupiah is used as an example, with various denominations available. The paragraph presents different combinations of banknotes that could be used to make up a total of 38,000 Rupiah and asks how one would choose the denominations to minimize the total number of banknotes. The Greedy algorithm is suggested as a method to solve this problem by always choosing the largest denomination that fits the remaining amount to be made up, thus reducing the total number of banknotes needed.
Mindmap
Keywords
đĄAlgorithm
đĄGreedy Strategy
đĄOptimization Problem
đĄComputational Thinking
đĄSorting
đĄLocal Optima
đĄBags of Fish
đĄCritical Thinking
đĄCurrency Exchange
đĄReflection
Highlights
Introduction to the concept of 3D algorithms in computational problem-solving.
Explanation of the term 'Greedy' in the context of computer science, contrasting its negative connotations in everyday language.
Description of the 3D technique as a problem-solving strategy used for optimization problems.
Definition of optimization problems as aiming to calculate the best result from a specific process.
Example of applying the 3D algorithm to maximize the number of fish Budi can carry in his car.
Illustration of sorting bags of fish from the most to the least to apply the 3D algorithm effectively.
Calculation of the maximum number of fish Budi can carry by choosing the right bags.
Second example where Budi needs to carry at least 15 fish, demonstrating the 3D algorithm's application for minimum requirements.
Emphasis on the importance of sorting data in problem-solving, particularly before applying the 3D algorithm.
Group activity involving Cici prioritizing homework assignments based on time constraints and equal value of each assignment.
Introduction of a visit to the zoo activity where Dina has to choose which animal shows to watch within a day.
Explanation of the currency exchange activity, focusing on the practical application of the 3D algorithm in daily life.
Challenge of finding the optimal way to make change using the least number of banknotes for a given amount.
Discussion on whether the 3D algorithm can always provide the most optimal solution in currency exchange problems.
Reflection questions posed to the audience to consider the application of the 3D algorithm in other optimization problems.
Conclusion and encouragement for the audience to apply the concepts learned in their studies and problem-solving.
Transcripts
[Musik]
Assalamualaikum warahmatullahi
wabarakatuh bertemu lagi di pelajaran
Informatika kelas 11 pada materi
strategi algoritmik dan pemrograman
yaitu Masih pada berpikir komputasional
pada bagian algoritma 3D
3D secara harfiah berarti Rakus atau
tamak meskipun dalam pengertian
sehari-hari kata rakus dan tamak
memiliki konotasi negatif namun dalam
konteks Informatika kita mengartikan
Greedy dalam konteks sebagai sebuah
strategi penyelesaian masalah yang dapat
berguna dalam merancang sebuah algoritma
atau solusi bagi sebuah permasalahan
komputasional Oleh karena itu diharapkan
tidak ada konotasi negatif pada kata
Greedy dalam konteks ini Teknik 3D
adalah salah satu teknik penyelesaian
masalah yang biasa digunakan untuk
menyelesaikan permasalahan optimasi
permasalahan optimasi berarti kita ingin
menghitung sebuah hasil yang terbaik
dari sebuah proses tertentu terbaik
ini dapat berarti nilai yang paling
kecil ataupun paling besar tergantung
dari jenis permasalahannya dalam
menyelesaikan permasalahan optimasi
algoritma 3D akan menerapkan prinsip
mengambil serangan langkah terbaik pada
setiap saat contoh
Budi ingin membawa beberapa ekor ikan
yang sudah tersimpan dalam
kantong-kantong plastik untuk diangkut
di dalam mobilnya terdapat 8 buah
kantong dengan yang berisi masing-masing
tiga lima dua
delapan empat
enam
enam dan tiga ekor ikan namun sayangnya
mobilnya hanya mampu membawa empat buah
kantong
kantong-kantong manakah yang harus
dibawa oleh Budi agar jumlah ikan yang
dibawanya sebanyak mungkin untuk dapat
membawa sebanyak mungkin ikan Budi harus
memilih kantong-kantong dengan sebanyak
mungkin ikan
Oleh karena itu
algoritma 3D dapat diterapkan di sini
dengan cara kita mengambil
kantong-kantong mulai dari yang berisi
ikan paling banyak terlebih dahulu
sampai didapatkan 4 buah kantong dengan
demikian kita harus mengurutkan
kantong-kantong terlebih dahulu
mulai dari yang paling banyak ikannya
sampai dengan yang paling sedikit
sehingga urutannya menjadi
866 54332
jika kita mengambil 4 buah kantong
pertama maka total banyaknya ikan yang
dapat dibawa adalah 8 ditambah 6 tambah
6 tambah 5 sama dengan 25 ekor ikan
tentunya tidak ada pilihan 4 kantong
yang akan menghasilkan total banyaknya
ikan lebih dari 25 ekor contoh yang
kedua
kali ini Budi harus membawa sedikitnya
15 ekor ikan tentunya jumlah kantong
terkecil yang harus dibawa oleh Budi
agar dapat membawa minimal 15 ekor ikan
sama seperti pada permasalahan
sebelumnya kita dapat menerapkan
algoritma 3D untuk menyelesaikan
permasalahan ini
dalam hal ini untuk memperkecil
banyaknya kantong yang harus dibawa maka
kita juga selalu memilih kantong dengan
jumlah ikan terbanyak terlebih dahulu
jika kita memilih kantong dengan jumlah
ikan 8 dan 6 maka kita sudah memiliki 14
ekor ikan
selanjutnya kita hanya perlu mengambil
satu kantong lagi yang mana saja agar
total jumlah ikan menjadi lebih dari 15
Oleh karena itu jawaban yang diinginkan
adalah 3 buah kantong jelas bahwa tidak
ada pilihan yang memungkinkan kita
mendapatkan 15 ekor ikan dengan dua atau
kurang kantong pada kedua contoh di atas
terdapat satu langkah yang penting yang
biasa diterapkan pada penyelesaian
masalah secara kritis
yaitu proses mengurutkan sebuah data
agar menjadi terurut mungkin dari kecil
ke besar atau sebaliknya agar kemudian
kita dapat melakukan serangkaian
pengambilan langkah secara 3D pada data
yang sudah terurut tersebut pola seperti
ini umum digunakan pada penyelesaian
permasalahan secara gerigi selanjutnya
Ayo berlatih aktivitas kelompok dengan
judul mengerjakan pekerjaan rumah atau
PR deskripsi tugasnya sebagai berikut
Cici menerima 10 buah pekerjaan rumah
yang harus ia kerjakan
setelah melihat isi dari masing-masing
PR biji memiliki perkiraan berapa lama
waktu yang diperlukan untuk mengerjakan
masing-masing PR tersebut
seperti terlihat pada tabel berikut
PR pelajaran a waktu mengerjakan satu
setengah jam PR mapel b 3 jam
PR mapel C 1 jam
PR mata pelajaran D waktu pengerjaannya
setengah jam
PR mapel e 4 jam PR mapel F 1 jam
pekerjaan rumah mapel D waktu
pengerjaannya dua setengah jam PR mapel
H 1 jam PR mapel I setengah jam PR mapel
J waktu pengerjaannya kira-kira 2 jam
sayangnya
ia tidak punya banyak waktu untuk
mengerjakan semua PR
Cici sudah menghitung bahwa ia hanya
punya waktu total 8 jam sebelum semua PR
tersebut harus dikumpulkan
Cici ingin menentukan PR mana yang harus
ia kerjakan terlebih dahulu dengan
pertimbangan bahwa setiap PR memiliki
nilai yang sama besarnya terhadap nilai
akhir Fiki bantulah Cici menentukan PR
yang mana saja yang harus ia kerjakan
dalam waktu maksimal 8 jam untuk
mendapatkan total nilai akhir yang
sebesar-besarnya aktivitas individu
berikutnya yaitu mengunjungi kebun
binatang
deskripsi tugasnya sebagai berikut
Dina sedang bertamasya mengunjungi kebun
binatang setiap hari kebun binatang
mengadakan beberapa pertunjukan atraksi
hewan yang dapat ditonton oleh para
pengunjung berikut adalah jadwal yang
telah ditetapkan oleh pengelola kebun
binatang
pertunjukan atau atraksi hewan orangutan
itu dimulai pukul 09.15 dan selesai
10.30
pukul 8 sampai 9.30
itu pertunjukan penguin
pukul 10 sampai 12 pertunjukan atau
atraksi hewan harimau
pukul
13.30 yaitu
pertunjukan beruang madu
pukul 11.00 sampai 12.30
pertunjukan burung pemangsa pukul 14.00
sampai 15 pertunjukan buaya
selanjutnya pukul 15.30 sampai 16.30
pertunjukan Panda waktu mulai pukul
16.00 dan waktu selesai pukul 17
pertunjukan atau atraksi hewan ular
piton
kemudian pukul 15.00 sampai 15.30 adalah
pertunjukan singa dan pukul 15.30 sampai
pukul 16 atraksi hewan anjing laut
tentunya dalam satu waktu tertentu Dina
hanya dapat menonton satu pertunjukan
atraksi hewan Dina ingin dapat melihat
sebanyak-banyaknya pertunjukan dalam
satu hari tersebut dan ia tidak dapat
memiliki preferensi dalam Melihat
pertunjukan hewan atau artinya semuanya
ia anggap sama menariknya Tentukan ada
berapa banyak maksimal pertunjukan yang
dapat ditonton oleh Dina aktivitas
berikutnya
judulnya adalah menukar uang
deskripsinya sebagai berikut dalam
kehidupan sehari-hari kita pasti sudah
punya
banyak terbiasa dalam perhitungan yang
melibatkan uang misalnya ketika Anda
membeli sebuah barang atau makanan
ataupun ingin membayar untuk sebuah jasa
tertentu seringkali menyiapkan sebuah
sejumlah uang tertentu
sesuai dengan harga barang atau jasa
tersebut
selanjutnya bagi penjual atau penyedia
jasa Apabila mereka menerima uang
pembayaran dengan jumlah total yang
lebih besar dari harga yang ditetapkan
Mereka pun juga harus menyiapkan uang
kembalian sesuai dengan jumlah kelebihan
pembayaran
di Indonesia mata uang Rupiah memiliki
beberapa pecahan uang mulai dari yang
terkecil Rp100
dan seterusnya sampai dengan 100.000
seandainya kita memiliki sejumlah
pecahan uang misalnya beberapa uang
seribuan 2000-an
rp5.000-an rp10.000-an dan 20 ribuan
Jika kita ingin mendapatkan uang tepat
sejumlah
38.000 maka kita dapat memilih beberapa
cara
Cara yang pertama misalnya 3 lembar 10
ribuan ditambah satu lembar 5 ribuan
ditambah dua lembar ribuan ditambah 2
koin 500 dengan total 8 buah lembaran
uang koin yang kedua satu lembar 20
ribuan ditambah satu lembar 10 ribuan
ditambah 4 lembar 2000-an totalnya
menjadi 6 lembaran uang
yang selanjutnya bisa juga satu lembar
20 ribuan ditambah satu lembar 10 ribuan
ditambah satu lembar rp5.000-an ditambah
satu lembar 2000-an ditambah satu lembar
seribuan dengan total ada lima lembaran
uang
jelas bahwa jumlah total lembaran yang
dibutuhkan tergantung dari pemilihan
pecahan uang yang kita gunakan
nah permasalahan yang mungkin kita
tanyakan adalah bagaimana caranya
Memilih pecahan-pecahan uang yang akan
digunakan sedemikian rupa sehingga total
lembaran yang diperlukan untuk
menghasilkan suatu nilai uang tertentu
menjadi sekecil mungkin pada contoh di
atas dapat diperiksa bahwa untuk
menghasilkan nilai uang sebesar
38.000 dari pecahan-pecahan seribuan
2000-an 5 ribuan
10ribuan dan 20ribuan maka diperlukan
minimal 5 buah lembar uang Yaitu sesuai
dengan cara terakhir di atas
dapatkah kalian mencari strategi yang
umum untuk menyelesaikan permasalahan
serupa Jika jumlah uang yang dihasilkan
berbeda namun pecahan-pecahan uang yang
sama
kita bisa menganggap bahwa jumlah nilai
yang diinginkan selalu merupakan
kelipatan ribuan rupiah sehingga selalu
didapatkan dengan menggabungkan
pecahan-pesan di atas selanjutnya Ayo
renungkan setelah selesai melakukan
aktivitas di atas jawablah pertanyaan
berikut pada buku refleksi yang pertama
Apakah kalian dapat memberikan sebuah
contoh lain dari permasalahan optimasi
yang ada di kehidupan sehari-hari
yang kedua untuk contoh permasalahan
yang kalian pilih sebagai jawaban nomor
1 Menurut kalian apakah algoritma 3D
dapat diterapkan pada permasalahan
tersebut yang ketiga pada permasalahan
penukaran uang pada aktivitas soal
Apakah algoritma 3D selalu dapat
digunakan untuk mencari jawaban yang
paling optimal berikutnya pada
permasalahan penukaran uang di atas
Apakah algoritma 3D selalu dapat
digunakan untuk mencari jawaban yang
paling optimal
ambil sebuah contoh kasus dimana pecahan
yang tersedia hanya 1000
2000 dan 10.000 dan kita ingin menukar
nilai 15.000 berapakah jawaban yang
diberikan oleh algoritma TV pada kasus
seperti ini apakah ini adalah jawaban
yang optimal untuk kasus Pertanyaan
nomor 3 Menurut kalian strategi Seperti
apakah yang kira-kira lebih tepat untuk
digunakan
pertanyaan berikutnya pada Ayo Renungkan
pelajaran paling berkesan apa yang
kalian dapatkan dari latihan ini
demikian tadi materi berpikir
komputasional pada bagian algoritma BT
Terima kasih semoga bermanfaat Selamat
belajar dan tetap semangat
[Musik]
Voir Plus de Vidéos Connexes
Discrete Math - 3.1.4 Optimization Algorithms
Pemrograman Dinamis - Berpikir Komputasional | Informatika XI
3. Greedy Method - Introduction
The Fundamental Counting Principle
3 Types of Algorithms Every Programmer Needs to Know
L-1.1: Introduction to Algorithm & Syllabus Discussion for GATE/NET & Placements Preparation | DAA
5.0 / 5 (0 votes)