Allmath.ru

Вся математика в одном месте!

 

 

 

 



Rambler's Top100


Математические основы информатики

Математические основы информатики. Прилуцкий М.Х. 220 с.

Учебник состоит из файлов формата Doc, запакованных WinRar. Скачать.

Содержание

  МНОЖЕСТВА

Множества. Конечные и бесконечные множества. Способы задания множеств.  Подмножества.  Множество всех подмножеств данного множества. О числе к-элементных подмножеств  n-элементного  множества.  Определение мощности множества всех подмножеств конечного множества (с использованием формулы бинома Ньютона).  Универсальное множество. Понятие алгебры.  Алгебра множеств. Понятия алгебраических и кардинальных операций. Алгебраические операции  над  множествами.  Законы  алгебры  множеств. Двойственность в алгебре множеств. Уравнения и системы уравнений в алгебре множеств.  Основные леммы,  используемые при решении уравнений в алгебре  множеств.  Мощность  множества.  Понятие счетного множества и континуума.  Канторовская диагональная процедура. Примеры счетных множеств. Доказательство счетности множества алгебраических чисел. Свойства счетных множеств.  Необходимые и достаточные условия бесконечности множества. Примеры континуальных множеств. Теорема Кантора-Бернштейна. Доказательство существования иррациональных и  трансцендентных  чисел. Кардинальные операции  над множествами.  Прямое произведение множеств. Проекция множеств.

БИНАРНЫЕ ОТНОШЕНИЯ

Бинарные отношения. Свойства бинарных отношений. Представления бинарных отношений в виде матриц,  орграфов,  верхнего и нижнего сечений. Операции над бинарными отношениями. Выражение свойств бинарных отношений через задающие их множества. Отношения порядка. Упорядоченные множества.  Отношение  эквивалентности.  Классы эквивалентности.  Системы различных представителей.  Лексикографическое отношение порядка. Мажоранта и миноранта множеств.  Максимум и минимум множеств. Точные грани множеств. Понятие графика. Функциональные, инъективные графики. Инверсия графика. Соответствия. Функциональные, инъективные, сюръективные и биективные соответствия.  Общее понятие функции.  Биективная  функция.

    АЛГЕБРА ВЫСКАЗЫВАНИЙ

Высказывания. Операции над высказываниями.  Формулы и функции алгебры логики.  О числе функций алгебры логики от n переменных.  Равносильные формулы.  Законы алгебры логики.  ДНФ и КНФ. Разложение функций алгебры логики по к  переменным. СДНФ и СКНФ.  Логические следствия. Проблема разрешимости в алгебре логики.  Тавтологии и противоречия. Основные схемы доказательств: если x то y, доказательство от противного, доказательство построением цепочки импликаций, доказательство разбором случаев.  Суперпозиция функций алгебры  логики.  Полные  системы функций. Понятие базиса. Алгебра Жегалкина. Полином Жегалкина. Теорема Жегалкина. Замкнутые  классы  функций.  Линейные  функции.  Монотонные функции. Теорема о монотонных функциях.  Двойственность в алгебре высказываний. Самодвойственные функции . Функции не сохраняющие константы 0, 1. Теорема Поста о функциональной полноте.

   ПЕРЕЧЕНЬ ПРАКТИЧЕСКИХ ЗАНЯТИЙ

1. Множества. Бинарные отношения.

1.1. Понятие множества.  Конечные и бесконечные множества. Способы задания множеств. Подмножества. Равенство множеств. Множество всех подмножеств  конечного множества. Пустое и  универсальное множество.

1.2. Операции над множествами.

1.3. Законы алгебры множеств.  Уравнения и системы уравнений.

1.4. Бинарные отношения.

 2. Алгебра логики.

 2.1. Высказывания. Операции над высказываниями.

 2.2. Формулы алгебры логики.

 2.3. Истинностные таблицы для сложных высказываний.

 2.4. ДНФ и КНФ. Приведение к ДНФ и КНФ.

 2.5. СДНФ и СКНФ. Приведение к СДНФ и СКНФ.

 2.6. Проверка полноты систем функций алгебры логики.

МОДЕЛИ ПРИНЯТИЯ РЕШЕНИЙ

1. ЛИНЕЙНЫЕ ОПТИМИЗАЦИОННЫЕ МОДЕЛИ.

