Сборник задач по дискретной математике. 2-е изд. М: Наука, 1992, 368 с





Скачать 101.95 Kb.
НазваниеСборник задач по дискретной математике. 2-е изд. М: Наука, 1992, 368 с
Дата публикации31.07.2013
Размер101.95 Kb.
ТипЛитература
100-bal.ru > Математика > Литература

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


3-й семестр 2012–2013, спец. ИУ-7

ЛИТЕРАТУРА

Основная литература (ОЛ)


1.Белоусов А.И., Ткачев С.Б. Дискретная математика: Учеб. для вузов / Под ред. В.С. Зарубина и А.П. Крищенко. – 4-е изд. - М. Изд-во МГТУ им. Н.Э. Баумана, 2006, – 743 с.

2.Яблонский С.В. Введение в дискретную математику. – 3-е изд.. – М: Высшая школа, 2001. – 384 с.

3.Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике. – 2-е изд. – М: Наука, 1992, – 368 с.

4.Дж. Андерсон. Дискретная математика и комбинаторика. – М., СПб, Киев: Изд. Дом. «Вильямс», 2003. – 960 с.

5.Белоусов А.И., Власов П.А. Элементы комбинаторики: метод. указания к выполнению домашнего задания. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2012. – 53 с.

Дополнительная литература (ДЛ)


  1. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. В 2 т. – М.: Мир, 1978.

6.Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979. – 536 с.

7.Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений, 2-е изд.. – М.: Издательский дом «Вильямс», 2002. – 528 с.

8.Евстигнеев В.А. Применение теории графов в программировании. – М.: Наука, 1985. – 352 с.

9.Блюменфельд В.К., Котов В.Е. Теория схем программ. – М.: Наука, 1991. – 248 с.

10.Зыков А.А. Основы теории графов. – М.: «Вузовская книга», 2004. – 664 с.

11.Лекции по теории графов / В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич. – М: Наука, 1990. – 383 с.

12.Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. – М: Наука, 1975, – 240 с.

13.Шапорев С.Д. Дискретная математика: курс лекций и практических занятий. – СПб, БХВ-Петербург, 2006. – 400 с.

14.Прикладная комбинаторная математика (сб. статей). – М.: Мир, 1968.- 362 с.

Лекции

МОДУЛЬ 1: Множества, отношения, алгебры


Лекция 1. Предмет и метод дискретной математики. Множества. Кортеж. Декартово произведение.

ОЛ-1 1.1, 1.2; ОЛ-2 1.1.

ДЛ-4 1.6; МРК, конспект лекций.

Лекция 2. Отношение арности . Отображения и их классификация. Операции и предикаты.

ОЛ-1 1.3, 2.2; ОЛ-2 1.3.

Лекции 3–4. Отношения эквивалентности и фактор-множества. Частично упорядоченные (ч.у.) множества. Теорема о неподвижной точке.

ОЛ-1 1.5–1.8, 1.9.

Лекция 5. Алгебраические структуры. Группоиды, полугруппы, группы.

ОЛ-1 2.1–2.2; ОЛ-2 2.1, 2.2.

Лекция 6. Циклические группы. Подгруппы. Теорема Лагранжа.

ОЛ1 2.6, 2.7, ОЛ-2 2.1, 2.2.

Лекции 78. Кольца, тела, поля.

ОЛ1 2.3, 2.4, ОЛ-2 2.1, 2.2.

Лекции 910. Полукольца. Решение систем линейных уравнений в замкнутых полукольцах.

ОЛ1 3.1–3.3.

МОДУЛЬ 2: Элементы теории графов


Лекция 11. Основные понятия теории графов: неориентированные и ориентированные графы, цепи, пути, циклы, контуры. Подграфы. Компоненты и бикомпоненты.

ОЛ-1 5.1; ДЛ-2 гл.2 §2, 3; ДЛ-7 гл. 1.

Лекция 12. Деревья и их классификация. Теорема о числе листьев в полном бинарном дереве. Дерево решений и задача сортировки.

ОЛ-1 5.3; ДЛ-2 3.4.

Лекции 13-14. Методы систематического обхода вершин графа: поиск в глубину и поиск в ширину.

ОЛ-1 5.5; ДЛ-2 5.2, 5.4.

Лекция 15. Гомоморфизм и изоморфизм графов. Группа автоморфизмов графа и ее вычисление.

