Тема 1. Введение.

План:

1.      Определение и роль дискретной математики.

2.      Связь дискретной математики с другими науками

Цель:   Знакомство понятием "Дискретная математика". Установление роли дискретной математики как составляющего элемента в математической подготовке специалистов в области информатики и компьютерных технологий.

1. Определение и роль дискретной математики.

Дискретная математика - совокупность математиче­ских дисциплин, изучающих свойства абстрактных дискретных объектов, т.е. свойства математических моделей объектов, про­цессов, зависимостей, существующих в реальном мире, которы­ми оперируют в различных областях знаний. Таким образом, дис­кретный анализ - самостоятельный раздел современной мате­матики, изучающий свойства различных структур, имеющих ко­нечный характер. Они могут возникать как в самой математике, так и в ее приложениях. К их числу принято относить объекты, имеющие прерывный (дискретный) характер в отличие от объек­тов, изучаемых классической математикой и носящих непрерыв­ный характер.

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

Дискретная математика или дискретный анализ -сравнитель­но новое направление в математике, объединяющее отдельные ее разделы, ранее сформированные как самостоятельные теории. К ним относятся математическая логика и теории множеств, гра­фов, кодирования, автоматов.

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

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

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

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

Стимулом для развития многих направлений дискретной мате­матики явились запросы теоретической кибернетики, непосред­ственно связанной с развитием ЭВМ.

Теоретическая кибернетика занимается изучением разнообраз­ных практических проблем средствами дискретной математики:

~  Растущий поток информации и проблемы ее передачи, обра­ботки и хранения привели к возникновению и развитию теории кодирования;

~  Различные экономические задачи, задачи электротехники сти­мулировали создание и развитие теории графов;

~  Связь релейно-контактных схем с формулами алгебры логики и их использование для описания функционирования автоматов дали начало развитию и применению математической логики и теории автоматов. Математическая логика в широком смысле изучает основания математики, принципы построения матема­тических теорий.

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

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

2. Связь дискретной математики с другими науками

Дискретная математика имеет тесную связь со многими дисциплинами и науками.  

Кибер­нетические области информатики используют в качестве аппара­та, язык - как фундаментальной, так и прикладной математики. Од­нако надо учитывать, что эти науки связаны между собой и их деление условно.

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

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

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

Методы, разрабатываемые дискретной математикой, часто ис­пользуются в различных направлениях информатики. Так, теоре­тическая информатика (или теоретическая кибернетика) исполь­зует математические методы для построения и изучения моделей обработки, передачи и использования информации. Объекты ее изучения -дискретные множества. Теоретическая информатика является как поставщиком задач, так и потребителем методов дискретной математики.

Достижения математической логики используются для ана­лиза процессов переработки информации с помощью ЭВМ.

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

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

Системный ана­лиз изучает структуру реальных объектов и дает способы их фор­мализованного описания. Общая теория систем как часть систем­ного анализа изучает различные по характеру системы с общих позиций. Теория массового обслуживания изучает широкий класс моделей передачи и переработки информации в системах массо­вого обслуживания (СМО).

В настоящее время нашла широкое применение наука семи­отика, которая исследует знаковые системы самой различной природы. Четко различая понятие знака и знаковой ситуации, се­миотика включает такие разделы, как синтактика (что связывает знак), семантика (что выражает знак), сигматика (что обозначает знак) и прагматика (что дает знак). Синтаксический аспект ин­формации, связанный со структурными и статистическими оцен­ками, в основном рассматривается в информатике и вычисли­тельной технике. Сигматический аспект рассматривает теория сиг­налов и кодирования. Знаковые системы благодаря своей гибкости способны обеспечить разнообразные запросы пользователей. Функ­циональное единство семантики и прагматики имеет широкие пер­спективы: появляется возможность установления аналогий между функционированием систем естественного и искусственного про­исхождения.

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

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

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

Искусственный интеллект -одно из молодых и перспектив­ных направлений информатики, появившееся во второй полови­не XX в. на базе вычислительной техники, математической логи­ки, программирования, психологии, лингвистики и других от­раслей знаний. Объектами его изучения являются межпредметные процедуры (метапроцедуры), используемые при решении задач, традиционно называемых интеллектуальными. Проникая в тайны творческой деятельности людей, искусственный интеллект созда­ет программные и программно-аппаратные модели таких мета­процедур.

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

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

Для нас представляют интерес все эти направления современ­ной информатики. Теперь мы сможем осознать место дискретной математики в системе знаний, необходимых для тех, кто связал свою жизнь с компьютером.

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

На знаниях законов логики базируются принципы алгоритми­зации, которые лежат в основе программирования. Фундаментом всей вычислительной техники и автоматики является преобразо­вание двоичных сигналов, анализ, проектирование и использова­ние логических схем. Основу современной математической логи­ки составляют исчисление высказываний и исчисление предика­тов. Любой язык программирования базируется на исчислении высказываний и исчислении предикатов. В частности, на языке про­граммирования "Пролог" анализируются различные виды дедук­тивных умозаключений, выводятся достоверные следствия из них. Широко применяются логические методы для построения баз дан­ных. Активно используются знания логики в развитии современ­ных направлений информационных наук. Например, ряд проблем искусственного интеллекта невозможно решить без знаний основ классической логики. Рассмотрим их более подробно.

Представление знаний - методы и приемы формализации ин­формации из различных областей знаний для их хранения, клас­сификации, обобщения и применения при решении конкретных задач.

Моделирование рассуждений - изучение и формализация раз­личных умозаключений и их использование при решении задач средствами ЭВМ.

Методы диалогового общения человека и машины. Специфика работы программистов заключается в том, что оппонентом в ди­алоге выступает компьютер. В него заложены программы, обрабатывающие только точно сформулированную информацию. В про­цессе ее обработки возникают два варианта диалогового общения:

~     ЭВМ самостоятельно задает вопросы по полученной инфор­мации согласно заложенной в нее программе;

~     Компьютер задает вопросы, которые заложены заранее в за­готовленную программистом модель беседы.

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

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

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

Требования к знаниям умениям и навыкам.

Студенты должны  иметь представление: о роли и месте дискретной  математики в процессе профес­сиональной подготовке по специальности. Иметь представление о теоретической и прикладной роли  дискретной  математики в информатике