Назначение курса.

Введение.

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

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

Интересно отметить, что теория синтеза логических схем, пройдя почти полный " биологический цикл" на глазах одного поколения исследователей, представляет собой весьма поучительный пример того, как сильно подвержены моральному старению отрасли технических наук, слабо связанные с фундаментальной наукой. Ещё 10 лет назад все технические журналы были заполнены статьями по минимизации и синтезу логических схем. Большинство методов минимизации, разработанных учёными, сейчас забыты и не востребованы практикой. А те идеи, которые в то время считались сугубо теоретическими, нашли практическое применение в современной технике. Например, нечёткая логика, сети Петри и теория алгоритмов выдержали проверку временем и находят широкое применение в различных областях кибернетики и программирования, таких как системное программирование, сложность вычисления и искусственный интеллект.

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

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

Математическая логика и теория алгоритмов традиционно относятся к фундаментальной науке и считаются мало связанными с практикой и трудными для понимания. Действительно, когда Дж. Буль создал математический аппарат булевой алгебры, он долго не находил практического применения, однако в 20-ом столетии именно этот математический аппарат позволил спроектировать все узлы ЭВМ. Следовательно, первый из этих предрассудков успешно опровергается развитием вычислительной техники.

Что же касается предрассудка о трудности понимания этой дисциплины, то он в значительной степени происходит оттого, что книги по математической логике и теории алгоритмов написаны математиками для математиков.

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

Именно общая теория алгоритмов показала, что есть задачи неразрешимые ни при каком увеличении мощности вычислительных средств, а её бурно развивающаяся ветвь - теория сложности вычислений постепенно приводит к пониманию того, что бывают задачи разрешимые, но объективно-сложные, причём сложность их может оказаться в некотором смысле абсолютной, т.е. практически недоступной для современных ЭВМ.

В данном курсе ставились следующие задачи:

1. Изложить все рассматриваемые вопросы по возможности как можно более просто, но не проще чем это требуется для специалиста высшей квалификации.

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

3. Каждый раздел курса содержит вопросы для самопроверки. Для усвоения данного курса студент обязан ответить на все эти вопросы.

В результате освоения данного курса студент на основе ясного понимания соответствующих теоретических разделов должен уметь:

- реализовывать простейший вид логического преобразования информации в произвольном базисе логических функций;

- выделять в доказательных рассуждениях естественного языка логическую структуру, строить схемы формальных доказательств и проверять их правильность.