Konputagarritasunerako oinarrizko teknikak

Abstract

Konputagarritasunaren Teoriak sistema informatikoek algoritmoen diseinuaren bitartez problemak ebaztean dituzten muga logikoak ezartzea du helburu. Txosten honetan teoria horren alderdi sinpleena aztertzen da. Konputagarritasunaren eta konputaezintasunaren definizioak ematen dira, eta problemak sailkatzen dira: erabakigarriak, sasierabakigarriak, erabakiezinak. Sailkapen hori gauzatzeko Konputagarritasunaren Teorian erabiltzen diren oinarriak eta frogapen teknikak azaltzen dira. Funtzio unibertsalaren definizioa ematen da eta kasu zailagoetarako prozesu tartekatzearen teknika azaltzen da. Informatikan berebiziko garrantzia duen geratze-problemaren definizioa ematen da eta bere erabakiezintasuna frogatzeko diagonalizazioaren teknika azaltzen da. Teknika hau multzo edo propietate bat erabakiezina dela frogatzeko erabiltzen den lehen tresnetakoa da, eta txosten honetan arreta guztia jarri da bere pausoak eta aldaerak zehazki azaltzeko. Azkenik problema erabakigarri eta sasierabakigarrien karakterizazioa eta propietateak ematen dira. UPV/EHUko Informatika Fakultatean ematen den Ingeniaritza Informatikoko Graduaren Ikasketa Planaren "Konputazioaren Eredu Abstraktuak" irakasgaiaren ikasleentzat irakaskuntza laguntza moduan idatzia izan den arren, egileen asmoa edo nahia, emaitza eta tekniken deskribapen ulergarria ematea da.