ОЛ-1 5.7; ДЛ-7 гл. 1, §11.

Лекция 16. Задача о путях во взвешенном ориентированном графе и ее решение с помощью алгоритма Флойда — Уоршелла — Клини. Задача о достижимости и поиске кратчайших расстояний между двумя узлами графа.

ОЛ-1 5.6; ДЛ-2 5.6–5.10; ДЛ-4 гл. 3 §1.

МОДУЛЬ 3: Регулярные языки и конечные автоматы


Лекция 17. Алфавит, слово, язык. Операции над языками, регулярные языки.

ОЛ-1 7.1, 7.4.

Лекция 18. Понятие конечного автомата (КА). Анализ и синтез КА. Теорема Клини о совпадении класса языков, допускаемых КА и класса регулярных языков.

ОЛ-1 7.5.

Лекция 19. Детерминизация и минимизация КА. Регулярность дополнения регулярного языка и пересечения двух регулярных языков. Проблемы пустоты и эквивалентности.

ОЛ-1 7.6, 7.7.

Лекция 20. Лемма о разрастании для регулярных языков.

ОЛ-1 7.8.

МОДУЛЬ 4: Элементы комбинаторики


Лекция 21. Основные комбинации. Формулы включения и исключения.

ОЛ-2 часть 2, §3; ОЛ-4 12.3, 11.1, 11.2; ОЛ-5 1.1, 1.2; ДЛ-9 2.14, 2.15.

Лекция 22. Ладейные полиномы. Подстановки с запрещенными позициями. Сюръекции и разбиения.

ОЛ-4 12.3, 12.4.

Лекция 23. Линейные рекуррентные соотношения.

ОЛ-4 11.1–11.2; ОЛ-5 2.1–2.4, ДЛ-9 2.7–2.9, 2.11.

Лекция 2425. Теория перечисления Пойя. Производящие функции.

ОЛ-4 19.1, 19.2, 13.1, 13.2, 13.5; ОЛ-5 3.1–3.4; ДЛ-10, с. 61–107.

Практические занятия

МОДУЛЬ 1: Множества, отношения, алгебры


Занятие 1. Доказательство теоретико-множественных тождеств.

ОЛ-1 Д.1.2, задачи 1.1–1.6.

Занятие 2. Операции над соответствиями. Исследование свойств бинарных отношений.

ОЛ-1 задачи 1.7–1.20.

Занятие 3. Отношения эквивалентности и порядка.

ОЛ-1 задачи 1.21–1.31.

Занятие 4. Группоиды, полугруппы, группы

ОЛ-1 задачи 2.1–2.8.

Занятия 5-6. Кольца, тела, поля. Полукольца.

ОЛ- 1 задачи 2.10–2.19; 3.1–3.4.

МОДУЛЬ 2: Элементы теории графов


Занятие 7. Основные понятия теории графов. Некоторые комбинаторные задачи на графах .

ОЛ-1 задачи 5.1–5.19.

Занятие 8. Поиск в глубину и поиск в ширину.

ОЛ-1 задачи 5.25–5.31.

Занятие 9. Распознавание изоморфизма графов. Группа автоморфизмов графа и ее вычисление.

ОЛ-1 задачи 5.6, 5.8; ОЛ-5 3.1.

Занятие 10. Задача о путях во взвешенном ориентированном графе и ее решение с помощью алгоритма Флойда — Уоршелла — Клини. Задача о достижимости и поиске кратчайших расстояний между двумя узлами графа.

ОЛ-1 задачи 5.32–5.34.

МОДУЛЬ 3: Регулярные языки и конечные автоматы


Занятие 11. Анализ и синтез конечных автоматов.

ОЛ-1 задачи 7.9–7.21.

Занятие 12. Детерминизация и минимизация конечных автоматов.

ОЛ-1 задачи 7.29–7.33; задача 7.34.

Занятие 13. Лемма о разрастании для регулярных языков.

ОЛ-1 задача 7.35.

МОДУЛЬ 4: Элементы комбинаторики


Занятие 14. Элементы комбинаторики: формулы включения и исключения.

ОЛ-5 1.3.

Занятие 15. Рекуррентные соотношения.

ОЛ-4 задачи к разд. 11.2; ОЛ-5 2.4.

Занятие 16. Производящие функции. Элементы теории Пойя.

