Применение дискретной в информатике

РЕФЕРАТ КР содержит пояснительную записку на 23 листах формата А4, включающую 13 рисунков, 10 таблиц, 5 литературных источников.БУЛЕВА АЛГЕБРА, БУЛЕВА ФУНКЦИЯ, ТАБЛИЦЫ ИСТИННОСТИ, ДИЗЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА, КОНЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА, ПОЛИНОМ ЖЕГАЛКИНА, ПРОИЗВОДНАЯ ЛОГИЧЕСКОЙ ФУНКЦИИ, ГРАФ, АЛГОРИТМ, НЕЧЕТКОЕ МНОЖЕСТВО Рассмотрены следующие аспекты: применение математической логики в информатике выполнение логических операций, рассмотрено использование математической логики на практическом примере. практическое применение алгоритмов нахождения минимального и максимального деревьев покрытия и кратчайший путь, решена задача коммивояжера, применение метода нечеткого отношения предпочтения, для решения оптимизационной задачи.

При составлении работы использовались данные с разных источников, а именно были использованы различные методические рекомендации по дискретной математики и работы различных авторов (Воротников А.П Новиков Ф.А Логинов Б.М Яблонский С.В.), а также при решении задач выборе альтернатив на основе нечёткого отношения предпочтения использовались данные с журнала Hard’n’Soft. Цель работы: изучить применение методов дискретной математики в экономике, а именно научиться находить и применять различные алгоритмы для решения экономических задач и получить знания об использовании математической логики в информатике: научиться составлять эффективные алгоритмы, которые отличались бы скоростью и надежностью.

СОДЕРЖАНИЕ ВВЕДЕНИЕ 1 МАТЕМАТИЧЕСКАЯ ЛОГИКА 1.1 ПРИМЕНЕНИЕ МАТЕМАТИЧЕСКОЙ ЛОГИКИ В ИНФОРМАТИКЕ 1.2 ПРИМЕНЕНИЕ МАТЕМАТИЧЕСКОЙ ЛОГИКИ 2 ГРАФЫ 2.1 АЛГОРИТМ ДЕЙКСТРА 16 2.2 ЖАДНЫЙ АЛГОРИТМ 2.3 ПОСТРОЕНИЕ МИНИМАЛЬНОГО ОСТОВА 2.4 ЗАДАЧА КОММИВОЯЖЕРА 3 НЕЧЕТКИЕ МНОЖЕСТВА 22 ЗАКЛЮЧЕНИЕ 27 СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 28 ВВЕДЕНИЕ Курсовая работа представляет собой комплекс задач по следующим темам дисциплины: “Дискретная математика и дискретный анализ”: “Способы задания булевских функций”, “Теория графов”, “Стратегия нахождения минимального остова”, “Жадный алгоритм”, “Алгоритм Дейкстра”, “Задача Коммивояжера”, “Многокритериальный выбор альтернатив на основе нечёткого отношения предпочтения”. Курсовая работа содержит три части: математическая логика, графы, нечеткие множества.

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

Во второй части рассматривается применение теории графов в экономических задачах, которые подразделяются на: алгоритм построения минимального остова, который состоит в определении минимальных затрат на проезд от дома до супермаркета; Жадный алгоритм – решения задачи о максимальной загруженности линий, которые соединяют нефтеперерабатывающие заводы с новым месторождением нефти; Алгоритм Дейкстра – задача о нахождении оптимального пути, следовательно минимальных затрат на обеспечение отдыха своим сотрудникам; Задача Коммивояжера – максимизация прибыли и уменьшения затрат времени.

В третьей части рассмотрен способ нахождения более предпочтительно товара с помощью метода многокритериального выбора альтернатив на основе нечёткого отношения предпочтения. 1 МАТЕМАТИЧЕСКАЯ ЛОГИКА 1.1 ПРИМЕНЕНИЕ МАТЕМАТИЧЕСКОЙ ЛОГИКИ В ИНФОРМАТИКЕ Объединение математико-логической установки с иными математическими подходами, прежде всего с вероятностно-статистическими идеями и методами – на фоне глубокого интереса к вычислительным приборам было во многом определяющим в формировании замысла кибернетики, как комплексного научного направления, имеющего своим предметом процессы В ряде случаев используется технический аппарат математической логики (синтез релейно-контактных схем); сверх того, что особенно важно, идеи математической логики это, конечно же, в теории алгоритмов, но также и всей науки в целом и свойственный ей стиль мышления оказали и продолжают оказывать очень большое влияние на те своеобразные области деятельности, содержанием которых является автоматическая переработка информации (информатика), использование в криптографии и автоматизация процессов управления (кибернетика). Информатика – это наука, которая изучает компьютер, а также взаимодействие компьютера с человеком.

