Meno:Matej
Priezvisko:Lučenič
Názov:Možnosti využitia ľudského postupu pri riešení ťažkých problémov v informatike
Vedúci:Dac. RNDr. Juraj Procházka CSc.
Rok:2009
Blok:INF
Kľúčové slová:problém obchodného cestujúceho, hamiltonovská kružnica, lineárne prehľadávanie, konvexný obal, metóda najlacnejšieho vkladania, lokálna optimalizácia
Abstrakt:Lučenič Matej: Možnosti využitia ľudského postupu pre návrh algoritmov na riešenie ťažkých problémov [ Diplomová práca ] – Komenského Univerzita, Bratislava, Fakulta Matematiky, Fyziky a Informatiky; Katedra Informatiky. – Školiteľ: doc. RNDr. Juraj Procházka, CSc. Bratislava : Komenského Univerzita 2009. 42 strán. Experimentálne zisťované parametre ľudského riešenia vizuálne zadaného problému obchodného cestujúceho ukazujú, že človek vie tento problém riešiť veľmi efektívne, pričom dosahuje pomerne kvalitné výsledky. Otázkou je, či je možné na základe pozorovania ľudského postupu navrhnúť algoritmus, ktorý by dokázal riešiť problém s podobným úspechom. Hlavnou výhodou človeka je globálny pohľad na vizuálne prezentovaný problém, ktorý počítač dokáže vyvážiť rýchlosťou svojej práce a vyššou schopnosťou rozlíšenia drobných rozdielov vo vzdialenostiach vrcholov. V tejto práci na základe výsledkov pozorovania ľudského postupu navrhujeme algoritmus pre riešenie problému obchodného cestujúceho v rovine a analyzujeme jeho vlastnosti v porovnaní s algoritmami podobného typu. Výsledkom je algoritmus lineárneho prehľadávania, ktorý pracuje v čase O(n4) a kvalita jeho riešení je porovnateľná a v niektorých prípadom lepšia, ako kvalita riešení porovnávaných algoritmov.

Súbory diplomovej práce:

Praca2.pdf