Сборник задач по курсу «Дискретная математика»

Московский государственный технический университет
имени Н.Э. Баумана
И.П. Иванов, А.Ю. Голубков,
С.Ю. Скоробогатов
СБОРНИК ЗАДА
Ч ПО КУРСУ
«ДИСКРЕТНАЯ МАТЕМАТИКА»
Методические указания
Москва
Издательство МГТУ им. Н.Э. Баумана
2013

УДК 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.
Заказ
Издательство МГТУ им. Н.Э. Баумана.
Типография МГТУ им. Н.Э. Баумана.
105005, Москва, 2-я Бауманская ул., д. 5, стр. 1.
ISBN 978-5-7038-3682-8
c
⃝МГТУ им. Н.Э. Баумана, 2013

ВВЕДЕНИЕ
Курс «Дискретная математика» является логическим продолжением курса «Алгоритмы и структуры данных». Он посвящен
изучению таких математических объектов, как графы и автоматы,
способов их представления в памяти компьютера и алгоритмов для
решения связанных с ними задач.
В отличие от курса алгоритмов, в котором для решения задач предлагается использовать язык C, курс дискретной математики рассчитан на применение языка Go, в котором автоматическое
управление памятью сочетается с отсутствием жесткой объектной
ориентации, характерной для языков Java и C#.
Сборник содержит 28 задач, в которых рассмотрена б´
ольшая
часть алгоритмов, изучаемых в курсе «Дискретная математика».
Курс разбит на три модуля. Домашнее задание по модулю
«Программирование на языке Go» состоит из восьми задач, приведенных в разделе 1 данного сборника. Раздел 2 состоит из 12 задач,
которые нужно решить в модуле «Графы». И, наконец, раздел 3 содержит восемь задач домашнего задания по модулю «Автоматы».

1. ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ GO
1.1. Быстрая сортировка
Реализуйте алгоритм быстрой сортировки произвольных данных в функции
func qsort(n int,
less func(i, j int) bool,
swap func(i, j int)) {
...
}
Параметрами функции qsort являются:
n — число сортируемых записей,
less — функция сравнения i-й и j-й записей;
swap — функция обмена i-й и j-й записей.
Составьте программу qsort.go, демонстрирующую работоспособность функцию qsort.
1.2. Кодирование и раскодирование текста в кодировке UTF-8
Реализуйте алгоритмы перевода текста из кодировки UTF-32
в UTF-8 и обратно. Алгоритмы должны быть оформлены в виде
двух функций:
func encode(utf32 []rune) []byte {
...
}
func decode(utf8 []byte) []rune {
...
}
Параметром функции encode служит текст в виде массива кодовых точек, функция возвращает образ этого текста в кодировке
4