Na videz nemogoči funkcionali : delo diplomskega seminarja

Makovecki, Tine (author), Bauer, Andrej (mentor)

V delu obravnavamo računalniško implementacijo funkcionala izbire na Cantorjevi množici. Utemeljimo, da lahko predikate na Cantorjevi množici predstavimo z dvojiškimi drevesi in da nam ta predstavitev pomaga pri implementaciji funkcionala izbire. Dokažemo, da so funkcionali, ki jih obravnavamo, izračunljivi in da so drevesa, ki jih v postopku uporabimo, končna. Funkcional izbire implementiramo v programskem jeziku OCaml na različne načine, ki jih med seboj tudi primerjamo.

• Language: Slovenian
• Keywords: funkcional izbire, Cantorjeva množica, funkcijsko programiranje, funkcionali, drevesa, izračunljivost
• Work type: Final seminar paper
• Typology: 2.11 - Undergraduate Thesis
• Organization: FMF - Faculty of Mathematics and Physics
• Year: 2018
• PID: 20.500.12556/RUL-103726
• UDC: 004
• COBISS.SI-ID: 18478425
• Publication date in RUL: 23.09.2018

Secondary language

• Language: English
• Title: Seemingly impossible functionals

Abstract

In this work we discuss the implementation of the selection functional on the Cantor set. We show that continous predicates on the Cantor set can be represented with binary trees and that this representation helps implement the selection functional. It is proven that the functional we discuss is computable and the trees we use are finite. We implement the selection functional in the programming language OCaml in several ways, which we later compare.

• Keywords: selection functional, Cantor set, functional programming, functionals, trees, computability