Kategori: StrukDa

Info tentang StrukDa (Struktur Data). Buku referensi adalah “Struktur Data Menggunakan Turbo Pascal 6.0” Insap Santosa, Penerbit ANDI OFFSET Yogyakarta. Kini RASP mengajar bersama MK (giliran di awal semester).

Struktur Data 10

Proses rekursi di program p_318b

Mempunyai kondisi pengakhiran rekursi yaitu jika nilai n sudah lebih kecil atau sama dengan nol. Setiap kali fungsi memanggil dirinya sendiri, nilai dari n dikurangi dengan nilai satu, sehingga nilai n akhirnya akan menjadi nol dan proses rekursi akan diakhiri, sehingga fungsi ini akan memanggil dirinya sendiri sebanyak n kali.
Program di p_319 merupakan program menghitung n! Yang akan dikerjakan secara rekursi.
Program di p_322 merupakan
Program untuk mengurutkan data dengan metode quick sort yang dilakukan secara rekursi. Metode ini menggunakan teknik memecah data menjadi partisi-partisi sehingga metode ini disebut dengan nama metode pengurutan pertukaran partisi (partition exchange sort).
Proses pengurutan dimulai dengan memilih sebuah elemen secara sembarang. Di program, elemen yang dipilih adalah elemen terbawah.

	


	





	

		
		
Struktur Data 9
	


	
	
	

		
Kamis 22 Maret 2012


Buku referensi: Jogiyanto Hartono, MBA, PhD, 1993. Konsep Dasar Pemrograman Bahasa C, Penerbit Andi, Yogyakarta.
Materi: Bab 9 Larik, Bab 10 Pointer, Bab 11 Fungsi, Bab 12 Tipe Data Tingkat Lanjut.
Bab 11, bagian 11.11. Rekursi, hlm 318. Rekursi (recursion) adalah suatu proses dari fungsi yang memanggil dirinya sendiri secara berulang-ulang.


Karena proses dilakukan


Berulang-ulang, harus ada suatu kondisi yang mengakhiri prosesnya. Jika tidak, maka proses tidak akan pernah berhenti sampai memori yang digunakan tidak dapat menampung lagi.
Program contoh di p_318 merupakan program rekursi yang tidak akan berhenti karena tidak mempunyai kondisi yang menghentikan prosesnya. Proses rekursi ini ditunjukkan oleh statemen terus_tidak_berhenti() yaitu proses yang memanggil fungsi dirinya sendiri.



	


	





	

		
		
Struktur Data 8
	


	
	
	

		
Hubungan rekurens sbb


•FIBO(N) = FIBO (N-1) + FIBO (N-2)


•Karena FIBO(N) ditentukan oleh 2 nilai yang berbeda dengan argumen yang nilainya lebih kecil, untuk mencari bilangan Fibonnaci diperlukan 2 nilai awal yaitu


•FIBO(1) = 1


•FIBO(2) = 2


PR




•Buat program untuk mencari bilangan Fibonnaci. Boleh memakai bahasa C++, Pascal, Basic, dll.


•Dikumpulkan kamis depan dalam bentuk makalah di mana ada pengantar, source code, hasil running program, pembahasan, simpulan.


•Source sudah dimodifikasi di mana ada identitas dan keterangan program.



	


	





	

		
		
Struktur Data 7
	


	
	
	

		
Notasi pemrograman


•FAKTORIAL(0) = 1  1)


•FAKTORIAL(N) = N x FAKTORIAL(N-1)  2)


•


•Persamaan 2) di atas merupakan contoh hubungan rekurens (recurrence relation), berarti bahwa nilai suatu fungsi dengan argumen tertentu bisa dihitung dari fungsi yang sama dengan argumen yang lebih kecil.


Persamaan 1)




•Tidak bersifat rekursif, disebut nilai awal. Setiap fungsi rekursi paling sedikit mempunyai satu nilai awal. Jika tidak, fungsi tersebut tidak bisa dihitung secara eksplisit.




Bilangan Fibonnaci




•Bisa didefinisikan berdasarkan deret integer tak berhingga sebagai berikut:


•1, 1, 2, 3, 5, 8, 12, 13, 21, 34, 55, 89, …


•Bilangan ke-N, di mana (N > 2) dalam deret bisa dicari dari dua bilangan sebelumnya yang terdekat dengan bilangan ke-N yaitu bilangan ke-(N-1) dan bilangan ke-(N-2).


•Jika FIBO (N) menunjukkan bilangan Fibonnaci ke-N maka FIBO (N) bisa dihitung berdasarkan



	


	





	

		
		
