Задача комівояжера в освіті інженерів-програмістів

Yevgeny Gayev, Vadim Kalmikov

Анотація


Мета: Славетну задачу комівояжера (ЗК) пропонується зробити звичайною вправою для студентів інженерних спеціальностей за умов, що вони оволодівають комп’ютерними науками в середовищі легкого програмування, як MATLAB. Методи: легке програмування в MATLAB дозволяє такий сучасний педагогічний підхід, як “навчання на власних відкриттях”. Результати: MATLAB-програма для ЗК, орієнтована на карту України, яка дозволяє графічно ілюструвати процес пошуку оптимального шляху між містами з опцією прискорення або гальмування демонстрації. Очікуємо, що програма буде корисною для вивчення ЗК як однієї з фундаментальних логістичних задач, а також як захоплююча вправа з програмування. Запропоновано, крім того, кілька підпрограм, що належать до ключових алгоритмів курсу програмування. Таке поєднання відповідає сучасному педагогічноиу методу “вчитися шляхом відкриттів”. Обговорення: Ми роз’яснюємо, як створити візуальну програму для дискретної оптимізації, пропонуємо потрібні підпрограми, включаючи доволі сучасний графічний інтерфейс користувача, пропонуємо її використання для демонстрації катастрофічного росту часу, потрібного для знаходження розв’язку. Висновки: Легке програмування, реалізоване в MATLAB, перетворює складні програмні задачі у привабливі, зосереджує студентів на точній постановці задачі, потрібних законах та алгоритмах, реалізуючи таким чином педагогічний підхід “навчання шляхом відкриттів”.


Ключові слова


ЗК (задача комівояжера); комбінаторика; логістика; навчання програмуванню; оптимізація; навчання шляхом відкриттів; програмування

Посилання


Azarskov V.M., Gayev Ye.A. (2014) Suchasne programuvannya [Modern programming, p. 1. Кyiv: NAU. – 256 p.]. (in Ukrainian)

Gayev E.O., Azarskov V.М. (2016) Suchasne programuvannya [Modern Programming, p. 2. Кyiv: NAU. – 197 p.]. (in Ukrainian)

Azarskov V.М., Gayev E.A. (2015) Programmirovanie intensifitsiruet ovladenie nauk studentami [Programming intensifies mastering sciences by students]. Materiali XIY Mizhnarodnoji Konferencii [Materials ХІY International Conference «Industrial hydraulics and pneumatics»], Sumy, pp. 28 -29. (in Russian)

Gayev E.A., Martych. M., Tarak G. (2015) Programmy modelirovaniya sluchainykh yavlenii dlya izucheniya programmirovaniya i matematiki [Programs for modeling random phenomena for learning programming and mathematics]. Information Technologies in Education, 2015, № 23, p. 30-42. (http://ite.kspu.edu/webfm_send/829) (in Russian)

Gayev E.A., Rozhok О., Ovcharchin N. (2014) Zvuk ta muzyka v kursi prohramuvannia [Sound and music in the course of programming]. Software Engineering, 2014, № 3(19), pp. 41 - 48. (in Ukrainian)

https://en.wikipedia.org/wiki/List_of_educatio nal_programming_languages

Discovery-Based Learning. https://en. wikipedia.org/wiki/Discovery_learning.

Entdeckendes Lernen. https://de. wikipedia.org/ wiki/Entdeckendes_Lernen. (in German)

An algorithmic programming language developed within Russian Buran space project. https://en.wikipedia.org/wiki/DRAKON

Computer Science Curriculum 2008. IEEE Computer Society. http://www.acm.org//education /curricula/ComputerScience2008.pdf

A full and modern overview of the Travelling Salesman Problem (TSP). https://en.wikipedia.org/wiki/Travelling_salesman_problem

Golovnev A.G. (2012) Priblizhennye algoritmy resheniya perestanovochnykh zadach.. Diss. magistra. [Approximation algorithms for solving commuting problems]. - Master degree Thesis, SPb.: Academic Educ.-Sci. Nanotechnology Center of RAS. - 25 p. (in Russian)

Mudrov V.I. (1969) Zadacha o kommivoyazhere. [The problem of the traveling salesman.]. Moscow: "Znanie", 62 p. (in Russian)

An overview of GPS technique. https:// en.wikipedia.org/wiki/GPS_navigation_device

TSP overview in German. https://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden.


Повний текст: PDF

Посилання

  • Поки немає зовнішніх посилань.


ISSN 2306-1472 (Online), ISSN 1813-1166 (Print)

Передплатний індекс 86179

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

Ulrich's Periodicals DirectoryIndex CopernicusDOAJSSMРИНЦWorldCatCASEBSCOCrossRefBASEDRIVERНаціональна бібліотека ім. ВернадськогоНауково-технічна бібліотека НАУ