Строительство логических машин – интересная глава истории логики и кибернетики.

В ней запечатлены первые проекты создания искусственного разума и первые споры о возможности этого. Идея логических машин появилась в 13 веке у испанского схоластика Раймунда Луллия, рассматривалась затем Лейбницем и получило новое развитие в 19 веке, после возникновения математической логики.

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

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

Современные универсальные вычислительные машины являются вместе с тем логическими машинами.

Именно введение логических операций сделало их такими гибкими; оно же позволяет им моделировать рассуждения. Таким образом, арифметическая ветвь “разумных автоматов” соединились с логической. В 20-е годы, однако, формальная логика представлялась слишком абстрактной о метафизической для приложения к жизни. Между тем уже тогда можно было предвидеть внедрение логических исчислений в технику. Математическая логика облегчает механизацию умственного труда.Нынешние машины выполняют гораздо более сложные логические операции, нежели их скромные прототипы начала века. Проблема искусственного разума сложна и многогранна. Вероятно, не ошибёмся, если скажем, что окончательные границы механизации мысли можно установить лишь экспериментальным путём. Заметим ещё, что в современной кибернетики обсуждается возможность моделирования не только формальных, но и содержательных мыслительных процессов. 1.1.1 Математическая логика в технике.

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

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

Это реализуется, как правило, на основе сверхбольших интегральных, схем (СБИС). Однако технология СБИС и их структура предъявляет ряд специфических требований к алгоритмам, а именно: регулярность, параллельно—поточная организация вычислений, сверхлинейная операционная сложность (многократное использование каждого элемента входных данных), локальность связей вычислений, двумерность пространства реализации вычислений.

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

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

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

По-видимому, молекулярная электроника станет основой для создания ЭВМ шестого поколения. Все это объективно обусловливает интенсивные работы по методам синтезов алгоритмов обработки логических данных и их эффективному погружению в операционную среду бинарных элементов.Очевидно, что бинарные элементы и бинарные данные наиболее полно соответствуют друг другу в плане представления и обработки последних на таких элементах, если рассматривать их по отдельности. Действительно, положим, алгебра логики над числами (0,1) реализуется на бинарном элементе полном использовании его операционного ресурса.

Другими словами, ставится вопрос об эффективности, а иногда вообще возможности реализации данного алгоритма на такой сети (структуре). В этом состоит суть погружения алгоритма в структуру. 1.1.2 Математическая логика в криптографии.Криптография изучает методы пересылки сообщений в замаскированном виде, при которых только намеченные отправителем получатели могут удалить маскировку и прочитать сообщение.

Общая схема защиты информации представлена на рисунке 2. Этап кодирования от ошибок основан на внесении в передаваемое сообщение избытка информации, достаточного для преодоления помех на линии связи.Например, допустим, передается последовательность символов типа “0” и “1”. При этом в сети связи с некоторой вероятностью могут происходить ошибки приема сигнала “0 “ вместо сигнала “1” или наоборот, тогда кодер на каждый символ ai сообщения передает пятью импульсами 0, если ai -0 и наоборот.

На приемном конце принимаемая последовательность импульсов разбивается по пять импульсов, называемая блоками. Если в принятом блоке содержится 2 и менее импульса 0, то принимается решение о том, что передавался символ ai-1. Таким образом, исходная вероятность ошибки будет значительно снижена. Более элегантные методы кодирования, которые при достаточной надежности позволяют вносить не такой большой избыток информации.Для выражения в информации требуется ввести некоторый алфавит, из которого будет состоять сообщение (конечные упорядоченные множества из этих символов). Обозначим через A – мощность выбранного алфавита.

Будем также считать, что все множества информации или , что то же самое, множество всевозможных сообщений конечно. В качестве меры информации в сообщении данной длины можно взять Log2 от числа всевозможных сообщений конечно.Тогда объем информации, падающий на один символ алфавита X=log2a. Далее имеем дело со словами длинной S, тогда всего таких слов будет N=AS (декартова S- степень алфавита), а следовательно, количество информации в слове Y=Log2N=Log2As=SX. Львиную долю криптоанализа составляют мето.