SOME COMBINATORIAL PROBLEMS ON BINARY MATRICES IN PROGRAMMING COURSES

K.Y. Yordzhev

doi:10.14308/ite000313

K.Y. Yordzhev South-West University ''N. Rilsky'', Blagoevgrad, Bulgaria

Keywords: stimulation of students' interest, motivation to study, education in programming, binary matrix, S-permutation matrices, combinatorial algorithms

Abstract

The study proves the existence of an algorithm to receive all elements of a class of binary matrices without obtaining redundant elements, e. g. without obtaining binary matrices that do not belong to the class. This makes it possible to avoid checking whether each of the objects received possesses the necessary properties. This significantly improves the efficiency of the algorithm in terms of the criterion of time. Certain useful educational effects related to the analysis of such problems in programming classes are also pointed out.

Downloads

Download data is not yet available.

Metrics

Metrics Loading ...

References

1. M. Aigner Combinatorial theory. Springer-Verlag, 1979.
2. H. Anand, V. C. Dumir, H. Gupta A combinatorial distribution problem. Duke Math. J. 33 (1966), 757-769.
3. G. Dahl Permutation Matrices Related to Sudoku. Linear Algebra and its Applications, 430 (2009), 2457-2463.
4. I. Good, J. Grook The enumeration of arrays and generalization related to contingency tables. Discrete Math, 19 (1977), 23-45.
5. H. Gupta, G. L. Nath Enumeration of stochastic cubes. Notices of the Amer. Math. Soc. 19 (1972) A-568.
6. P. Lancaster Theory of Matrices. Academic Press, NY, 1969.
7. R. P. Stanley Enumerative combinatorics. V.1, Wadword & Brooks, California, 1986.
8. M. L. Stein, P. R. Stein Enumeration of stochastic matrices with integer elements. Los Alamos Scientific Laboratory Report LA-4434, 1970.
9. K. Yordzhev On a Relationship Between the S-permutation Matrices and the Bipartite Graphs. (to appear).
10. V. I. Baranov, B. S. Stechkin Ekstremal'nye nombinatornye zadachi i ix prilozhenija. Moskva, Nauka, 1989
11. K. Ja. Jordzhev Kombinatorni zadachi nad binarni matrici. Matematika i matematichesko obrazovanie, 24 (1995), 288-296.
12. P. Nakov, P. Dobrikov Programirane=++Algoritmi. Treto izdanie, Sofija 2005, ISBN 954-9805-06-X.
13. V. E. Tarakanov Kombinatornye zadachi na binarnyx matricax. Kombinatornyj analiz, Moskva, izd-vo MGU, 1980, vyp.5, 4-15.
14. V. E. Tarakanov Kombinatornye zadachi i (0,1)-matricy. Moskva, Nauka, 1985.
15. V. S. Shevelev Reducirovannye latinskie prjamougol'niki i kvadratnye matricy s odinakovymi summami v strokax i stolbcax. Diskretnaja matematika, tom 4, vyp. 1, 1992, 91-110.