Combinatorial Problem

Combinatorial Problem

NAMA : BERLIANA

NPM    : 20312133

KELAS : IF 20 E 

Combinatorial problems adalah jenis permasalahan yang berhubungan dengan objek-objek dengan jumlah yang terbatas. "Combinatorial" mengacu pada penyusunan item-item. Combinatorial problems, merupakan permasalahan yang paling sulit diselesaikan baik secara teori maupun dalam prakteknya. Salah satu contoh permasalahan kombinatorial yang cukup terkenal adalah Traveling Salesman Problem atau disingkat TSP dan Knapsack Problem.

jadi dapat disimpulkan, Combinatorial problem merupakan suatu permasalahan matematis untuk menyusun, mengelompokkan, mengurutkan, atau memilih sejumlah objek diskrit tertentu. Dan sampai saat ini, combinatorial problem masih menjadi salah satu masalah yang paling sulit dalam komputasi baik itu dari teori maupun prakteknya. Maka dari itu Combinatorial menjadi salah satu bidang yang sering diteliti karena dengan semakin berkembangnya ilmu pengetahuan diharapkan akan ditemukan metode-metode maupun pendekatan-pendekatan baru yang bisa menjadi sebuah cara penyelesaian terbaik untuk permasalahan ini.

Kesulitan dari combinatorial problem antara lain :

1. Sejumlah objek combinatoric tertentu berkembang seiring dengan meningkatnya ukuran masalah.
2. Tidak diketahui algoritma pasti yang dapat digunakan untuk menyelesaikan permasalahan combinatorial problem

Tipe Problem Combinatorial Problem :

• Masalah : Menemukan suatu objek combinatoric seperti permutasi, kombinasi atau subset yang memenuhi batasan tertentu dan memiliki properti yang diinginkan.
• Problem yang sulit :
• Sejumlah objek combinatorikctertentu tumbuh dengan cepat seiring  peningkatan ukuran masalah.
• Tidak diketahui algoritma eksak untuk menyelesaikan masalah tersebut.

Permasalahan Combinatorial problems

Permasalahan Combinatorial problems ${\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\sigma </span></span>}}_{\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">1 </span></span>}}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">, </span></span><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\dots </span></span><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">, </span></span>{\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\sigma </span></span>}}_{\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">P </span></span>}}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\in </span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">S </span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">( </span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">n </span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">) </span></span>$dari jenis siklus yang diberikan ${\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\mu </span></span>}}^{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">( </span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">1 </span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">) </span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">, </span></span><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\dots </span></span><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">, </span></span>{\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\mu </span></span>}}^{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">( </span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">P </span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">) </span></span>}$seperti yang

[6]${\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"> \sigma </span></span>}}_{\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">1 </span></span>}}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\cdots </span></span>{\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\sigma </span></span>}}_{\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">P </span></span>}}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">= </span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">1\; .</span></span>}$

 

Solusi :

Sebuah interpretasi geometris dari masalah ini adalah untuk menghitung sampul bola${\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"> S </span></span>}}^{\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">2 </span></span>}}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">= </span></span>\mathbb{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">C </span></span>}{\mathbb{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">P </span></span>}}^{\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">1 </span></span>}}$bercabang di atas p poin yang diberikan dengan monodromy${\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"> \mu </span></span>}}^{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">( </span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">1 </span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">) </span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">, </span></span><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\dots </span></span><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">, </span></span>{\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\mu </span></span>}}^{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">( </span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">P </span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">) </span></span>}$. Teori karakter dasar dari S ( n ) memberi ( Jones 1998 )

[7]$<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"> \# </span></span><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\{ </span></span>{\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\sigma </span></span>}}_{\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">Saya </span></span>}}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\in </span></span>{\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">C </span></span>}}_{{\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\mu </span></span>}}^{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">( </span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">Saya </span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">) </span></span>}}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">, </span></span><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\Pi </span></span>{\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\sigma </span></span>}}_{\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">Saya </span></span>}}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">= </span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">1 </span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\} </span></span><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">= </span></span>{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">kan </span></span><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\Pi </span></span>{\mathit{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">F </span></span>}}_{{\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\mu </span></span>}}^{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">( </span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">Saya </span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">) </span></span>}}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">kan </span></span>}_{\text{<span style="vertical-align: inherit;"><span style="vertical-align: inherit;">Planch</span></span>}}$

di mana C _μ μ danadalah kelas konjugsi dengan tipe siklus

$$F μ ( λ ) = | C μ | χ μ λ redup λ

$$

Kelebihan

kombinatorik dapat digunakan untuk membilang, membuat perkiraan, menggeneralisasi, dan berpikir sistematis. Kombinatorik dapat diterapkan dalam 9 banyak bidang lainnya seperti programming, fisika, dan teknik serta bidang ilmu lainnya. Selain itu kombinatorik memainkan peranan penting dalam ilmi-ilmu hitung.

 

Kekurangan

 permasalahan kombinatorik: “....bahwa kebanyakan siswa mengalami kesulitan persoalan kombinatorik yang diberikan. Kesulitan memahami masalah berdampak pada kesulitan siswa merancang model matematika dari masalah itu. Kesulitan ini berlanjut terus sampai pada kesalahan mereka menentukan formula menyelesaikan masalah dan tentunya juga kesalahan pada jawaban persoalan yang diberikan.”

Alamat web Program studi, Fakultas, Universitas : http://ti.ftik.teknokrat.ac.id, http://ftik.teknokrat.ac.id, www.teknokrat.ac.id