ОЛ-4 задачи к разд. 13.3, 19.1 и 19.2; ОЛ-5 3.5.

Материалы для подготовки

МОДУЛЬ 1: Множества, отношения, алгебры

Вопросы для подготовки к рубежному контролю


15.Множества, подмножества. Способы определения множеств. Равенство множеств. Операции над множествами (объединение, пересечение, разность, симметрическая разность, дополнение). Методы доказательства теоретико-множественных тождеств.

16.Неупорядоченная пара, упорядоченная пара, кортеж. Декартово произведение множеств.

17.Отображения: область определения, область значений. Инъективное, сюръективное и биективное отображения. Частичное отображение.

18.Соответствия. График и граф соответствия, область определения, область значения. Сечение соответствия. Сечение соответствия по множеству. Функциональность соответствия по компоненте. Бинарные и n-арные отношения. Связь между отношениями, соответствиями и отображениями.

19.Композиция соответствий, обратное соответствие и их свойства (с доказательством).

20.Специальные свойства бинарных отношений на множестве (рефлексивность, иррефлексивность, симметричность, антисимметричность, транзитивность).

21.Классификация бинарных отношений на множестве: эквивалентность, толерантность, порядок, предпорядок, строгий порядок.

22.Отношение эквивалентности. Класс эквивалентности. Фактор-множество.

23.Отношения предпорядка и порядка. Наибольший, максимальные, наименьший и минимальные элементы. Точная нижняя и верхняя грани множества.

24.Точная верхняя грань последовательности. Индуктивное упорядоченное множество. Теорема о неподвижной точке (с доказательством). Пример вычисления неподвижной точки.

25.Операции на множестве. Понятие алгебраической структуры. Свойства операций (ассоциативность, коммутативность, идемпотентность). Нуль и нейтральный элемент (единица) относительно операции. Примеры. Универсальная алгебра, носитель, сигнатура. Примеры. Однотипные алгебры.

26.Группоиды, полугруппы, моноиды. Единственность нейтрального элемента. Обратный элемент. Группа. Единственность обратного элемента в группе.

27.Циклическая полугруппа (группа). Образующий элемент. Примеры конечных и бесконечных циклических полугрупп и групп. Порядок конечной группы. Порядок элемента. Теорема о равенстве порядка конечной циклической группы порядку группы.

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

29.Тела и поля. Примеры полей. Область целостности. Теорема о конечной области целостности (с доказательством). Поля вычетов. Решение систем линейных уравнений в поле вычетов.

30.Подполугруппа, подмоноид, подгруппа. Примеры. Циклические подгруппы. Подкольца и подполя.

31.Смежные классы подгруппы по элементу. Теорема Лагранжа. Изоморфизм групп. Примеры.

32.Полукольцо. Идемпотентное полукольцо. Естественный порядок идемпотентного полукольца.

33.Замкнутое полукольцо. Итерация элемента. Примеры вычисления итерации в различных замкнутых полукольцах.

34.Непрерывность операции сложения в замкнутом полукольце. Теорема о наименьшем решении линейного уравнения в замкнутом полукольце.

35.Квадратные матрицы порядка n над идемпотентным полукольцом. Теорема о полукольце квадратных матриц. Замкнутость полукольца квадратных матриц над замкнутым полукольцо. Решение систем линейных уравнений в замкнутых полукольцах.

Типовые задачи рубежного контроля


  1. Доказать тождество .

36.Доказать тождество .

37.Доказать тождество .

38.Доказать, что для любой функции f и любых множеств A и B имеют место соотношения: а) ; б) .

39.Построить график и граф бинарного отношения , заданного на множестве , если .

40.Для бинарного отношения на множестве построить графики отношений и .

41.Для бинарного отношения на множестве найти , , , , , .

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

43.Ассоциативна ли операция на множестве M, если , .

44.Решить уравнение в группе , если , , .

45.Решить уравнение в группе , где .

46.Найти в решение системы уравнений



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

МОДУЛЬ 2: Элементы теории графов

Вопросы для подготовки к рубежному контролю


  1. Основные понятия теории графов: неориентированные и ориентированные графы, цепи, пути, циклы, контуры, маршруты. Подграфы. Компоненты и бикомпоненты.

48.Деревья и их классификация. Теорема о числе листьев в полном p-дереве.

49.Методы систематического обхода вершин графа: поиск в глубину и поиск в ширину.

