Дискретная математика в примерах и задачах (Тишин В.В.)
Теория алгоритмов
189
Пример решения задания 3.2.3
Решить задание 3.2.3 для
,
z
,
y
,
x
f
)
(
вычисляемой нормальным
алгоритмом c данной. схемой подстановок:
1
11
1
1
.
1. Вначале мы имеем запись изображения набора аргументов
.
z
y
x
1
1
1
1
1
1
Запишем последовательность слов, получающих-
ся при работе данного нормального алгоритма над словом
:
1
1
1
1
1
1
z
y
x
,
z
y
x
1
1
1
1
1
1
,
z
y
x
1
1
1
1
1
,
z
y
x
1
1
1
1
1
1
,
z
y
x
1
1
1
1
2
1
,
…,
z
x
1
1
1
1
1
,
z
x
2
3
1
1
1
,…,
z
x
3
5
1
1
1
,
z
x
1
2
1
.
z
x
1
2
1
Итак, в результате работы нормального алгоритма над изо-
бражением набора аргументов получилось слово из
2
1
x
z
единиц, которое служит изображением числа
.
z
x 2
Значит, искомая функция имеет вид
.
2
)
(
z
x
z
,
y
,
x
f
2. Проверим работу алгоритма над изображением набора ар-
гументов (2,0,1):
,
11
1
111
,
1
1
111
,
1
111
,
11111
.
11111
В результате получено изображение числа 4.
Но
.
,
,
f
4
1
2
2
)
1
0
2
(
Так что нормальный алгоритм полу-
чил то, что и должен был получить.
3.3. Рекурсивные функции
Числовой функцией
0
0
:
N
N
f
n
,
где
}.
3
2
1
0
{
0
,…
,
,
,
N
Исходными функциями называются числовые функции сле-
дующих видов:
1)
0
)
(x
o
— нулевая функция;
2)
1
)
(
x
x
s
— функция следования;
3)
k
n
n
k
x
x
x
x
I
)
,…,
,
(
2
1
— функция выбора аргумента.
zinref.ru
Дискретная_математика_в_примерах_и_задачах
В. В. Тишин
Допущено учебно-методическимсоветом по прикладной математике
иинформатике УМО по классическому университетскому образованию
вкачестве учебного пособия для студентов высших учебных заведений, обучающихся по специальности и направлению «Прикладная математика
иинформатика» и по направлению «Информационные технологии»
Санкт-Петербург«БХВ-Петербург»
2008
УДК 681.3.06(075.8) ББК 32.973.26-018.2я73
Т47
Тишин В. В.
Т47 Дискретная математика в примерах и задачах. — СПб.: БХВПетербург, 2008. — 352 с.: ил. — (Учебная литература для вузов)
ISBN 978-5-9775-0232-0
Учебное пособие составлено на основании материалов лекционного курса, содержит краткую теорию, варианты заданий и примеры решения по следующим разделам дискретной математики: множества, декартовы произведения, соответствия, отношения, булевы функции, теория алгоритмов, предикаты, комбинаторика, конечные автоматы. Даны основные определения, необходимые для выполнения заданий. Для каждого типа задач предлагается по 30 вариантов заданий, приводится подробный образец решения.
Для преподавателей и студентов технических вузов и университетов, аспирантов, научных работников и инженеров
| УДК 681.3.06(075.8) |
| ББК 32.973.26-018.2я73 |
Группа подготовки издания: | |
Главный редактор | Екатерина Кондукова |
Зам. главного редактора | Татьяна Лапина |
Зав. редакцией | Григорий Добин |
Компьютерная верстка | Натальи Караваевой |
Корректор | Виктория Пиотровская |
Дизайн серии | Инны Тачиной |
Оформление обложки | Елены Беляевой |
Фото | Кирилла Сергеева |
Зав. производством | Николай Тверских |
Лицензия ИД № 02429 от 24.07.00. Подписано в печать 07.07.08.
Формат 60 901/16. Печать офсетная. Усл. печ. л. 22. Тираж 2500 экз. Заказ №
«БХВ-Петербург»,194354,Санкт-Петербург,ул. Есенина, 5Б.
Санитарно-эпидемиологическоезаключение на продукцию № 77.99.60.953.Д.003650.04.08 от 14.04.2008 г. выдано Федеральной службой
по надзору в сфере защиты прав потребителей и благополучия человека.
Отпечатано с готовых диапозитивов в ГУП «Типография «Наука»
199034, Санкт-Петербург,9 линия, 12
©Тишин В. В., 2008
©Оформление, издательство «БХВ-Петербург»,2008
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
IV | Оглавление |
Глава 5. Комбинаторика ……………………………………………………. | 211 |
5.1. Сочетания, размещения, перестановки …………………………… | 211 |
5.2. Бином Ньютона и полиномиальная формула ………………….. | 217 |
5.3. Формула включений и исключений………………………………… | 226 |
5.4. Задачи о распределениях ……………………………………………….. | 231 |
5.5. Арифметический треугольник ……………………………………….. | 235 |
5.6. Рекуррентные соотношения …………………………………………… | 243 |
Глава 6. Конечные автоматы…………………………………………….. | 255 |
6.1. Автоматы Мили …………………………………………………………….. | 255 |
6.2. Частичные автоматы ……………………………………………………… | 269 |
6.3. Реализация автоматов схемами ………………………………………. | 284 |
6.4. Распознавание множеств автоматами……………………………… | 300 |
Список литературы……………………………………………………………. | 337 |
Предисловие
Дискретная математика — одно из самых динамично развивающихся направлений современной математики, и тотальная компьютеризация всех областей нашей жизни приводит к постоянному росту спроса как на программистов, так и на специалистов, разрабатывающих математические основы компьютерных технологий.
Важным моментом усвоения математики и овладения еѐ методами является самостоятельная работа учащегося. Система индивидуальных заданий активизирует самостоятельную работу студентов и способствует более глубокому освоению курса и отработке приѐмов решения задач.
Всем, имеющим отношение к преподаванию дискретной математики, знакомы, ставшие классическими, задачники: “Задачи и упражнения по дискретной математике” Г. П. Гаврилова и А. А. Сапоженко, “Алгебра логики в задачах” С. Г. Гиндикина,
атакже “Задачи по теории множеств, математической логике и теории алгоритмов” И. А. Лаврова и Л. Л. Максимовой, но в настоящее время ощущается потребность в задачниках по дискретной математике, содержащих серии однотипных задач для выполнения студентами индивидуальных заданий.
Настоящий сборник отражает многолетний опыт работы автора, приобретѐнный им в Самарском государственном аэрокосмическом университете им. С. П. Королѐва при чтении лекций,
атакже при ведении практических занятий по курсам “Дискретная математика” и “Математическая логика и теория алгоритмов”.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
2 | Предисловие |
|
|
Система | индивидуальных заданий, практикуемая в СГАУ |
с 80-хгодов прошлого века, хорошо себя зарекомендовала. При проведении практических занятий студенты активно участвуют в решении и разборе задач, аналогичных тем, что им придѐтся выполнять индивидуально. Большинство разделов курса дискретной математики подкреплено и проиллюстрировано индивидуальными заданиями, и самостоятельное решение студентами задач помогает им лучше усвоить теорию и получить практические навыки работы с объектами, являющимися предметом изучения дискретной математики. Выполнение комплекса задач, вошедших в данное пособие, даѐт возможность студентам освоить базовые понятия дискретной математики, прочувствовать связи между ними и отработать приѐмы решения основных типов задач данного предмета.
Каждое задание даѐтся в 30 вариантах, и для каждого задания в сборнике приведѐн образец решения, что может помочь студентам внимательно разобрать предлагаемые способы решения задач и грамотно оформить выполненные индивидуальные задания.
Данное пособие может быть также полезно для вузов, практикующих заочную форму обучения, а также для всех энтузиастов, решивших изучить дискретную математику самостоятельно.
Пособие состоит из 6 глав:
Множества, графики, соответствия, отношения;
Булевы функции;
Теория алгоритмов;
Предикаты;
Комбинаторика;
Конечные автоматы.
Вначале каждой главы вводятся понятия, даются определения и формулировки теорем, используемых при выполнении заданий, что практически исключает необходимость привлечения дополнительной литературы по рассматриваемой тематике.
Некоторые задачи, вошедшие в пособие, возникли “тиражированием” идей, встречавшихся в классических задачниках по дискретной математике, другие — в процессе чтения автором курсов
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Предисловие | 3 |
|
|
“Дискретная математика”, “Основы дискретной математики”
и“Математическая логика и теория алгоритмов” в Самарском государственном аэрокосмическом университете им. С. П. Королѐва и общения со студентами.
Приношу благодарность всем, вдохновившим меня на этот труд: авторам, идеи которых получили развитие в данной книге,
исвоим студентам, чья заинтересованность и свежесть взгляда повлияли на материал, представленный в данном сборнике.
studfiles.net
Тишин В. В. Дискретная математика в примерах и..
Краткий отрывок из начала книги (машинное распознавание)
В. В. ТишинДискретная
математика
в примерах и задачах
Допущено учебно-методическим советом по прикладной математике
и информатике УМО по классическому университетскому образованию
в качестве учебного пособия для студентов высших учебных заведений,
обучающихся по специальности и направлению «Прикладная математика
и информатика» и по направлению «Информационные технологии»
Санкт-Петербург
«БХВ-Петербург»
2008
УДК 681.3.06(075.8)
ББК 32.973.26-018.2я73
Т47
Тишин В. В.
Т47 Дискретная математика в примерах и задачах. — СПб.:
БХВ-Петербург, 2008. — 352 с: ил. — (Учебная литература
для вузов)
ISBN 978-5-9775-0232-0
Учебное пособие составлено на основании материалов лекцион-
ного курса, содержит краткую теорию, варианты заданий и примеры
решения по следующим разделам дискретной математики: множества,
декартовы произведения, соответствия, отношения, булевы функции,
теория алгоритмов, предикаты, комбинаторика, конечные автоматы.
Даны основные определения, необходимые для выполнения заданий.
Для каждого типа задач предлагается по 30 вариантов заданий, приво-
дится подробный образец решения.
Для преподавателей и студентов технических вузов
и университетов, аспирантов, научных работников и инженеров
УДК 681.3.06(075.8)
ББК32.973.26-018.2я73
Группа подготовки издания:
Главный редактор Екатерина Кондукова
Зам. главного редактора Татьяна Лапина
Зав. редакцией Григорий Добин
Компьютерная верстка Натальи Караваевой
Корректор Виктория Пиотровская
Дизайн серии Инны Тачиной
Оформление обложки Елены Беляевой
Фото Кирилла Сергеева
Зав. производством Николай Тверских
Лицензия ИД № 02429 от 24.07.00. Подписано в печать 07.07.08.
Формат 60х901Лв. Печать офсетная. Усл. печ. л. 22.
Тираж 2500 экз. Заказ № 3332
«БХВ-Петербург», 194354, Санкт-Петербург, ул. Есенина, 5Б.
Санитарно-эпидемиологическое заключение на продукцию
№ 77.99.60.953.Д.003650.04.08 от 14.04.2008 г. выдано Федеральной службой
по надзору в сфере защиты прав потребителей и благополучия человека.
Отпечатано с готовых диапозитивов
в ГУП «Типография «Наука»
199034, Санкт-Петербург, 9 линия, 12
ISBN 978-5-9775-0232-0 © Тишин в. в., 2008
© Оформление, издательство «БХВ-Петербург», 2008
Оглавление
Предисловие 1
Глава 1. Множества, графики, соответствия, отношения 5
1.1. Операции над множествами 5
1.2. Графики 36
1.3. Соответствия 45
1.4. Отношения 60
Глава 2. Булевы функции 73
2.1. Булевы функции. Суперпозиции 73
2.2. Булевы функции и теория множеств 83
2.3. Нормальные формы и полиномы 93
2.4. Классы Поста 102
2.5. Минимизация нормальных форм всюду определённых
булевых функций 116
2.6. Частичные функции и схемы 126
Глава 3. Теория алгоритмов 163
3.1 Машины Тьюринга 163
3.2. Нормальные алгоритмы 179
3.3. Рекурсивные функции 189
Глава 4. Предикаты 197
4.1. Предикаты 197
IV Оглавление
Глава 5. Комбинаторика 211
5.1. Сочетания, размещения, перестановки 211
5.2. Бином Ньютона и полиномиальная формула 217
5.3. Формула включений и исключений 226
5.4. Задачи о распределениях 231
5.5. Арифметический треугольник 235
5.6. Рекуррентные соотношения 243
Глава 6. Конечные автоматы 255
6.1. Автоматы Мили 255
6.2. Частичные автоматы 269
6.3. Реализация автоматов схемами 284
6.4. Распознавание множеств автоматами 300
Список литературы 337
Предисловие
Дискретная математика — одно из самых динамично разви-
вающихся направлений современной математики, и тотальная
компьютеризация всех областей нашей жизни приводит к посто-
янному росту спроса как на программистов, так и на специали-
стов, разрабатывающих математические основы компьютерных
технологий.
Важным моментом усвоения математики и овладения её мето-
дами является самостоятельная работа учащегося. Система ин-
дивидуальных заданий активизирует самостоятельную работу
студентов и способствует более глубокому освоению курса и от-
работке приёмов решения задач.
Всем, имеющим отношение к преподаванию дискретной ма-
тематики, знакомы, ставшие классическими, задачники: «Зада-
чи и упражнения по дискретной математике» Г. П. Гаврилова
и А. А. Сапоженко, «Алгебра логики в задачах» С. Г. Гиндикина,
а также «Задачи по теории множеств, математической логи-
ке и теории алгоритмов» И. А. Лаврова и Л. Л. Максимовой, но
в настоящее время ощущается потребность в задачниках по дис-
кретной математике, содержащих серии однотипных задач для
выполнения студентами индивидуальных заданий.
Настоящий сборник отражает многолетний опыт работы авто-
ра, приобретённый им в Самарском государственном аэрокосми-
ческом университете им. С. П. Королёва при чтении лекций,
а также при ведении практических занятий по курсам «Диск-
ретная математика» и «Математическая логика и теория алго-
ритмов».
2
Предисловие
Система индивидуальных заданий, практикуемая в СГАУ
с 80-х годов прошлого века, хорошо себя зарекомендовала. При
проведении практических занятий студенты активно участвуют в
решении и разборе задач, аналогичных тем, что им придётся вы-
полнять индивидуально. Большинство разделов курса дискретной
математики подкреплено и проиллюстрировано индивидуальны-
ми заданиями, и самостоятельное решение студентами задач по-
могает им лучше усвоить теорию и получить практические навы-
ки работы с объектами, являющимися предметом изучения
дискретной математики. Выполнение комплекса задач, вошед-
ших в данное пособие, даёт возможность студентам освоить ба-
зовые понятия дискретной математики, прочувствовать связи
между ними и отработать приёмы решения основных типов задач
данного предмета.
Каждое задание даётся в 30 вариантах, и для каждого задания
в сборнике приведён образец решения, что может помочь студен-
там внимательно разобрать предлагаемые способы решения задач
и грамотно оформить выполненные индивидуальные задания.
Данное пособие может быть также полезно для вузов, практи-
кующих заочную форму обучения, а также для всех энтузиастов,
решивших изучить дискретную математику самостоятельно.
Пособие состоит из 6 глав:
□ Множества, графики, соответствия, отношения;
□ Булевы функции;
□ Теория алгоритмов;
□ Предикаты;
□ Комбинаторика;
□ Конечные автоматы.
В начале каждой главы вводятся понятия, даются определения
и формулировки теорем, используемых при выполнении заданий,
что практически исключает необходимость привлечения допол-
нительной литературы по рассматриваемой тематике.
Некоторые задачи, вошедшие в пособие, возникли «тиражиро-
ванием» идей, встречавшихся в классических задачниках по дис-
кретной математике, другие — в процессе чтения автором курсов
Предисловие
3
«Дискретная математика», «Основы дискретной математики»
и «Математическая логика и теория алгоритмов» в Самарском
государственном аэрокосмическом университете им. С. П. Ко-
ролёва и общения со студентами.
Приношу благодарность всем, вдохновившим меня на этот
труд: авторам, идеи которых получили развитие в данной книге,
и своим студентам, чья заинтересованность и свежесть взгляда
повлияли на материал, представленный в данном сборнике.
Глава 1
Множества, графики,
соответствия, отношения
1.1. Операции над множествами
Запись xg А означает, что элемент х принадлежит множест-
ву А. Если х не является элементом множеств А, то пишут
х$ А или хе А. Два множества А и В считаются равными, ес-
ли они состоят из одних и тех же элементов. Будем писать А = В,
если А и В равны и А * В в противном случае.
Множество называется пустым и обозначается 0, если оно не
содержит элементов.
Будем говорить, множество А включено в множество В, и пи-
сать Л с В, если каждый элемент множества А является элемен-
том множества В. В этом случае А называется подмножеством
множества В. Считается, что для любого А справедливо вклю-
чение 0 с Л.
Если ЛсВи А* В,то будем писать А а В и говорить, что
множество А строго включено во множество В.
Семейство всех подмножеств данного множества А обозна-
чается Р{А).
Мощностью конечного множества А будем называть число
его элементов. Мощность конечного множества А обозначает-
ся | А |.
Объединением множеств А и В называется множество
АиВ = {х\хеА или хеВ].
6
Глава ‘
Пересечением множеств Aw В называется множество
АпВ = {х\хе А и хеВ).
Разностью множеств А и В называется множество
А\В = {х\хе А и х£ В}.
Е
freedocs.xyz
Тишин В.В. Дискретная математика в примерах и задачах [PDF]
Учебное пособие. — Самара: СГАУ имени академика С.П.Королева, — 2007. — 326 с.Настоящий сборник отражает многолетний опыт работы автора, приобретённый им в Самарском государственном аэрокосмическом университете им. С.П. Королёва при чтении лекций, а также при ведении практических занятий по курсам «дискретная математика» и «математическая логика и теория алгоритмов».Система индивидуальных заданий, практикуемая в СГАУ с 80-х годов прошлого века, хорошо себя зарекомендовала. При проведении практических занятий студенты с большим вниманием следят и активно участвуют в решении и разборе задач, аналогичных тем, что им придётся выполнять индивидуально. Большинство разделов курса дискретной математики подкреплено и проиллюстрировано индивидуальными заданиями, и самостоятельное решение студентами задач помогает им лучше усвоить теорию и получить практические навыки работы с объектами, являющимися предметом изучения дискретной математики. Выполнение комплекса задач, вошедших в данное пособие, даёт возможность студентам освоить базовые понятия дискретной математики, прочувствовать связи между ними и отработать приёмы решения основных типов задач данного предмета.
Каждое задание даётся в 30 вариантах, и для каждого задания в сборнике приведён образец решения, что может помочь студентам внимательно разобрать предлагаемые способы решения задач и грамотно оформить выполненные индивидуальные задания.
Данное пособие может быть также полезно для вузов, практикующих заочную форму обучения, а также для всех энтузиастов, решивших изучить дискретную математику самостоятельно.Пособие состоит из 6 глав:
Множества, графики, соответствия, отношения;
Булевы функции;
Теория алгоритмов;
Предикаты;
Комбинаторика;
Конечные автоматы.В начале каждой главы вводятся понятия, даются определения и формулировки теорем, используемых при выполнении заданий, что практически исключает необходимость привлечения дополнительной литературы по рассматриваемой тематике.
www.twirpx.com
Дискретная математика в примерах и задачах / Тишин В. В. / 2008г — 25 Июня 2014
Аннотация: Тишин В. В. Дискретная математика в примерах и задачах. — СПб.: БХВ-Петербург, 2008. — 352 с: ил. — (Учебная литература для вузов)Учебное пособие составлено на основании материалов лекционного курса,
содержит краткую теорию, варианты заданий и примеры решения по
следующим разделам дискретной математики: множества, декартовы
произведения, соответствия, отношения, булевы функции, теория
алгоритмов, предикаты, комбинаторика, конечные автоматы.
Даны основные определения, необходимые для выполнения заданий. Для
каждого типа задач предлагается по 30 вариантов заданий, приводится
подробный образец решения.
Для преподавателей и студентов технических вузов и университетов, аспирантов, научных работников и инженеров
Оглавление
Предисловие…………………………………………………………………………1
Глава 1. Множества, графики, соответствия, отношения…..5
1.1. Операции над множествами……………………………………………..5
1.2. Графики…………………………………………………………………………36
1.3. Соответствия………………………………………………………………….45
1.4. Отношения…………………………………………………………………….60
Глава 2. Булевы функции…………………………………………………..73
2.1. Булевы функции. Суперпозиции…………………………………….73
2.2. Булевы функции и теория множеств……………………………….83
2.3. Нормальные формы и полиномы…………………………………….93
2.4. Классы Поста……………………………………………………………….102
2.5.
Минимизация нормальных форм всюду определённых булевых
функций……………………………………………………………….116
2.6. Частичные функции и схемы………………………………………..126
Глава 3. Теория алгоритмов…………………………………………….163
3.1 Машины Тьюринга……………………………………………………….163
3.2. Нормальные алгоритмы………………………………………………..179
3.3. Рекурсивные функции…………………………………………………..189
Глава 4. Предикаты………………………………………………………….197
4.1. Предикаты……………………………………………………………………197
Глава 5. Комбинаторика…………………………………………………..211
5.1. Сочетания, размещения, перестановки………………………….211
5.2. Бином Ньютона и полиномиальная формула…………………217
5.3. Формула включений и исключений………………………………226
5.4. Задачи о распределениях………………………………………………231
5.5. Арифметический треугольник………………………………………235
5.6. Рекуррентные соотношения………………………………………….243
Глава 6. Конечные автоматы…………………………………………..255
6.1. Автоматы Мили……………………………………………………………255
6.2. Частичные автоматы…………………………………………………….269
6.3. Реализация автоматов схемами……………………………………..284
6.4. Распознавание множеств автоматами……………………………300
Список литературы………………………………………………………….337
mirsmartbook.ru
Список литературыГенератор кроссвордовГенератор титульных листовТаблица истинности ONLINEПрочие ONLINE сервисы |
| В нашем каталогеОколостуденческоеЭто интересно…Наши контакты |
spisok-literaturi.ru
Задачи по дискретной математике (+ ответы и примеры решения) [RTF]
Методическое пособие — Сборник задач и упражнений по курсу Дискретная математика. В пособии приведена теория, примеры решения задач и задачи для самостоятельного решения по разделу «Элементы теории множеств и теории графов». Элементы теории множеств: Теоретико-множественные операции, Соответствия, Отображения, Отношения. Элементы теории графов.
- 641,09 КБ
- дата добавления неизвестна
- изменен
Составить таблицы истинности для формул,Записать формулы в ДНФ и СДНФ, Построить полином Жегалкина для функций,..
- 163,19 КБ
- дата добавления неизвестна
- изменен
2014 г. Элементы алгебры высказываний. Логические операции над высказываниями. Равносильные формулы алгебры высказываний. Нормальные формы. Логические следствия. Решение задач с помощью алгебры высказываний. Исследование рассуждений. Получение логических следствий из данных формул и посылок для данных логических следствий. Необходимые и достаточные условия. Анализ и…
- 308,60 КБ
- дата добавления неизвестна
- изменен
Решебник содержит подробное решение задач по основным темам математической логики в т. ч. способы решения логических задач типа «Кто есть кто? » методами графов, табличным способом, сопоставлением трех множеств; тактических, истинностных задач, на нахождение пересечения множеств или их объединения. Буквенные ребусы и примеры со звездочками.
- 621,56 КБ
- дата добавления неизвестна
- изменен
Архив содержит 10 вариантов.
- 389,16 КБ
- дата добавления неизвестна
- изменен
СПб.: БХВ-Петербург, 2008. — 352 с: ил. — (Учебная литература для вузов) — ISBN 978-5-9775-0232-0 Учебное пособие составлено на основании материалов лекционного курса, содержит краткую теорию, варианты заданий и примеры решения по следующим разделам дискретной математики: множества, декартовы произведения, соответствия, отношения, булевы функции, теория алгоритмов, предикаты,…
- 9,64 МБ
- дата добавления неизвестна
- изменен
www.twirpx.com