Struktur Data 6
	


	
	
	

		
Hati-hati


•Dalam prosedur atau fungsi, pemanggilan ke diri sendiri bisa berarti proses berulang yang tidak bisa diketahui kapan akan berakhir.


•Dalam pemakaian sehari-hari, rekursi merupakan teknik pemrograman pada pekerjaan dengan mengekspresikannya ke dalam suku-suku dari program lain dengan menambah langkah-langkah sejenis.


Contoh




•Menghitung nilai faktorial dari bilangan bulat positif dan mencari deret Fibonnaci dari suatu bilangan bulat.


•Faktorial, nilainya secara rekursif dapat ditulis sebagai


•0! = 1,


•N! = N x (N – 1)! untuk N > 0



	


	





	

		
		
Struktur Data 5
	


	
	
	

		
•Dosen: RASP, MK


•Jadwal: Kamis 13.30 – 15.00 wib.


•Penilaian: PR, KLP, UTS.


•Materi: Berbahasa C++ dan Pascal terdiri atas 1) Rekursi, 2) Tumpukan, 3) Tipe data pointer, 4) Senarai berantai, 5) Antrian, 6) Senarai berantai banyak, 7) Pohon, 8) Pengurutan, 9) Pencarian, 10) Program terapan, 11) Graph, 12) Pengelolaan pengingat.




•Program = struktur data + algoritma


REKURSI




•Pengertian: rekursi berarti suatu proses yang bisa memanggil dirinya sendiri.


•Dalam rekursi sebenarnya terkandung pengertian prosedur atau fungsi.


•Perbedaannya adalah rekursi bisa memanggil diri sendiri, prosedur atau fungsi harus dipanggil lewat pemanggil prosedur atau fungsi.





	


	





	

		
		
Struktur Data 4
	


	
	
	

		
Teaching data structures
• adjacency matrix, adjacency list
• Degree of all vertices, connected component, checking connectivity
• Breadth-first search
• Shortest path
• Topological sort
• All shortest paths from a vertex
• Spanning trees: Kruskal, Prim
• Cycle detection: union-find
• Numerical algorithms: GCD, exponentiation, integer multiplication
• Strings
• Text search (brute force, Rabin-Karp, Knuth-Morris-Pratt, others)
• Edit distance
• Pattern matching by regular expressions, advanced regular expressions
• Categories of algorithms: divide and conquer, greedy, dynamic programming,
search
• Tractability: constant, logarithmic, linear, quadratic
• Decision problems: P, NP


Sumber: Finkel, Raphael, 2009. How to Teach Data Structures.

	


	





	

		
		
Struktur Data 3
	


	
	
	

		
Exercise -lesson
• Form teams of no more than 6 students.
• Choose a data-structures topic.
• Discuss how to structure a lesson on that topic.


Subject matter

• Generally important ideas (“screwdrivers”) versus specialty topics
(“voltmeters”).
• Common themes that one finds throughout the study of data structures.
• pointers: cells in memory that refer to other cells
• recursion
• fencepost errors
• dummy value
• experimentation and invention
• What is a data structure? Howdoes it relate tomore general software
tools?
• How does one discuss efficiency of data structures?
• Linked lists (the first structure built with pointers)
• Queues, stacks, deques: built out of either linked lists or arrays
• Quick example of using an array for a queue
• Searching though numeric data: linked lists, unsorted array, sorted
array (binary search, interpolation search), binary tree
• Recursion theorem (without proof)
• Finding the jth largest element in a set (recursive partitioning)
• Sorting numeric data: insertion sort, selection sort, quicksort, bin
sort, radix sort
• short discussion: Never use bubble sort, although bumble sort
is far worse!
• Priority queues: heaps and heap sort
• Balanced binary trees: red-black trees, 2-3 trees, B treee
• Hashing, including the ”hash” data structure of Perl or PHP
• Quick example of hashing “we came we saw we conquered”
• Cryptographic hashing (digests)
• Quad trees, k-d trees
• Graphs


Sumber: Finkel, Raphael, 2009. How to Teach Data Structures.

	


	





	

		
		
Struktur Data 2
	


	
	
	

		
Lesson: Binary trees
• Participants name integers
• Leader adds them to a growing sorted binary tree
• At some point, the integers are probes, not inserts median?
• Enumeration of operations
• insert
• search
• delete (seems hard)
• modify a node (seems as hard as delete followed by insert)
• enumerate all nodes
• find the smallest element (seems easy)
• find the middle element (seems hard)
• What is the cost of searching for a target? O(log n).


Sumber: Finkel, Raphael, 2009. How to Teach Data Structures.