50.Поиск кратчайших расстояний от фиксированной вершины: алгоритм волнового фронта и поиск в ширину в орграфе с числовыми метками дуг.

51.Поиск фундаментальных циклов в неориентированном графе.

52.Гомоморфизм и изоморфизм графов. Группа автоморфизмов графа и ее вычисление.

53.Задача о путях в ориентированном графе, размеченном над полукольцом и ее решение с помощью алгоритма Флойда — Уоршелла — Клини. Задача о достижимости и поиске кратчайших расстояний между двумя узлами графа.

Типовые задачи рубежного контроля


  1. Орграф задан матрицей меток дуг:

.

Используя поиск в ширину, найти кратчайшие расстояния от источника (вершины v1), Показать изменение содержимого очереди вершин.

54.Для орграфа, используя алгоритм Дейкстры, найти кратчайшие расстояния от источника (вершины v1), если орграф задан следующей матрицей меток дуг:

.

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

.

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

.

57. Найти группу автоморфизмов неориентированного графа, заданного матрицей смежности вершин.

.

58.Найти порядок группы автоморфизмов изображенного ниже графа



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

МОДУЛЬ 3: Регулярные языки и конечные автоматы

Вопросы для подготовки к рубежному контролю


  1. Алфавит, слово, язык. Операции над языками, полукольцо всех языков в заданном алфавите и его замкнутость.

60.Регулярные языки и регулярные выражения.

61.Понятие конечного автомата (КА) и языка, допускаемого КА. Анализ и синтез КА.

62.Теорема Клини о совпадении класса языков, допускаемых КА и класса регулярных языков.

63.Детерминизация и минимизация КА. Регулярность дополнения регулярного языка и пересечения двух регулярных языков. Проблемы пустоты и эквивалентности.

64.Лемма о разрастании для регулярных языков.

Типовые задачи рубежного контроля


  1. Построить конечный автомат по регулярному выражению . Детерминизировать и минимизировать его.

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

66.Найти язык, допускаемый конечным автоматом, изображенным на рисунке.



67.Решить следующую систему линейных уравнений с регулярными коэффициентами:



68.Построить конечный автомат, допускающий те и только те цепочки в алфавите {a,b}, которые не допускает следующий конечный автомат: вход , выход , дуги с метками , , , , . Для построенного автомата записать регулярное выражение, задающее его язык.

69.Задача 7.32 из [ОЛ1].

70.Доказать, что если язык регулярен, то и язык для любого регулярен.

71.Пусть . Доказать, что язык нерегулярен.

72.При каких k язык в алфавите {a} будет регулярным?

МОДУЛЬ 4: Элементы комбинаторики

Вопросы для подготовки к рубежному контролю


  1. Формулы включения и исключения.

73.Задача о подсчете беспорядков.

74.Ладейные полиномы и подстановки с запрещенными позициями.

75.Однородные линейные рекуррентные соотношения. Характеристический полином и характеристическое уравнение. Структура общего решения в случае вещественных и комплексных корней характеристического полинома. Частное решение, удовлетворяющее начальным условиям.

76.Неоднородные линейные рекуррентные соотношения. Структура общего решения. Поиск частного решения методом подбора.

77.Лемма Бернсайда.

78.Теорема Пойа.

Типовые задачи рубежного контроля


  1. Сколь много положительных целых чисел, меньших или равных числа 2300, взаимно простых с 700?

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

80.Найти число всех перестановок из 6 элементов с запрещенными парами: (3,3), (3,4), (4,1), (4,2), (5,4), (5,5), (5,6).

81.Найти общее решение соотношения .

82.Найти решение соотношения при заданных начальных условиях: , , , .

83.Найти общее решение для соотношения .

84.Найти структурный перечень двухцветных раскрасок правильного пятиугольника.

85.Найти число двухцветных раскрасок 9-клеточной доски.

Добавить документ в свой блог или на сайт

Похожие:

