Weitere Kapitel dieses Buchs durch Wischen aufrufen
We consider the material of the elective course for the young students, and briefly describe both so-called hard problems and some methods necessary to develop programs for their implementation on the computer. For this, we are considering several real problems of discrete optimization. For each of them we consider both “greedy” algorithms and more complex approaches. The latter are, first of all, are considered in the description of concepts, understandable to “advanced” young students and necessary for the subsequent program implementation of the branches and bounds method and some associated heuristic algorithms. According to the authors, all this “within reasonable limits” is available for “advanced” young students of 14–15 years.
Thus, we present our view on the consideration of difficult problems and possible approaches to their algorithmization – at a level “somewhat higher than the popular science”, but “somewhat less than scientific”. And for this, the paper formulates the starting concepts which allows one of such “complications” to be carried out within the next half-year.
Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten
Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:
“Ah, gentlemen, you know why we are here. We’ve not much time, and quite a problem here” (Andrew Lloyd Webber and Tim Rice).
Although the latter statement can also be disputed, if we consider it not as a problem of implementing the algorithm of its solution found beforehand by a person (namely, this problem is usually considered in literature not connected with artificial intelligence), but as a task of finding such a solution.
Let us also note, that in the final of the student team championship in programming in the world (according to the ACM version) back in 1992, there was a task about the mentioned nonograms.
The concept of “heuristics” will be briefly discussed below. According to the authors, the easiest example of a heuristic algorithm accessible for young students can be QuickSort, [ 9] etc.
This is a very important concept, but we shall not strictly define it. The meaning will always be clear from the context.
Computerra. https://en.wikipedia.org/wiki/Computerra. Accessed 14 June 2018
Habr. https://habr.com. Accessed 14 June 2018. (in Russian)
Lipski, W.: Kombinatoryka dla programistów. Wydawnictwa Naukowo-Techniczne, Warszawa (2004). (in Polish)
Goodman, S., Stephen, S.: Introduction to the Design and Analysis of Algorithms. McGraw-Hill Computer Science Series, New York (1977)
Melnikov, B., Melnikova, E.: Some competition programming problems as the beginning of artificial intelligence. Inf. Educ. 6(2), 385–396 (2007)
Nonogram. https://en.wikipedia.org/wiki/Nonogram. Accessed 14 June 2018
Sudoku. http://www.sudoku.com. Accessed 14 June 2018
15 puzzle. https://en.wikipedia.org/wiki/15_puzzle. Accessed 14 June 2018
Wirth, N.: Algorithms + Data Structures = Programs. Prentice Hall, Upper Saddle River (1979) MATH
Polák, L.: Minimization of NFA using the universal automaton. Int. J. Found. Comput. Sci. 16(999), 335–341 (2005) MATH
Russel, S., Norvig, P.: Artificial Intelligence: A Modern Approach. Prentice Hall, Upper Saddle River (2010)
Luger, G.: Artificial Intelligence: Structures and Strategies for Complex Problem Solving. Addison Wesley, Boston (2008)
Makarkin, S., Melnikov, B., Trenina, M.: An approach to solving a pseudogeometric version of the traveling salesman problem. Izvestia of higher educational institutions. Volga Region. Phys. Math. Sci. 2(34), 135–147 (2015). https://elibrary.ru/item.asp?id=24254294. (in Russian)
Melnikov, B.: The complete finite automaton. Int. J. Open Inf. Technol. 5(10), 9–17 (2017)
Melnikov, B., Melnikova, E., Pivneva, S., Churikova, N., Dudnikov, V., Prus, M.: Multi-heuristic and game approaches in search problems of the graph theory. In: Information Technology and Nanotechnology Proceedings, ITNT-2018, pp. 2884–2894 (2018)
- Basic Concepts of the Elective Course on the Hard Computing Problems
Neuer Inhalt/© ITandMEDIA