Rekurzija u nastavi informatike

diplomski rad

• Naslov (engleski): Recursion in computer science teaching
• Autor: Karmela Wrigley-Pimley-McKerr
• Mentor: Vedran Krčadinac (mentor)
• Član povjerenstva: Luka Grubišić (predsjednik povjerenstva)
• Član povjerenstva: Zvonimir Bujanović (član povjerenstva)
• Član povjerenstva: Mladen Vuković (član povjerenstva)
• Član povjerenstva: Vedran Krčadinac (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2023-05-04, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

U ovom diplomskom radu definirali smo rekurziju i dali primjere rekurzivnih algoritama u programskom jeziku Python. Fibonaccijeve brojeve i binomne koeficijente računali smo rekurzivno te smo usporedili učinkovitost rekurzivnog rješenja s iterativnim rješenjem mjereći vrijeme izvršavanja algoritama. Rekurzivne algoritme unaprijedili smo memoizacijom. Dalje smo generirali kombinatorne objekte: permutacije, kombinacije te sve podskupove danog skupa. Kornjačinom grafikom crtali smo fraktalne skupove: Kochovu krivulju, binarno stablo i trokut Sierpiński. Opisali smo dva rekurzivna algoritma za sortiranje: mergesort i quicksort te pokazali njihovo djelovanje na primjeru. Testirali smo njihovu brzinu u usporedbi s ugrađenom funkcijom u programskom jeziku Python te analizirali njihovu vremensku složenost. U poglavlju rekurzija u školi promatrali smo kako udžbenici za osnovnu i srednju školu obrađuju rekurziju. Na kraju smo dali osvrt na udžbenike i primjer kako obraditi rekurziju u nastavi.

Sažetak (engleski)

In this thesis, we defined recursion and gave examples of recursive algorithms in the Python programming language. Fibonacci numbers and binomial coefficients were calculated recursively and we compared the efficiency of the recursive solution with the iterative solution by measuring the execution time of the algorithms. We improved the recursive algorithms by memoisation. We generated combinatorial objects: permutations, combinations and all subsets of the given set. With the turtle graphics, we drew fractal sets: the Koch curve, the binary tree and the Sierpinski triangle. We described two recursive algorithms for sorting: mergesort and quicksort and showed their operation on an example. We tested their speed in comparison with a built-in function in the Python programming language and analysed their time complexity. In the chapter on recursion at school, we observed how text- books for primary and secondary schools deal with recursion. At the end, we gave an overview of textbooks and an example of how to teach recursion in class.

• Ključne riječi: rekurzivni algoritami; programski jezik Python; fraktalni skupovi; Kochova krivulja; binarno stablo; trokut Sierpiński
• Ključne riječi (engleski): recursive algorithms; Python programming language; fractal sets; Koch curve; e binary tree; Sierpinski triangle
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:159135
• Studijski program: Naziv: Matematika i informatika; smjerovi: Nastavnički; Smjer: Nastavnički; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: sveučilišni magistar edukacije matematike i informatike (univ. mag. educ. math. et inf.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2024-02-09 15:00:41