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

Автор(и)

  • Yevgeny Gayev National Aviation University
  • Vadim Kalmikov National Aviation University

DOI:

https://doi.org/10.18372/2306-1472.72.11989

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

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

Анотація

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

Біографії авторів

Yevgeny Gayev, National Aviation University

Doctor of Engineering. Professor.

Professor on Aircraft Control Systems Department, National Aviation University, Kyiv, Ukraine.

Education: Kharkiv State University, Kharkiv, Ukraine (1971).

Research area: fluid mechanics and thermal physics, boundary layer theory, mathematics, computer science, history of science.

Vadim Kalmikov, National Aviation University

Student.

Aircraft Control Systems Department, National Aviation University, Kyiv, Ukraine.

Research area: computer science, aerodynamics.

Посилання

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.

Downloads

Опубліковано

01.11.2017

Як цитувати

Gayev, Y., & Kalmikov, V. (2017). Задача комівояжера в освіті інженерів-програмістів. Вісник Національного авіаційного університету, 72(3), 91–98. https://doi.org/10.18372/2306-1472.72.11989

Номер

Том 72 № 3 (2017)

Розділ

Професійна освіта

Ліцензія

Автори, які публікуються у цьому журналі, погоджуються з такими умовами:

  1. Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution License, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому журналі.

  2. Автори мають право укладати самостійні додаткові угоди щодо неексклюзивного розповсюдження роботи у тому вигляді, в якому вона була опублікована цим журналом (наприклад, розміщувати роботу в електронному сховищі установи або публікувати у складі монографії), за умови збереження посилання на першу публікацію роботи у цьому журналі.

  3. Політика журналу дозволяє і заохочує розміщення авторами в мережі Інтернет (наприклад, у сховищах установ або на особистих веб-сайтах) рукопису роботи, як до подання цього рукопису до редакції, так і під час його редакційного опрацювання, оскільки це сприяє виникненню продуктивної наукової дискусії та позитивно позначається на оперативності та динаміці цитування опублікованої роботи (див. The Effect of Open Access).