Сборник задач по дискретной математике. 2-е изд. М: Наука, 1992, 368 с iconСборник задач по аналитической геометрии. Спб., Изд-во «Профессия»,2002....
Клетеник Д. В. Сборник задач по аналитической геометрии. Спб., Изд-во «Профессия»,2002. (15 экз.)
Сборник задач по дискретной математике. 2-е изд. М: Наука, 1992, 368 с iconСборник задач по высшей математике. М.: Наука, 2002. Общий курс высшей...
Письменный Д. Т. Конспект лекций по высшей математике: полный курс. –М.: Айрис-пресс, 2006г
Сборник задач по дискретной математике. 2-е изд. М: Наука, 1992, 368 с iconСборник задач по высшей математике : учеб пособие / В. П. Минорский....
Сборник задач по высшей математике : учеб пособие / В. П. Минорский. 15-е изд. М. Физматлит, 2010. 336 с. Isbn 9785-94052-184-6 :...
Сборник задач по дискретной математике. 2-е изд. М: Наука, 1992, 368 с iconТестовые вопросы по Дискретной математике
Предлагаемая программа элективного курса «Текстовые задачи» актуальна в период перехода к новым образовательным стандартам по математике....
Сборник задач по дискретной математике. 2-е изд. М: Наука, 1992, 368 с iconСборник задач по высшей математике : учеб пособие / В. П. Минорский....
Письменный, Д. Т. Конспект лекций по высшей математике: полный курс / Д. Т. Письменный. 9-е изд. М. Айрис-пресс, 2009. 608 с ил....
Сборник задач по дискретной математике. 2-е изд. М: Наука, 1992, 368 с iconСборник задач по высшей математике : учеб пособие / В. П. Минорский....
Шипачев,В. С. Курс высшей математики : учебник / В. С. Шипачев; под ред. А. Н. Тихонова. 4-е изд., испр. М. Оникс, 2009. 608 с ил....
Сборник задач по дискретной математике. 2-е изд. М: Наука, 1992, 368 с iconСборник задач по физике 8-10 Просвещение 26 30 116
Сборник заданий для подготовки и проведения письменного экзамена по математике за курс средней школы
Сборник задач по дискретной математике. 2-е изд. М: Наука, 1992, 368 с iconПрограмма по формированию навыков безопасного поведения на дорогах...
Рыкмевич А. П., сборник задач по физике. Для 9-11 классов средней школы. М.: Просвещение 1992
Сборник задач по дискретной математике. 2-е изд. М: Наука, 1992, 368 с iconРабочая программа «Практикум по решению задач по математике» 10 класс
Рабочая программа составлена на основе Примерной программы основного общего образования по математике (Сборник серии Стандарты второго...
Сборник задач по дискретной математике. 2-е изд. М: Наука, 1992, 368 с iconКонспект лекций по высшей математике М, Айрис,2005 Беклемишева Л....
Курс высшей математики. Введение в математический анализ. Дифференциальное исчисление. Лекции и практикум: Учебное пособие / Под...
Сборник задач по дискретной математике. 2-е изд. М: Наука, 1992, 368 с iconТема: Общие сведения о гидросфере
Адров, Н. М. Наука о Земле : учеб пособие для студ ун-тов по направл. 020200 (510600) Биология и биологическим спец. / Адров Н. М.;...
Сборник задач по дискретной математике. 2-е изд. М: Наука, 1992, 368 с iconУчебник для вузов / Т. Г. Стефаненко. 4-е изд., испр и доп. М.: Аспект...
Этнопсихология: Учебник для вузов / Т. Г. Стефаненко. — 4-е изд., испр и доп. — М.: Аспект Пресс, 2009.— 368 с
Сборник задач по дискретной математике. 2-е изд. М: Наука, 1992, 368 с iconII. Однородные дифференциальные уравнения первого порядка
Клетеник Д. В. Сборник задач по аналитической геометрии. Спб., Изд-во «Профессия»,2002. (15 экз.)
Сборник задач по дискретной математике. 2-е изд. М: Наука, 1992, 368 с iconСборник задач по математике для втузов. В 4 частях. Ч /Под ред. А....
Московский государственный технический университет радиотехники, электроники и автоматики (мгту мирэа)
Сборник задач по дискретной математике. 2-е изд. М: Наука, 1992, 368 с icon«Кинология – наука о воспитании служебных собак»
Сборник заданий к типовому расчету по математической статистике: учебно-методическое пособие/ Л. А. Секованова, Т. А. Андревкина,...
Сборник задач по дискретной математике. 2-е изд. М: Наука, 1992, 368 с iconРабочая программа по математике составлена на основе Федерального...
В. Н. Рудницкой «Математика» (Образовательная система «Начальная школа XXI века». Сборник программ к комплекту учебников «Начальная...


Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
100-bal.ru
Поиск