Понятие оптимизационных задач. Примеры формальных постановок оптимизационных задач. Эквивалентные формы записи задач линейного программирования Геометрический смысл задач линейного программирования. Графическое решение задач линейного программирования. Теорема о выпуклости множества допустимых решений задачи линейного программирования. Теорема о выпуклости множества оптимальных решений задач линейного программирования. Симплекс метод решения задач линейного программирования. Искусственное начальное решение в задаче линейного программирования. Особые случаи применения симплекс-метода.

Двойственность. Двойственные задачи линейного программирования для различных форм. Лемма о соотношениях линейных форм. Лемма о равенстве линейных форм. Лемма о взаимодвойственности систем линейных однородных алгебраических уравнений. Основная теорема двойственности. Следствие из основной теоремы двойственности о связи оптимальных решений прямой и двойственной задач линейного программирования. Теорема равновесия. Интерпретация двойственных оцкнок. Двойственный симплекс-метод.

ПРАКТИЧЕСКИЕ ЗАНЯТИЯ
ЛИНЕЙНЫЕ ОПТИМИЗАЦИОННЫЕ МОДЕЛИ.

1.Различные эквивалентные формы записи задач линейного программирования. Геометрическая интерпретация.

2.Симплекс метод решения задач линейного программирования.

3.Искусственное начальное решение.

4.Особые случаи применения симплекс метода.

5.Двойственные задачи линейного программирования.

6.Связь оптимальных решений прямой и двойственной задач.

7.Двойственные оценки. Их интерпретация.

8.Двойственный симплекс метод.

МОДЕЛИ ПРИНЯТИЯ РЕШЕНИЙ

   2. ЭКСТРЕМАЛЬНЫЕ ЗАДАЧИ ПЕРЕБОРНОГО ТИПА.

Задачи целочисленного булева программирования. Каноническая и многомерная задачи о  ранце и их интерпретации. Задача коммивояжера и ее интерпретации. Задачи о назначениях и их интерпретации. Задача целочисленного линейного программирования в общей постановке. Метод ветвей и границ. Общая схема метода ветвей и границ Джеффриона-Марстена. Решение канонической задачи о ранце методом ветвей и границ.  Решение многомерной задачи о ранце методом ветвей и границ. Решение задачи коммивояжера методом ветвей и границ.  Решение задачи целочисленного линейного программирования  методом ветвей и границ. Решение задачи о ранце с использованием табличной схемы. Решение задачи о ранце  с использованием рекуррентных соотношений динамического программирования. Решение задачи коммивояжера с использованием рекуррентных соотношений динамического программирования.  Задачи теории расписаний. Задачи теории расписаний с одним обслуживающим прибором. Перестановочный прием в задачах теории расписаний. Теорема Лившица-Кладова. Задачи теории расписаний в общей постановке. Задача Джонсона. Графики Ганта. Постановка задачи теории расписаний как задачи частично-целочисленного линейного программирования. Сетевые модели. Расчет временных характеристик сетевых моделей.  Потоки в сетях. Теорема Форда-Фалкерсона о максимальном потоке.  Алгоритм Форда-Фалкерсона поиска максимального потока в транспортной сети. Алгоритмы решения задач о назначениях. Минимаксные задачи о назначениях. Задачи о назначениях с индивидуальными  предпочтениями.

ПРАКТИЧЕСКИЕ ЗАНЯТИЯ

      ЭКСТРЕМАЛЬНЫЕ ЗАДАЧИ ПЕРЕБОРНОГО ТИПА.

     1.Решение канонической  и  многомерной  задач о ранце методом ветвей и границ.

     2.Решение задачи коммивояжера методом ветвей и границ.

     3.Решение задачи  целочисленного  линейного  программирования методом ветвей и     границ.

     4.Задачи теории расписаний.

     5.Расчет временных характеристик сетевой модели.

     6.Потоки в сетях. Алгоритм Форда-Фалкерсона.

     7.Решение задачи о назначениях алгоритмом Куна.

     8.Минимаксные и максиминные задачи о назначениях. Задачи о назначениях с индивидуальными предпочтениями.


Хотите публиковаться на портале? Присылайте свои предложения, книги, статьи на info@allmath.ru.

[Школьная математика][Высшая математика][Прикладная математика][Олимпиадная математика][Услуги][Лучшие книги][Ссылки]

 

Copyright (c) 2004, Allmath.ru. e-mail: info@allmath.ru