Analisa Algoritma

heru    Uncategorized     analisa algoritma

Semester ini, salah satu materi kuliah yang ditugaskan oleh jurusan kepada saya adalah analisa algoritma (2 SKS). Fokus matakuliah ini adalah pemecahan masalah dengan berbagai strategi algoritma, disamping juga melakukan perhitungan kompleksitas algoritmanya. Seperti biasa, materi secara lengkap dapat dilihat dan didownload di LMS UPN “Veteran” Yogyakarta. Pertemuan direncanakan selama 14 kali ditambah dengan UTS dan UAS. Berikut resume setiap pertemuan

1. Pendahuluan, sekedar mengingatkan mengenai sejarah dan istilah, mengingat kembali berbagai teknik pemrograman, Dijelaskan pula mengenai materi kuliah,RPS, referensi, serta pre test untuk melihat sejauh mana pengetahuan mengenai algoritma.
2. Konsep algoritma, berisi konsep dasar algoritma, tahapan algoritma, menegaskan kembali ciri algoritma yang baik, menjelaskan strategi algoritma, serta mengulang kembali notasi matematik yang penting bagi perkuliahan ini.
3. Running Time, membahas mengenai efisiensi algoritma, serta melakukan pengukuran running time pada berbagai algoritma yang sederhana.
4. Faktor analisa algoritma, membahas running time dan penggunaan memory, kompleksitas waktu serta best, worst dan average case
5. Notasi Asymptotic, membahas Big Oh, Big Omega, Big Teta beserta sifat dan hubungannya.
6. Algoritma Rekursif, membahas algoritma rekursif dengan studi kasus menara hanoi dan faktorial beserta perhitungan kompleksitasnya, menyelesaikan relasi rekurens linier dan koefisien konstan, serta menyelesaikan relasi rekurens dengan teorema master
7. Brute Force. Membahas algoritma brute force dengan studi kasus menghitung an,faktorial, perkalian matriks, mencari faktor, mencari elemen terbesar/terkecil, sequential search, bubble sort, polinom, serta membahas karakteristik algoritma brute force.
8. Exhaustive search, membahas dengan berbagai studi kasus TSP, 1/0 knapsack, serangan pada kriptografi, serta solusi alternatif algoritma exhaustive search
9. Divide And Conquer, membahas algoritma divide and conquer dengan studi kasus minmax dan sorting (merge sort), serta menghitung kompleksitas waktunya.
10. Divide And Conquer (lanjutan), membahas studi kasus perpangkatan a serta perkalian matriks dengan algoritma strassen, dan menghitung kompleksitas waktunya
11. Algoritma greedy, membahas algoritma greedy dengan studi kasus penukaran uang, scheduling dan knapsack problem, beserta kompleksitas waktunya
12. Algoritma backtrack, membahas algoritma backtrack dengan studi kasus knapsack 0/1, persoalan n-ratu dan labirin, beserta kompleksitas waktunya
13. Dynamic programming , membahas pemrograman dinamis dengan studi kasus lintasan terpendek, capital budgetting dan knapsack 0/1, beserta kompleksitas waktunya
14. 14. Dynamic programming membahas pemrograman dinamis dengan studi kasus TSP beserta kompleksitas waktunya.

Materi kuliah semester pendek

heru    IT     analisa algoritma, matematika diskret, otomata dan pengantar kompilasi

Materi kuliah semester pendek untuk matakuliah matematika diskret, analisa algoritma dan otomata dan pengantar kompilasi sudah bisa didownload melalui http://ielisa.upnyk.ac.id , berada dalam format ppt dan tersusun untuk 13 kali perkuliahan, yaitu. Berikut deskripsi masing masing materi

read more

Divide and Conquer

heru    IT     analisa algoritma

Salah satu strategi penyelesaian masalah dalam bidang komputasi adalah menggunakan divide dan conquer. Caranya adalah memecah problem menjadi beberapa sub problem. Masing masing sub problem tersebut dipecahkan dan selanjutnya solusinya digabungkan dengan suatu mekanisme tertentu. Apabila sub problem tersebut masih tidak bisa dipecahkan secara langsung, maka sub problem tersebut dipecah kembali menjadi beberapa sub problem secara divide an conquer. Dalam aplikasinya, hal tersebut bisa diselesaikan secara rekursif.

read more