It is stated that the matter of correct selection of the criterion in the formulation of the problem and the assessment of time (combinatorial) complexity of the algorithm for its solution is the most important and difficult to acquire. The authors propose the scenarios of interactive seminars that use the pre-planned wrong decisions technique enabling students to form their professional competence and scientific reasoning skills, the ability
to ask questions and analyze the problem solutions. Using the examples of optimization problems on graphs and networks the authors analyze the greedy algorithm and give the examples of matroids. In conclusion, they consider dismantled methods of finding optimal solutions in problems of placement.
Keywords: interactive teaching method; algorithms’ combinatorial complexity; NP-completeness; graph; network; tree; matching; optimization on graphs and networks; greedy algorithm; matroid; spanning tree of minimum and maximum weight; shortest tree; assignment problem.
References
- Revyakin A. M., Bardushkina I. V., Bardushkin V. V. Stsenarii problemnykh lektsii po lineinoi algebre, provodimykh v interaktivnykh formakh (Scenarios of Problem-Based Interactive Lectures on Linear Algebra), Vtorye Vserossiiskie Dekartovskie chteniya “Dekartovskii ratsionalizm i sovremennaya nauka”, mat-ly nauch.-prakt. konf. (17 apr. 2015, Moskva, Zelenograd), M., MIET, 2015, pp. 159—169.
- Revyakin A. M., Bardushkina I. V. Matematicheskie metody modelirovaniya v ekonomike (Mathematical Modeling in Economics), M., MIET, 2013, 327 p., il.
- Matematicheskie metody prinyatiya reshenii i setevye modeli v upravlenii i ekonomike (Mathematical Methods of Decision and Network Models in Administration and Economics), I. N. Abanina, V. V. Bardushkin, I. V. Bardushkina i dr., pod obshch. red. I. N. Abaninoi, A. M. Revyakina, M., MGADA, 2014, 176 p., il.
- Revyakin A. M. Setevye modeli dlya prinyatiya reshenii (Network Models for Decison-Making), Vestnik Moskovskogo gorodskogo pedagogicheskogo universiteta, Seriya Ekonomika, 2013, No. 3 (24), pp. 173—182.
- Geri M., Dzhonson D. Vychislitel’nye mashiny i trudnoreshaemye zadachi (Computers and Intractability), M., Mir, 1982, 416 p., il.
- Isachenko A. N., Revyakin A. M. Matroidy v matematicheskom modelirovanii ekonomicheskikh sistem (Matroids in Mathematical Modeling of Economic Systems), Ekonomicheskie i sotsial’no-gumanitarnye issledovaniya, 2015, No. 1 (5), pp. 13—18.
- Revyakin A. M. Matroids, Journal of Mathematical Sciences, 2002, Vol. 108, No. 1, pp. 71—130.