Дискретная математика

Дискретная математика занимается изучением конечных свойств объектов, которые возникают как в различных разделах математики, так и в ее технических приложениях. Под конечными свойствами понимаются их ограниченность или перечислимость. Важными отличиями разделов дискретной математики от классических разделов непрерывной математики являются отсутствие понятия непрерывности и предела последовательности.

То, что в разделах дискретной математики рассматриваются конечные свойства объектов, совсем не означает, что при исследовании невстречаются бесконечные совокупности объектов или их конфигураций, однако, как правило, эти бесконечности являются счетными.

Разделы дискретной математики всегда существовали в математике, но стали выделяться в самостоятельную дисциплину в связи с развитием средств связи и появлением компьютеров.

К разделам дискретной математики обычно относят:

математическую логику,

теорию алгоритмов,

булеву алгебру,

теорию конечных автоматов,

теорию дискретных групп,

теорию графов,

комбинаторику.

теорию чисел.

Характерными примерами приложений различных разделов дискретной математики являются:

методы распознавания образов, основанные на теории принятия ре шений,

криптографические протоколы.

теория кодирования информации,

теория сложности алгоритмов и т. д.

В данном методическом пособии рассматриваются только несколько разделов дискретной математики, которые, на мой взгляд, наиболее востребованы для специалистов в области вычислительной техники и систем связи.

Разумеется, существует огромное количество литературы по дискретной математике и при желании всегда можно найти гораздо более обширную информацию по любой из тем, представленных в данном методическом пособии. Однако практическая ценность данной работы состоит в том, что информация, взятая из различных источников, удобно структурирована и излагается в размере, необходимом для получения студентами базовых знаний по предмету.

1.

Введение

в комбинаторику

Комбинаторика — один из разделов дискретной математики, который приобрел важное значение в связи с использованием его в ВТ, кибернетике, робототехнике. Большинство задач комбинаторики можно сформулировать как задачи теории конечных множеств, поэтому эти две темы — элементы теории множеств и комбинаторика — рассматриваются взаимосвязано.

Человеку часто приходится иметь дело с задачами, в которых нужно подсчитать число всех возможных способов расположения некоторых предметов или число всех возможных способов осуществления некоторого действия. Например, сколькими способами могли быть распределены золотая, серебряная и бронзовая медали на Олимпийских играх по баскетболу; или сколькими различными способами можно разместить здания на площади? Задачи такого типа называются комбинаторными.