Иванов, А.Ю. Голубков, С.Ю. Скоробогатов СБОРНИК ЗАДАЧ ПО КУРСУ «ДИСКРЕТНАЯ МАТЕМАТИКА» Методические указания Москва Издательство МГТУ им. <...> Он посвящен изучению таких математических объектов, как графы и автоматы, способов их представления в памяти компьютера и алгоритмов для решения связанных с ними задач. <...> В отличие от курса алгоритмов, в котором для решения задач предлагается использовать язык C, курс дискретной математики рассчитан на применение языка Go, в котором автоматическое управление памятью сочетается с отсутствием жесткой объектной ориентации, характерной для языков Java и C#. <...> Домашнее задание по модулю «Программирование на языке Go» состоит из восьми задач, приведенных в разделе 1 данного сборника. <...> И, наконец, раздел 3 содержит восемь задач домашнего задания по модулю «Автоматы». <...> Быстрая сортировка Реализуйте алгоритм быстрой сортировки произвольных данных в функции func qsort(n int, less func(i, j int) bool, swap func(i, j int)) { . } <...> Параметрами функции qsort являются: n — число сортируемых записей, less — функция сравнения i-й и j-й записей; swap — функция обмена i-й и j-й записей. <...> Кодирование и раскодирование текста в кодировке UTF-8 Реализуйте алгоритмы перевода текста из кодировки UTF-32 в UTF-8 и обратно. <...> Параметром функции encode служит текст в виде массива кодовых точек, функция возвращает образ этого текста в кодировке 4 UTF-8. <...> Правила кодирования текста в кодировке UTF-8 приведены в табл. <...> Вычисление выражений в польской записи Польская запись — это форма записи арифметических, логических и алгебраических выражений, в которой операция располагается слева от операндов. <...> Выражения в польской записи могут обходиться без скобок, однако мы оставим скобки для наглядности. <...> Например, выражение 5 · (3+4) в польской записи выглядит как (*5(+34)) Пусть в нашем случае выражения состоят из чисел от 0 до 9, круглых скобок и трех знаков операций: плюс, минус и звездочка (умножить). <...> Экономное вычисление выражений в польской записи Пусть выражения в польской <...>
Сборник_задач_по_курсу_«Дискретная_математика».pdf
УДК 519
ББК 22.176
И20
Рецензент П.Г. Ключар¨
И20
ев
Иванов И.П.
Сборник задач по курсу «Дискретная математика» : метод.
указания / И.П. Иванов, А.Ю. Голубков, С.Ю. Скоробогатов.
— М. : Изд-во МГТУ им. Н.Э. Баумана, 2013. — 31, [1] с. :
ил.
ISBN 978-5-7038-3682-8
Приведены задачи по курсу «Дискретная математика», относящиеся
к теории графов и теории автоматов.
Для студентов, обучающихся по направлению подготовки бакалавров
«Прикладная математика и информатика».
Рекомендовано методической комиссией факультета «Информатика
и системы управления» МГТУ им. Н.Э. Баумана.
УДК 519
ББК 22.176
Учебное издание
Иванов Игорь Потапович
Голубков АртемЮрьевич
Скоробогатов Сергей Юрьевич
СБОРНИК ЗАДАЧ ПО КУРСУ
«ДИСКРЕТНАЯ МАТЕМАТИКА»
Редактор С.А. Серебрякова
Корректор Р.В. Царева
Компьютерная верстка В.И. Товстоног
Подписано в печать 08.05.2013. Формат 60×84/16.
Усл. печ. л. 1,86. Тираж 100 экз. Изд. № 49.
Заказ
Издательство МГТУ им. Н.Э. Баумана.
Типография МГТУ им. Н.Э. Баумана.
ISBN 978-5-7038-3682-8
105005, Москва, 2-я Бауманская ул., д. 5, стр. 1.
c
МГТУ им. Н.Э. Баумана, 2013
Стр.2
ОГЛАВЛЕНИЕ
1. ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ GO . . .................... 4
1.1. Быстрая сортировка ....................................... 4
1.2. Кодирование и раскодирование текста в кодировке UTF-8 . . 4
1.3. «Длинное» сложение ...................................... 5
1.4. Решение систем линейных алгебраических уравнений
в рациональных числах .................................. 5
1.5. Вычисление выражений в польской записи . . . ............. 6
1.6. Экономное вычисление выражений в польской записи . . . . . 6
1.7. Лексический анализ ....................................... 7
1.8. Арифметическое выражение. .............................. 8
2. ГРАФЫ........................................................ 11
2.1. Граф делителей ........................................... 11
2.2. Подготовка экспедиции на Марс........................... 11
2.3. Компоненты связности .................................... 12
2.4. Прямой порядок вершин . ................................. 13
2.5. Маршрут, содержащий все ребра мультиграфа ............. 14
2.6. Дорожки в парке .......................................... 15
2.7. Телефонные линии........................................ 15
2.8. Компоненты сильной связности ........................... 16
2.9. Конденсация орграфа ..................................... 17
2.10. База орграфа............................................. 18
2.11. Минимальный путь на карте ............................. 19
2.12. Идеальный путь в лабиринте ............................. 20
3. АВТОМАТЫ.................................................. 21
3.1. Визуализация автомата Мили.............................. 21
31
Стр.31
3.2. Язык автомата Мили . . . ................................... 22
3.3. Минимизация автомата Мили . . ........................... 23
3.4. Преобразование автомата Мили в автомат Мура............ 25
3.5. Визуализация распознающего автомата . . . ................. 26
3.6. Минимизация распознающего автомата .................... 27
3.7. Визуализация недетерминированного распознающего
автомата ................................................. 28
3.8. Детерминизация распознающего автомата ................. 29
Стр.32