Дискретная математика. Ориентированные и неориентированные графы. Способы задания графов. Цепи. Циклы. Связность. Деревья. Пространство циклов графа. Кратчайшие пути и цепи. Элементы теории кодирования. Алфавитное кодирование. Оптимальное кодирование. Коды с обнаружением и исправлением ошибок

Решение задач и выполнение научно-исследовательских разработок: Отправьте запрос сейчас: irina@bodrenko.org    
математика, IT, информатика, программирование, статистика, биостатистика, экономика, психология
Пришлите по e-mail: irina@bodrenko.org описание вашего задания, срок выполнения, стоимость



 Компьютерные науки Математика и информатика Векторный и тензорный анализ Теория игр Аналитическая геометрия и линейная алгебра Дифференциальная геометрия и топология Дополнительные главы дифференциальной геометрии Bodrenko.com Bodrenko.org

Bodrenko.com
Bodrenko.org

Учебные дисциплины на сайте Bodrenko.org
Портабельные Windows-приложения на сайте Bodrenko.com
"Геометрические методы математической физики" Компьютерные науки Математика и информатика Векторный и тензорный анализ Теория игр Аналитическая геометрия и линейная алгебра Римановы многообразия Элементы вариационного исцисления Дифференциальная геометрия и топология "Геометрия подмногообразий" Дополнительные главы дифференциальной геометрии "Диффиренциальные уравнения на многообразиях" "Дифференциальная геометрия и топология кривых" Bodrenko.com Bodrenko.org

Bodrenko.org

 

Кафедра

                 Бодренко Андрей Иванович, кандидат физико-математических наук, доцент  

Ф.И.О., ученая степень, ученое звание  автора

 

 

 

 

 

Учебно-методический комплекс по дисциплине

 

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

                                                                                            (название)        

 

Специальность: 010503 Математическое обеспечение и администрирование информационных сетей, 230100 Информатика и вычислительная техника,      230102 Автоматизированные системы обработки информации и управления,           230201 Информационные системы и технологии

 

 

 

Утверждено

Рекомендовано

Ученым советом факультета

Протокол №_

«____»_____________ 200_г.

кафедрой  ______________________

Протокол №_

«____»____________ 200_г.

Декан факультета__________

Зав. кафедрой____________________

 

Волгоград 2009 г.

 

 

 

Автор-составитель:

Ф.и.о., ученая степень, ученое звание, должность

Бодренко Андрей Иванович, кандидат физико-математических наук, доцент, доцент кафедры

Учебно-методический комплекс__ Дискретная математика               

                                             

составлен в соответствии с требованиями Государственного образовательного стандарта высшего профессионального образования по специальности: 010503 Математическое обеспечение и администрирование информационных сетей, 230100 Информатика и вычислительная техника, 230102 Автоматизированные системы обработки информации и управления, 230201 Информационные системы и технологии.

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

 

 

__________________________________________________________________________

 

 

 

 

 

 


 

СОДЕРЖАНИЕ

 

 

Стр.

 

1.     Рабочая программа учебной дисциплины

4

 

2.     Методические рекомендации по изучению дисциплины для студентов

2.1.         Советы по планированию и организации времени, необходимого на изучение дисциплины.

2.2.         Описание последовательности действий студента по изучению дисциплины.

2.3.         Рекомендации по использованию материалов учебно-методического комплекса и по работе     с литературой.

2.4.         Советы по подготовке к экзамену и разъяснения по поводу работы с тестовой системой курса, по выполнению домашних заданий.

10            

 

11

 

 

11

 

 

 

12

 

 

13

 

3.     Учебно-методические материалы (УММ)

3.1.         Лекции

3.2.         Практические занятия: план проведения занятий; списки типовых задач по каждой теме, рекомендуемые сборники задач по каждой теме.

3.3.         Методические указания для преподавателей, ведущих практические занятия.

4.     Словарь терминов

5.     Формы текущего, промежуточного, рубежного и итогового контроля:

5.1.         Контрольные вопросы по каждой теме.

5.2.         Варианты контрольных работ, тесты.

13

13

 

 

14

 

15

16

 

16

16

17

 

6.     Балльно-рейтинговая система оценки успеваемости студентов по дисциплине

29

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рабочая программа учебной дисциплины

 

I. Аннотация.

Рабочая программа составлена на основании государственного образовательного стандарта высшего профессионального образования по курсу "Дискретная математика" и учебного плана по специальности "МОАИС","МОАИС-спо", "ИВТ", "ИСТ ", "АСОИУ "


I.1. ЦЕЛЬ ПРЕПОДАВАНИЯ ДИСЦИПЛИНЫ. Курс "Дискретная математика" входит в состав общих математических и естественнонаучных дисциплин, изучаемых на математическом факультете университета и, в соответствии с положениями Государственного Образовательного Стандарта Высшего профессионального образования по специальностям "МОАИС","МОАИС-спо", "ИВТ", "ИСТ ", "АСОИУ " направлен на формирование представлений и навыков работы с математическими объектами, которые составляют основу инвариантного математического аппарата. Преподавание курса "Дискретная математика" имеет целью формирование у студентов правильных представлений об основных понятиях логики, изучение процессов формализации рассуждений и применение полученных знаний в работе с ЭВМ.
1.2. ЗАДАЧИ ИЗУЧЕНИЯ ДИСЦИПЛИНЫ. Студент должен знать понятие булевой алгебры; понятие дизъюнктивной нормальной формы; понятие полинома Жегалкина; понятие полной системы функций; понятия операции суперпозиции и подстановки; понятие замкнутой системы булевых функций; теорему Поста о полноте системы булевых функций; основные комбинаторные конфигурации и их число; простейшие сведения из теории групп. Студент должен уметь применять на практике основные определения алгебры, математического анализа, демонстрируя это при решении задач. Разбираться в доказательствах основных теорем курса.
1.3. ВЗАИМОСВЯЗЬ УЧЕБНЫХ ДИСЦИПЛИН. Понятия дискретной математики основываются на знаниях алгебры, математического анализа, составляют базис аппарата формализации математических рассуждений. Методы дискретной математики применяются математической экономике, вычислительной математике и математической кибернетике.

Методика формирования результирующей оценки:
Выполнение каждой письменной контрольной работы оценивается от 0 до 12 баллов.
Выполнение студентом заданий на каждом практическом занятии оценивается от 0 до 4 баллов.
Рейтинговая оценка работы студента в семестре равна сумме баллов за 3 контрольные работы и практические занятия, и может достичь 72 баллов. Студент, набравший в результате текущего семестрового контроля менее 20 баллов, к зачету не допускается; ему выставляется итоговая пятибалльная оценка "неудовлетворительно".
Зачет по дисциплине проводится в письменном виде. Зачетный билет содержит 5 пунктов, содержащих как теоретические вопросы, так и задачи. Ответ студента на каждый пункт билета оценивается от 0 до 8 баллов.
Итоговая рейтинговая оценка знаний студента равна сумме баллов, полученных в течение семестра за выполнение контрольных работ, и до 40 баллов, полученных за письменную экзаменационную работу в конце семестра (но не более 100 баллов).
Итоговая пятибалльная оценка по дисциплине определяется в соответствии со следующей схемой: если количество баллов не меньше 91, то выставляется оценка "отлично", иначе, если количество баллов не меньше 71, то выставляется оценка "хорошо", иначе, если количество баллов не меньше 60, то выставляется оценка "удовлетворительно".

В семестре студенты сдают зачет. Для получения зачета необходимо получить семестровую оценку не ниже "удовлетворительно".



II. CОДЕРЖАНИЕ УЧЕБНОЙ ДИСЦИПЛИНЫ.


1. Объем дисциплины и виды учебной работы.

N п/п

Вид учебной работы

Всего часов

1.

Аудиторные занятия (всего)

54

1.1

Лекции

36

1.2.

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

18

2.

Самостоятельная работа (всего)

12

3.

Общая трудоемкость дисциплины

84

4.

Вид итогового контроля

Экзамен



2. Тематический план дисциплины.

Номер темы

Тематика лекций и практических занятий

Лекции(часов)

Практ. занятия (часов)

1.

Функциональные соответствия и отношения.

2

2

2.

Булевы функции.

10

4

3.

Логика предикатов.

4

2

4.

Элементы комбинаторики.

4

2

5.

Графы и сети.

8

4

6.

Элементы теории кодирования.

4

2

7.

Алгоритмы и формальные системы.

4

2

 

Всего часов

36

18



3. Содержание лекций и практических занятий.

3.1. Содержание лекций.

Номер

 

Объем,

лекции

Тема лекции

час

 

 

 

1

2

3

Тема 1.

Функциональные соответствия и отношения.

2

1.

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

 

2.

Суперпозиция функций.

 

3.

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

 

4.

Свойства бинарных операций.

 

5.

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

 

6.

Отношения эквивалентности.

 

7.

Отношения порядка.

 

8.

Операции над двоичными числами.

 

Тема 2.

Булевы функции.

10

1.

Булевы функции и их свойства.

 

2.

Представление булевой функции в виде ДНФ.

 

3.

Представление булевой функции в виде КНФ.

 

4.

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

 

5.

Замыкание системы булевых функций.

 

6.

Основные классы булевых функций и их замкнутость.

 

Тема 3.

Логика предикатов.

4

1.

Операции над предикатами.

 

2.

Предикатные формулы. Тавтологии.

 

Тема 4.

Элементы комбинаторики.

4

1.

Основные комбинаторные конфигурации.

 

2.

Формулы пересчета числа комбинаторных конфигураций.

 

Тема 5.

Графы и сети.

8

1.

Ориентированные и неориентированные графы. Способы задания графов.

 

2.

Цепи. Циклы. Связность.

 

3.

Деревья.

 

4.

Пространство циклов графа.

 

5.

Кратчайшие пути и цепи.

 

Тема 6.

Элементы теории кодирования.

4

1.

Алфавитное кодирование.

 

2.

Оптимальное кодирование.

 

3.

Коды с обнаружением и исправлением ошибок.

 

Тема 7.

Алгоритмы и формальные системы.

4

1.

Алгоритмическая процедура.

 

2.

Машины Тьюринга.

 

3.

Понятие формальной грамматики.

 




3.2. Содержание практических занятий.

Номер

 

Объем,

практической

Наименование практической работы

час

работы

 

 

1

2

3

Тема 1.

Функциональные соответствия и отношения.

2

1.

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

 

2.

Суперпозиция функций.

 

3.

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

 

4.

Свойства бинарных операций.

 

5.

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

 

6.

Отношения эквивалентности.

 

7.

Отношения порядка.

 

8.

Операции над двоичными числами.

 

Тема 2.

Булевы функции.

4

1.

Булевы функции и их свойства.

 

2.

Представление булевой функции в виде ДНФ.

 

3.

Представление булевой функции в виде КНФ.

 

4.

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

 

5.

Замыкание системы булевых функций.

 

6.

Основные классы булевых функций и их замкнутость.

 

Тема 3.

Логика предикатов.

2

1.

Операции над предикатами.

 

2.

Предикатные формулы. Тавтологии.

 

Тема 4.

Элементы комбинаторики.

2

1.

Основные комбинаторные конфигурации.

 

2.

Формулы пересчета числа комбинаторных конфигураций.

 

Тема 5.

Графы и сети.

4

1.

Ориентированные и неориентированные графы. Способы задания графов.

 

2.

Цепи. Циклы. Связность.

 

3.

Деревья.

 

4.

Пространство циклов графа.

 

5.

Кратчайшие пути и цепи.

 

Тема 6.

Элементы теории кодирования.

2

1.

Алфавитное кодирование.

 

2.

Оптимальное кодирование.

 

3.

Коды с обнаружением и исправлением ошибок.

 

Тема 7.

Алгоритмы и формальные системы.

2

1.

Алгоритмическая процедура.

 

2.

Машины Тьюринга.

 

3.

Понятие формальной грамматики.

 

 

 

План практических занятий по курсу “Дискретная математика”

[1] Гаврилов Г. П., Сапоженко А.А. "Сборник задач по дискретной математике". - М. 1977.

[2] Джеймс Андерсон.  “Дискретная математика и комбинаторика”.-М.  Издательство “Вильямс” 2004

Тема 1. Функциональные соответствия и отношения. [2] стр.67-112;    (1-2-ая неделя)                                                             1. Операции над множествами.
2. Суперпозиция функций.
3. Операции на множестве.
4. Свойства бинарных операций.
5. Бинарные отношения.   
6. Отношения эквивалентности.
7. Отношения порядка.
8. Операции над двоичными числами.

 Задачи  из [2]: 1-17 (стр. 70); 1-15 (стр. 75-76); 1-8 (стр. 82-84); 1-12 (стр. 97-98);                                                          1-2(стр.105 ); 1-9 (стр. 111-112);  

Тема 2. Булевы функции. [1] стр. 9-76; (3-7-ая неделя)                                                            
1. Булевы функции и их свойства.
2. Представление булевой функции в виде ДНФ.
3. Представление булевой функции в виде КНФ.
4. Представление булевой функции в виде полинома Жегалкина.
5. Замыкание системы булевых функций.
6. Основные классы булевых функций и их замкнутость.

Задачи из [1]: 2.16-2.31,3.1-3.33, 5.1-5.24 (стр. 9-49); 1.1-1.25, 2.1-2.29, 3.1-3.33, 4.1-4.23, 5.1-5.55, 6.1-6.33 (стр. 50-76);


Тема 3. Элементы комбинаторики. [1] стр. 249-280; [2] стр. 322-363; (8-11-ая неделя)                                                            
1. Основные комбинаторные конфигурации.
2. Формулы пересчета числа комбинаторных конфигураций.

Задачи из [1]: 1.1-1.24, 2.1-2.9 (стр. 249-280);                                                                                                        Задачи из [2]:  1-27 (стр. 322-323), 1-20 (стр. 329-330), 1-36 (стр. 341-343), 1-24 (стр. 346),                     1-12 (стр. 363);


Тема 4. Графы и сети. [1] стр. 101-158; [2] стр. 322-363; (12-14-ая неделя)                                                            
1. Ориентированные и неориентированные графы. Способы задания графов.
2. Цепи. Циклы. Связность.
3. Деревья.
4. Пространство циклов графа.
5. Кратчайшие пути и цепи.

Задачи из [1]: 1.1-1.44, 2.1-2.51, 3.1-3.33, 4.1-4.58 (стр. 101-158);                                                                                                        Задачи из [2]:  1-8 (стр. 251-252), 1-12 (стр. 256-259), 1-11 (стр. 264-267), 1-12 (стр. 273-277),                     1-29 (стр. 285-289);


Тема 5. Элементы теории кодирования. [1] стр. 159-177; [2] стр. 322-363; (15-16-ая неделя)                                                            
1. Алфавитное кодирование.
2. Оптимальное кодирование.
3. Коды с обнаружением и исправлением ошибок.

Задачи из [1]: 1.1-1.28, 2.1-2.25, 3.1-3.31 (стр. 159-177);                                                                                                        Задачи из [2]:  1-13 (стр. 765-766), 1-13 (стр. 773-774), 1-11 (стр. 264-267), 1-12 (стр. 273-277),                     1-29 (стр. 285-289);


Тема 6. Алгоритмы и формальные системы. [1] стр. 213-248; (17-18-ая неделя)                                                            
1. Алгоритмическая процедура.
2. Машины Тьюринга.
3. Понятие формальной грамматики.
Задачи из [1]: 1.1-1.26, 2.1-2.25, 3.1-3.31 (стр. 213-248);  



III. Программа экзамена.


Тема 1. Функциональные соответствия и отношения.
1. Операции над множествами.
2. Суперпозиция функций.
3. Операции на множестве.
4. Свойства бинарных операций.
5. Бинарные отношeния.
6. Отношения эквивалентности.
7. Отношения порядка.
8. Операции над двоичными числами.
Тема 2. Булевы функции.
1. Булевы функции и их свойства.
2. Представление булевой функции в виде ДНФ.
3. Представление булевой функции в виде КНФ.
4. Представление булевой функции в виде полинома Жегалкина.
5. Замыкание системы булевых функций.
6. Основные классы булевых функций и их замкнутость.
Тема 3. Логика предикатов.
1. Операции над предикатами.
2. Предикатные формулы. Тавтологии.
Тема 4. Элементы комбинаторики.
1. Основные комбинаторные конфигурации.
2. Формулы пересчета числа комбинаторных конфигураций.
Тема 5. Графы и сети.
1. Ориентированные и неориентированные графы. Способы задания графов.
2. Цепи. Циклы. Связность.
3. Деревья.
4. Пространство циклов графа.
5. Кратчайшие пути и цепи.
Тема 6. Элементы теории кодирования.
1. Алфавитное кодирование.
2. Оптимальное кодирование.
3. Коды с обнаружением и исправлением ошибок.
Тема 7. Алгоритмы и формальные системы.
1. Алгоритмическая процедура.
2. Машины Тьюринга.
3. Понятие формальной грамматики.



IV. Учебно-методическое обеспечение.
Лекции и практические занятия в основном рассчитаны на применение учебных пособий [1-6], методических рекомендаций [1-3], и электронных методических рекомендаций [1].
Наш вариант изложения дисциплины имеет своей целью удобство ее приложений в других дисциплинах курса обучения. Другие варианты изложения и дополнительные результаты могут быть получены студентами из книг, приведенных в списке литературы.
В лекциях обсуждаются решения всех задач, включаемых в контрольные работы и экзаменационные билеты.

В течение семестра на практических занятиях проводится 3 контрольные работы. Расчетная продолжительность каждой контрольной работы не превышает 2 часа. Задания для контрольных работ (без разбиения на варианты) содержатся в электронных методических указаниях [1] и также доступны студентам без ограничений.

V. ЛИТЕРАТУРА.

V.1. ЛИТЕРАТУРА.

1. Яблонский С.В. Введение в дискретную математику. М., 1987.
2. Верещагин Н.К, Шень А. Языки и исчисления. М.: МЦНМО, 2000.
3. Журавлев Ю.И. Проблемы кибернетики. М.1962. ')
4. Лупанов О.Б. Проблемы кибернетики. М., 1965.
5. Яблонский С.В., Гаврилов Г.П., Кудрявцев В.Б. Функции алгебры логики и классы Поста. М.: Наука, 1966.
6. Гаврилов Г. П., Сапоженко А.А. "Сборник задач по дискретной математике". - М. 1989.
7. Харари Ф. Теория графов. М.: Наука, 1982.
8. Патерсон У., Уэлдон Э. Коды исправляющие ошибки. М.: Мир, 1976.
9. Трахтенброт Б.А., Барздинь Я.М. Конечные автоматы. М.: Наука, 1970.
10. Верещагин Н.К., Шень А. Вычислимые функции. М.: МЦНМО, 1999.

V.2. МЕТОДИЧЕСКИЕ УКАЗАНИЯ

1. Фонд контрольных заданий по курсу "Дискретная математика ". (Электронные методические указания. Составитель -- Бодренко А.И.)
2. Программа экзамена по курсу "Дискретная математика ". (Электронные методические указания. Составитель -- Бодренко А.И.)
3. Программа зачета по курсу "Дискретная математика ". (Электронные методические указания. Составитель -- Бодренко А.И.)



Программа учебной дисциплины утверждена сроком на 4 года

на заседании кафедры
20 августа 2008 г., протокол N 1.

Заведующий кафедрой ______________________


2. Методические рекомендации по изучению дисциплины для студентов

    • Советы по планированию и организации времени, необходимого на изучение дисциплины;
    • Описание последовательности действий студента, или «сценарий изучения дисциплины»;
    • Рекомендации по использованию материалов учебно-методического комплекса;
    • Рекомендации по работе с литературой;
    • Советы по подготовке к экзамену (зачету);

 

                   Курс "Дискретная математика" входит в состав общих математических и естественнонаучных дисциплин, изучаемых на математическом факультете университета и, в соответствии с положениями Государственного Образовательного Стандарта Высшего профессионального образования по специальностям "МОАИС","МОАИС-спо", "ИВТ", "ИСТ ", "АСОИУ " направлен на формирование представлений и навыков работы с математическими объектами, которые составляют основу инвариантного математического аппарата. Преподавание курса "Дискретная математика" имеет целью формирование у студентов правильных представлений об основных понятиях логики, изучение процессов формализации рассуждений и применение полученных знаний в работе с ЭВМ.
                     Студент должен знать понятие булевой алгебры; понятие дизъюнктивной нормальной формы; понятие полинома Жегалкина; понятие полной системы функций; понятия операции суперпозиции и подстановки; понятие замкнутой системы булевых функций; теорему Поста о полноте системы булевых функций; основные комбинаторные конфигурации и их число; простейшие сведения из теории групп. Студент должен уметь применять на практике основные определения алгебры, математического анализа, демонстрируя это при решении задач. Разбираться в доказательствах основных теорем курса.
                     Понятия дискретной математики основываются на знаниях алгебры, математического анализа, составляют базис аппарата формализации математических рассуждений. Методы дискретной математики применяются математической экономике, вычислительной математике и математической кибернетике.

2.1.  Советы по планированию и организации времени, необходимого для изучения дисциплины.

При изучении дисциплины «Дискретная математика» необходимо работать с теоретическим материалом, излагаемым на лекциях, решать задачи на практических занятиях, систематически и последовательно на протяжении всего семестра.  Планирование и организация времени, необходимого для изучения дисциплины «Дискретная математика», должны проводиться в соответствии с  установленными объемом и видами учебной работы.

Разъяснения по поводу работы с тестовой системой курса, по выполнению домашних заданий.

 

Лекции и практические занятия в основном рассчитаны на применение учебных пособий [1-2], методических рекомендаций [1-3], и электронных методических рекомендаций [1].
Наш вариант изложения дисциплины имеет своей целью удобство ее приложений в других дисциплинах курса обучения. Другие варианты изложения и дополнительные результаты могут быть получены студентами из книг, приведенных в списке литературы.
В лекциях обсуждаются решения всех задач, включаемых в контрольные работы и экзаменационные билеты.

В течение семестра на практических занятиях проводится 3 контрольные работы. Расчетная продолжительность каждой контрольной работы не превышает 2 часа. Задания для контрольных работ (без разбиения на варианты) содержатся в электронных методических указаниях [1] и также доступны студентам без ограничений.

 

2.2. Описание последовательности действия студента при  изучении дисциплины.

Изучение дисциплины «Дискретная математика» проводится в соответствии со следующим тематическим планом.

            Тематический план изучения дисциплины «Дискретная математика».

Номер темы

Тематика лекций и практических занятий

Лекции(часов)

Практ. занятия (часов)

1.

Функциональные соответствия и отношения.

2

2

2.

Булевы функции.

10

4

3.

Логика предикатов.

4

2

4.

Элементы комбинаторики.

4

2

5.

Графы и сети.

8

4

6.

Элементы теории кодирования.

4

2

7.

Алгоритмы и формальные системы.

4

2

 

Всего часов

36

18

 

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

 
2. 3.  Рекомендации по использованию материалов учебно-методического комплекса и по работе с литературой.

Лекции и практические занятия в основном рассчитаны на применение учебных пособий [1-3], методических рекомендаций [1-3], и электронных методических рекомендаций [1]. Наш вариант изложения дисциплины имеет своей целью удобство ее приложений в других дисциплинах курса обучения. Другие варианты изложения и дополнительные результаты могут быть получены студентами из книг, приведенных в списке литературы.  На лекциях обсуждаются решения всех задач, включаемых в контрольные работы и экзаменационные билеты.  В течение каждого семестра на занятиях проводятся 3 контрольные работы. Расчетная продолжительность каждой контрольной работы не превышает 2 часа. Задания для контрольных работ (без разбиения на варианты) содержатся в электронных методических указаниях [1] и также доступны студентам без ограничений.
               Материалы учебно-методического комплекса целесообразно использовать в течение всего периода изучения дисциплины. Изучение теоретических вопросов, излагаемых на лекциях, необходимо сопровождать изучением соответствующих разделов в предлагаемой литературе. Необходимый минимум теоретического материала и типовые задачи по изучаемым в дисциплине «
Дискретная математика» вопросам содержатся в следующих учебниках и сборниках задач. 

 

1. Яблонский С.В. Введение в дискретную математику. М., 1987.
2. Верещагин Н.К, Шень А. Языки и исчисления. М.: МЦНМО, 2000.
3. Журавлев Ю.И. Проблемы кибернетики. М.1962. ')
4. Лупанов О.Б. Проблемы кибернетики. М., 1965.
5. Яблонский С.В., Гаврилов Г.П., Кудрявцев В.Б. Функции алгебры логики и классы Поста. М.: Наука, 1966.
6. Гаврилов Г. П., Сапоженко А.А. "Сборник задач по дискретной математике". - М. 1989.
7. Харари Ф. Теория графов. М.: Наука, 1982.
8. Патерсон У., Уэлдон Э. Коды исправляющие ошибки. М.: Мир, 1976.
9. Трахтенброт Б.А., Барздинь Я.М. Конечные автоматы. М.: Наука, 1970.
10. Верещагин Н.К., Шень А. Вычислимые функции. М.: МЦНМО, 1999.

При подготовке к контрольным работам и экзамену целесообразно также использовать  следующие  учебно-методические материалы.


1. Фонд контрольных заданий по курсу "Дискретная математика ". (Электронные методические указания. Составитель -- Бодренко А.И.)
2. Программа экзамена по курсу "Дискретная математика ". (Электронные методические указания. Составитель -- Бодренко А.И.)
3. Программа зачета по курсу "Дискретная математика ". (Электронные методические указания. Составитель -- Бодренко А.И.)

2. 4.  Советы по подготовке к экзамену  и разъяснения по поводу работы с тестовой системой курса, по выполнению домашних заданий.

 

В течение каждого семестра на занятиях проводятся 3 контрольные работы. Расчетная продолжительность каждой контрольной работы не превышает 2 часа. Задания для контрольных работ (без разбиения на варианты) содержатся в электронных методических указаниях [1] и также доступны студентам без ограничений.
Выполнение каждой письменной контрольной работы оценивается от 0 до 12 баллов. Выполнение студентом заданий на каждом практическом занятии оценивается от 0 до 2 баллов.  Домашние задания следует выполнять в наиболее полном объеме и в срок.

            Рейтинговая оценка работы студента в семестре равна сумме баллов за 3 контрольные работы и практические занятия, и может достичь 72 баллов. Студент, набравший в результате текущего семестрового контроля менее 20 баллов, к экзамену  не допускается; ему выставляется итоговая пятибалльная оценка "неудовлетворительно".

Экзамен  по дисциплине проводится в письменном виде. Экзаменационный билет содержит 5 пунктов, содержащих как теоретические вопросы, так и задачи. Ответ студента на каждый пункт билета оценивается от 0 до 8 баллов.

Сложные разделы дисциплины должны быть тщательно проработаны и при необходимость вынесены на предэкзаменационную консультацию.

Итоговая рейтинговая оценка знаний студента равна сумме баллов, полученных в течение семестра за выполнение контрольных работ, и до 40 баллов, полученных за письменную экзаменационную работу в конце семестра (но не более 100 баллов).

Итоговая пятибалльная оценка по дисциплине определяется в соответствии со следующей схемой: если количество баллов не меньше 91, то выставляется оценка "отлично", иначе, если количество баллов не меньше 71, то выставляется оценка "хорошо", иначе, если количество баллов не меньше 60, то выставляется оценка "удовлетворительно".

           Студенты сдают экзамен.

3. УЧЕБНО-МЕТОДИЧЕСКИЕ МАТЕРИАЛЫ

3.1. ЛЕКЦИИ

Тема 1. Функциональные соответствия и отношения.
1. Операции над множествами.
2. Суперпозиция функций.
3. Операции на множестве.
4. Свойства бинарных операций.
5. Бинарные отношeния.
6. Отношения эквивалентности.
7. Отношения порядка.
8. Операции над двоичными числами.
Тема 2. Булевы функции.
1. Булевы функции и их свойства.
2. Представление булевой функции в виде ДНФ.
3. Представление булевой функции в виде КНФ.
4. Представление булевой функции в виде полинома Жегалкина.
5. Замыкание системы булевых функций.
6. Основные классы булевых функций и их замкнутость.
Тема 3. Логика предикатов.
1. Операции над предикатами.
2. Предикатные формулы. Тавтологии.
Тема 4. Элементы комбинаторики.
1. Основные комбинаторные конфигурации.
2. Формулы пересчета числа комбинаторных конфигураций.
Тема 5. Графы и сети.
1. Ориентированные и неориентированные графы. Способы задания графов.
2. Цепи. Циклы. Связность.
3. Деревья.
4. Пространство циклов графа.
5. Кратчайшие пути и цепи.
Тема 6. Элементы теории кодирования.
1. Алфавитное кодирование.
2. Оптимальное кодирование.
3. Коды с обнаружением и исправлением ошибок.
Тема 7. Алгоритмы и формальные системы.
1. Алгоритмическая процедура.
2. Машины Тьюринга.
3. Понятие формальной грамматики.

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

 [1] Гаврилов Г. П., Сапоженко А.А. "Сборник задач по дискретной математике". - М. 1977.

[2] Джеймс Андерсон.  “Дискретная математика и комбинаторика”.-М.  Издательство “Вильямс” 2004

Тема 1. Функциональные соответствия и отношения. [2] стр.67-112;    (1-2-ая неделя)                                                             1. Операции над множествами.
2. Суперпозиция функций.
3. Операции на множестве.
4. Свойства бинарных операций.
5. Бинарные отношения.   
6. Отношения эквивалентности.
7. Отношения порядка.
8. Операции над двоичными числами.

 Задачи  из [2]: 1-17 (стр. 70); 1-15 (стр. 75-76); 1-8 (стр. 82-84); 1-12 (стр. 97-98);                                                          1-2(стр.105 ); 1-9 (стр. 111-112);  

Тема 2. Булевы функции. [1] стр. 9-76; (3-7-ая неделя)                                                            
1. Булевы функции и их свойства.
2. Представление булевой функции в виде ДНФ.
3. Представление булевой функции в виде КНФ.
4. Представление булевой функции в виде полинома Жегалкина.
5. Замыкание системы булевых функций.
6. Основные классы булевых функций и их замкнутость.

Задачи из [1]: 2.16-2.31,3.1-3.33, 5.1-5.24 (стр. 9-49); 1.1-1.25, 2.1-2.29, 3.1-3.33, 4.1-4.23, 5.1-5.55, 6.1-6.33 (стр. 50-76);


Тема 3. Элементы комбинаторики. [1] стр. 249-280; [2] стр. 322-363; (8-11-ая неделя)                                                            
1. Основные комбинаторные конфигурации.
2. Формулы пересчета числа комбинаторных конфигураций.

Задачи из [1]: 1.1-1.24, 2.1-2.9 (стр. 249-280);                                                                                                        Задачи из [2]:  1-27 (стр. 322-323), 1-20 (стр. 329-330), 1-36 (стр. 341-343), 1-24 (стр. 346),                     1-12 (стр. 363);


Тема 4. Графы и сети. [1] стр. 101-158; [2] стр. 322-363; (12-14-ая неделя)                                                            
1. Ориентированные и неориентированные графы. Способы задания графов.
2. Цепи. Циклы. Связность.
3. Деревья.
4. Пространство циклов графа.
5. Кратчайшие пути и цепи.

Задачи из [1]: 1.1-1.44, 2.1-2.51, 3.1-3.33, 4.1-4.58 (стр. 101-158);                                                                                                        Задачи из [2]:  1-8 (стр. 251-252), 1-12 (стр. 256-259), 1-11 (стр. 264-267), 1-12 (стр. 273-277),                     1-29 (стр. 285-289);


Тема 5. Элементы теории кодирования. [1] стр. 159-177; [2] стр. 322-363; (15-16-ая неделя)                                                            
1. Алфавитное кодирование.
2. Оптимальное кодирование.
3. Коды с обнаружением и исправлением ошибок.

Задачи из [1]: 1.1-1.28, 2.1-2.25, 3.1-3.31 (стр. 159-177);                                                                                                        Задачи из [2]:  1-13 (стр. 765-766), 1-13 (стр. 773-774), 1-11 (стр. 264-267), 1-12 (стр. 273-277),                     1-29 (стр. 285-289);


Тема 6. Алгоритмы и формальные системы. [1] стр. 213-248; (17-18-ая неделя)                                                            
1. Алгоритмическая процедура.
2. Машины Тьюринга.
3. Понятие формальной грамматики.
Задачи из [1]: 1.1-1.26, 2.1-2.25, 3.1-3.31 (стр. 213-248);  

 

[1] Гаврилов Г. П., Сапоженко А.А. "Сборник задач по дискретной математике". - М. 1977.

[2] Джеймс Андерсон.  “Дискретная математика и комбинаторика”.-М.  Издательство “Вильямс” 2004

 

3.3. Методические указания для преподавателей, ведущих практические занятия.

           

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

             Наш вариант изложения дисциплины имеет своей целью удобство ее приложений в других дисциплинах курса обучения. Другие варианты изложения и дополнительные результаты могут быть получены студентами из книг, приведенных в списке литературы.
В лекциях обсуждаются решения всех задач, включаемых в контрольные работы и экзаменационные билеты.
              В течение семестра на практических занятиях проводится 3 контрольные работы. Расчетная продолжительность каждой контрольной работы не превышает 2 часа. Задания для контрольных работ (без разбиения на варианты) содержатся в электронных методических указаниях [1] и также доступны студентам без ограничений.

 

 

 

  1. СЛОВАРЬ ТЕРМИНОВ.

Тема 1. Функциональные соответствия и отношения.
1. Операции над множествами.
2. Суперпозиция функций.
3. Операции на множестве.
4. Бинарные отношeния.
5. Отношения эквивалентности.
7. Отношения порядка.
Тема 2. Булевы функции.
1. Булевы функции.
2. Представление булевой функции в виде CДНФ.
3. Представление булевой функции в виде CКНФ.
4. Полином Жегалкина.
5. Замыкание системы булевых функций.
6. Основные классы булевых функций .
Тема 3. Логика предикатов.
1. Операции над предикатами.
2. Предикатные формулы. Тавтологии.
Тема 4. Элементы комбинаторики.
1. Основные комбинаторные конфигурации.
2. Формулы пересчета числа комбинаторных конфигураций.
Тема 5. Графы и сети.
1. Ориентированные и неориентированные графы.
2. Цепи. Циклы. Связность.
3. Деревья.
4. Пространство циклов графа.
Тема 6. Элементы теории кодирования.
1. Алфавитное кодирование.
2. Оптимальное кодирование.
3. Коды с обнаружением и исправлением ошибок.
Тема 7. Алгоритмы и формальные системы.
1. Алгоритмическая процедура.
2. Машины Тьюринга.
3. Понятие формальной грамматики.

См. [1] Яблонский С.В. Введение в дискретную математику. М., 1987.

 

 

  1. ФОРМЫ ТЕКУЩЕГО,  ПРОМЕЖУТОЧНОГО, РУБЕЖНОГО И ИТОГОВОГО КОНТРОЛЯ

 

5.1.КОНТРОЛЬНЫЕ ВОПРОСЫ ПО КАЖДОЙ ТЕМЕ

Тема 1. Функциональные соответствия и отношения.
1. Операции над множествами.
2. Суперпозиция функций.
3. Операции на множестве.
4. Свойства бинарных операций.
5. Бинарные отношeния.
6. Отношения эквивалентности.
7. Отношения порядка.
8. Операции над двоичными числами.
Тема 2. Булевы функции.
1. Булевы функции и их свойства.
2. Представление булевой функции в виде ДНФ.
3. Представление булевой функции в виде КНФ.
4. Представление булевой функции в виде полинома Жегалкина.
5. Замыкание системы булевых функций.
6. Основные классы булевых функций и их замкнутость.
Тема 3. Логика предикатов.
1. Операции над предикатами.
2. Предикатные формулы. Тавтологии.
Тема 4. Элементы комбинаторики.
1. Основные комбинаторные конфигурации.
2. Формулы пересчета числа комбинаторных конфигураций.
Тема 5. Графы и сети.
1. Ориентированные и неориентированные графы. Способы задания графов.
2. Цепи. Циклы. Связность.
3. Деревья.
4. Пространство циклов графа.
5. Кратчайшие пути и цепи.
Тема 6. Элементы теории кодирования.
1. Алфавитное кодирование.
2. Оптимальное кодирование.
3. Коды с обнаружением и исправлением ошибок.
Тема 7. Алгоритмы и формальные системы.
1. Алгоритмическая процедура.
2. Машины Тьюринга.
3. Понятие формальной грамматики.

        5.2. Варианты контрольных работ, тесты.

Формы текущего, промежуточного, рубежного и итогового контроля:

Варианты контрольных работ, тесты;

 

  1. Функция, заданная СДНФ  , имеет столбец значений

  1. Функция, заданная СДНФ  , имеет столбец значений

  1. Функция, заданная СДНФ  , имеет столбец значений

  1. Функция, заданная СДНФ  , имеет столбец значений

  1. Функция, заданная СДНФ  , имеет столбец значений

  1. Функция, заданная СДНФ  , имеет столбец значений

  1. Функция, заданная СДНФ  , имеет столбец значений

 

  1. Булевы функции и задаются столбцами значений и . Столбцом значений функции является



  1. Булевы функции и задаются столбцами значений и . Столбцом значений функции является

.

  1. Булевы функции и задаются столбцами значений и . Столбцом значений функции является

.

  1. Булевы функции и задаются столбцами значений и . Столбцом значений функции является

.

  1. Булевы функции и задаются столбцами значений и . Столбцом значений функции является

.

 

13. СДНФ булевой функции, задаваемой таблицейсодержит элементарную конъюнкцию

1) ,2) Y.

14. СДНФ булевой функции, задаваемой таблицейсодержит элементарную конъюнкцию

1) ,2) X .

15. СДНФ булевой функции, задаваемой таблицейсодержит элементарную конъюнкцию

1) ,2) X Y.

16. СДНФ булевой функции, задаваемой таблицейсодержит элементарную конъюнкцию

1) Y,2) X Y.

17. СДНФ булевой функции, задаваемой таблицейсодержит элементарную конъюнкцию

1) Y,2) X.

18. СДНФ булевой функции, задаваемой таблицейсодержит элементарную конъюнкцию

1) XY,2) X.

 

19. Бинарное отношение R(x, y) есть отношение строгого порядка, если оно
транзитивно, антисимметрично и антирефлексивно
20. Бинарное отношение R(x, y) есть отношение эквивалентности, если оно
рефлексивно, симметрично и транзитивно
21. Бинарное отношение между окружностями и на плоскости: "окружность пересекается с окружностью " является
1) симметричным,2) нетранзитивным,
22. Бинарное отношение между окружностями и на плоскости: "окружность находится внутри окружности " является
1) транзитивным,2) антисимметричным,
23. Бинарному отношению удовлетворяют пары:
(11,15) и (17,21)

Примерный список задач по темам курса “Дискретная математика”

Множества

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

  1. Пусть универсальное множество U - множество всех сотрудников некоторой фирмы; A – множество всех сотрудников данной организации старше 40 лет; B – множество сотрудников, имеющих стаж работы более 10 лет; C – множество менеджеров фирмы. Каков содержательный смысл(характеристическое свойство) каждого из следующих множеств:; ; ; ; ; ; ; ; ; ;
  2. Осуществить операции (объединения, пересечения, разности и дополнения) над множествами A={2,4,6,8} и B={3,6,9}, если U={1,2,3,…,10}
  3. Даны два произвольных множества A и B такие, что (пустое множество). Что представляют собой  и ?
  4. Даны два произвольных множества A и B такие, что (пустое множество). Что представляют собой  и ?
  5. Дано произвольное множество X. Найти множества ;

 

Диаграммы Венна

  1. Представить множество  диаграммой Венна.
  2. Проиллюстрировать на конкретных множествах и с помощью диаграммы Венна справедливость соотношения .
  3. Подтвердить справедливость свойства дистрибутивности справа пересечения  относительно объединения , а также слева и справа  относительно , т.е.:

а)  - справа пересечения  относительно объединения ;

б)  - слева  относительно ;

в)  - справа  относительно .

  1. Пусть . Проиллюстрировать на примере конкретных множеств и с помощью диаграмм Венна справедливость следующих соотношений:

а);

б);

в) ;

г) ;

д) ;

е).

 

Доказательства

  1. Доказать справедливость соотношения .
  2. Доказать справедливость соотношения .
  3. Доказать, что относительно данного универсального множества U дополнение любого множества , если , единственно.
  4. Доказать эквивалентность приведенных ниже утверждений, т.е. что из каждого следует другое:

      пустое множество

 

 

Отношения

 

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

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

а) R1 - "находиться на одинаковом расстоянии от начала координат";

б) R2 - 'находиться на разном расстоянии от начала координат";

в) R3 - "находиться на одной и той же окружности с центром в начале координат";

г) R4 - "быть симметричным относительно оси X".

  1. Для указанных ниже, заданных на множестве элементов структуры на рисунке, отношений привести примеры пар, для которых выполняются отношения, и пар, для которых отношения не выполняются:

 

а) R2 - "быть частью целого";

б) R2 - "быть непосредственно связанным с";

в) R2 - "быть начальником";

                 a

 

 

         b              c

 

 

d      e       f      g        h

 
г) R2 - "быть непосредственным начальником".

 

 

 

 

Свойства бинарных отношений

  1. Каковы свойства отношений, заданных на множестве натуральных чисел N:

а) Rl - "быть не больше < ";

б) R2 - "быть делителем";

в) R3 - "быть равным".

  1. Каковы свойства отношений, заданных на множестве точек действительной плоскости R2?:

а) R1 - "находиться на одинаковом расстоянии от начала координат";

б) R2 - "быть симметричным относительно оси X".

  1. Каковы свойства отношений, заданных на множестве людей:

а) R1 - "быть сыном";

б) R2 - "жить в одном городе";

в) R3 - "быть братом".

  1. Каковы свойства отношений, заданных на множестве элементов структуры (см. рисунок):

                 a

 

 

         b              c

 

 

d      e       f      g        h

 
а) R1 - "быть непосредственно связанным с";

б) R2 - "быть начальником".

 

 

 

 

 

 

 

 

  1. Какими свойствами характеризуются следующие отношения на M={1,2,3,…,9}:

a)R1={(a,b): (a-b) – четное};

b)R2={(a,b): (a+b) – четное};

c)R3={(a,b): (a+1) – делитель (a+b)};

d)R4={(a,b): a – делитель (a+b), a 1}.

 

Эквивалентность и порядок

  1. К каким типам отношений относятся отношения  и  на множестве векторов длины n с компонентами из N, определяемые следующим образом:

а)(а1,…,an)(b1,…,bn), если а1b1,…,anbn

б)(а1,…,an)<(b1,…,bn), если (а1,…,an)(b1,…,bn) и хотя бы в одной координате i выполняется ai<bi.

  1. Пусть R1 и R2 – отношения на N2, определяемые следующим образом: (a,b)R1(c,d) тогда и только тогда, когда ас и bd; (a,b)R2(c,d) тогда и только тогда, когда ас и bd. Являются ли R1 и R2 отношениями порядка?

                                                                                                                                                                           Двоичная система счисления

  1. Представить C в двоичной системе счисления:                                                                                             a) C=A*B-B*56; b) C=A*243-B*B; c) C=A*326+B+A-B*432; где A=100111012  , B=101111101

 

 

Комбинаторика

24.  Расписание одного дня содержит 5 уроков. Определить количество таких расписаний при выборе из 11 дисциплин.

25.  Комиссия состоит из председателя, его заместителя и еще пяти человек. Сколькими способами члены комиссии могут распределить между собой обязанности?

26.  Сколькими способами можно выбрать трех дежурных из группы в 20 человек?

27.  Сколько различных звукосочетаний можно взять на десяти выбранных клавишах рояля, если каждое звукосочетание может содержать от трех до десяти звуков?

28.  В вазе стоят 10 красных и 5 розовых гвоздик. Сколькими способами можно выбрать из вазы пять гвоздик одного цвета?

29.  Номера трамвайных маршрутов иногда обозначаются двумя цветными фонарями. Какое количество различных маршрутов можно обозначить, если использовать фонари восьми цветов?

30.  Чемпионат, в котором участвуют 16 команд, проводится в два круга (т. е. каждая команда дважды встречается с любой другой). Определить, какое количество встреч следует провести.

31.  Замок открывается только в том случае, если набран определенный трехзначный номер. Попытка состоит в том, что набирают наугад три цифры из заданных пяти цифр. Угадать номер удалось только на последней из всех возможных попыток. Сколько попыток предшествовало удачной?

32.  Из группы в 15 человек выбирают четырех участников эстафеты 800+400+200+100. Сколькими способами можно расставить спортсменов по этапам эстафеты?

33.  Команда из пяти человек выступает на соревнованиях по плаванию, в которых участвуют еще 20 спортсменов. Сколькими способами могут распределиться места, занятые членами этой команды?

34.  Сколькими способами можно расположить на шахматной доске две ладьи так, чтобы одна не могла взять другую? (Одна ладья может взять другую, если она находится с ней на одной горизонтали или на одной вертикали шахматной доски.)

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

36.  Порядок выступления восьми участников конкурса определяется жребием. Сколько различных исходов жеребьевки при этом возможно*

37.  Тридцать человек разбиты на три группы по десять человек в каждой. Сколько может быть различных составов групп?

38.  Сколько четырехзначных чисел, делящихся на 5, можно составить из цифр 0, 1, 3, 5, 7, если каждое число не должно содержать одинаковых цифр?

39.  Сколько различных светящихся колец можно сделать, расположив по окружности 10 разноцветных лампочек (кольца считаются одинаковыми при одинаковом порядке следования цветов)?

40.  На книжной полке помещается 30 томов. Сколькими способами их можно расставить, чтобы при этом первый и второй тома не стояли рядом?

41.  Четыре стрелка должны поразить восемь мишеней (каждый по две). Сколькими способами они могут распределить мишени между собой?

42.  Из группы в 12 человек ежедневно в течение 6 дней выбирают двух дежурных. Определить количество различных списков дежурных, если каждый человек дежурит один раз.

43.  Сколько четырехзначных чисел, составленных из цифр 0, 1, 2, 3, 4, 5, содержат цифру 3 (цифры в числах не повторяются)?

44.  Десять групп занимаются в десяти расположенных подряд аудиториях. Сколько существует вариантов расписания, при которых группы №1 и №2 находились бы в соседних аудиториях?

45.  В турнире участвуют 16 шахматистов. Определить количество различных расписаний первого тура (расписания считаются различными, если отличаются участниками хотя бы одной партии; цвет фигур и номер доски не учитываются).

46.  Шесть ящиков различных материалов доставляются на пять этажей стройки. Сколькими способами можно распределить материалы по этажам? В скольких вариантах на пятый этаж доставлен какой-либо один материал?

47.  Два почтальона должны разнести 10 писем по 10 адресам. Сколькими способами они могут распределить работу?

48.  Поезд метро делает 16 остановок, на которых выходят все пассажиры. Сколькими способами могут распределиться между этими остановками 100 пассажиров, вошедших в поезд на конечной остановке?

49.  Сколько трехзначных чисел, делящихся на 3, можно составить из цифр 0, 1, 2, 3, 4, 5, если каждое число не должно содержать одинаковых цифр?

50.  Собрание из 80 человек избирает председателя, секретаря и трех членов ревизионной комиссии. Сколькими способами это можно сделать?

51.  Из 10 теннисисток и 6 теннисистов составляют 4 смешанные пары. Сколькими способами это можно сделать?

52.  Три автомашины №1, 2, 3 должны доставить товар в шесть магазинов. Сколькими способами можно использовать машины, если грузоподъемность каждой из них позволяет взять товар сразу для всех магазинов и если две машины в один и тот же магазин не направляются? Сколько вариантов маршрута возможно, если решено использовать только машину №1?

53.  Четверо юношей и две девушки выбирают спортивную секцию. В секции хоккея и бокса принимают только юношей, в секцию художественной гимнастики – только девушек, а в лыжную и конькобежную секции – и юношей, и девушек. Сколькими способами могут распределиться между секциями эти шесть человек?

54.  Из лаборатории, в которой работает 20 человек, 5 сотрудников должны уехать в командировку. Сколько может быть различных составов этой группы, если начальник лаборатории, его заместитель и главный инженер одновременно уезжать не должны?

55.  В фортепьянном кружке занимаются 10 человек, в кружке художественного слова— 15, в вокальном кружке – 12, в фото-кружке – 20 человек. Сколькими способами можно составить бригаду из четырех чтецов, трех пианистов, пяти певцов и одного фотографа?

56.  Двадцать восемь костей домино распределены между четырьмя игроками. Сколько возможно различных распределений?

57.  Из группы в 15 человек должны быть выделены бригадир и 4 члена бригады. Сколькими способами это можно сделать?

58.  Пять учеников следует распределить по трем параллельным классам. Сколькими способами это можно сделать?

59.   Лифт останавливается на десяти этажах. Сколькими способами могут распределиться между этими остановками 8 пассажиров, находящихся в кабине лифта?

60.  Восемь авторов должны написать книгу из шестнадцати глав. Сколькими способами возможно распределение материала между авторами, если два человека напишут по три главы, четыре — по две, два — по одной главе книги?

61.  В шахматном турнире участвуют 8 шахматистов третьего разряда, 6 — второго и 2 перворазрядника. Определить количество таких составов первого тура, чтобы шахматисты одной категории встречались между собой (цвет фигур не учитывается).

62.  Из цифр 1, 2, 3, 4, 5, 6, 7, 8, 9 составляются всевозможные пятизначные числа, не содержащие одинаковых цифр. Определить количество чисел, в которых есть цифры 2, 4 и 5 одновременно.

63.  Семь яблок и три апельсина надо положить в два пакета так, чтобы в каждом пакете был хотя бы один апельсин и чтобы количество фруктов в них было одинаковым. Сколькими способами это можно сделать?

64.  Буквы азбуки Морзе состоят из символов (точек и тире). Сколько букв можно изобразить, если потребовать, чтобы каждая буква содержала не более пяти символов?

65.  Номер автомобильного прицепа состоит из двух букв и четырех цифр. Сколько различных номеров можно составить, используя 30 букв и 10 цифр?

66.  Садовник должен в течение трех дней посадить 10 деревьев. Сколькими способами он может распределить по дням работу, если будет сажать не менее одного дерева в день?

67.  Из вазы, где стоят 10 красных и 4 розовые гвоздики, выбирают один красный и два розовых цветка. Сколькими способами это можно сделать?

68.  Двенадцати ученикам выданы два варианта контрольной работы. Сколькими способами можно посадить учеников в два ряда, чтобы у сидящих рядом не было одинаковых вариантов, а у сидящих друг за другом был один и тот же вариант?

69.  Каждый из десяти радистов пункта А старается установить связь с каждым из двадцати радистов пункта Б. Сколько возможно различных вариантов такой связи?

70.  Шесть ящиков различных материалов доставляют на восемь этажей стройки. Сколькими способами можно распределить материалы по этажам? В скольких из них на восьмой этаж будет доставлено не менее двух материалов?

71.  Сколькими способами можно построить в одну шеренгу игроков двух футбольных команд, так чтобы при этом два футболиста одной команды не стояли рядом?

72.  На книжной полке книги по математике и по логике — всего 20 книг. Показать, что наибольшее количество вариантов комплекта, содержащего 5 книг по математике и 5 книг по логике, возможно в том случае, когда число книг на полке по каждому предмету равно 10.

73.  Лифт, в котором находится 9 пассажиров, может останавливаться на десяти этажах. Пассажиры выходят группами в два, три и четыре человека. Сколькими способами это может произойти?

74.  В шахматной встрече двух команд по 8 человек участники партий и цвет фигур каждого участника определяются жеребьевкой. Каково число различных исходов жеребьевки?

  1. Вычислить значения функций f(x1,x2,x3) на наборах (0,0,1) и (1,0,1)

a)

b)

c)

  1. Приведена таблица истинности для булевых функций f,g,h,e

x1

x2

x3

f

g

h

e

0

0

0

0

0

0

0

0

0

1

0

0

1

1

0

1

0

1

1

1

1

0

1

1

1

1

1

0

1

0

0

0

1

0

1

1

0

1

0

1

1

0

1

1

0

0

0

1

1

1

1

1

1

0

1

0

 

Проверить функции на существенность переменных. Обосновать ответ.

  1. Привести к КНФ формулы:

  1. Проверить на полноту системы:

a){01100110, , x}

b){11100111, ,1}

 

 

Графы

1.      Задать граф G1, представленный на рисунке 1,

 

 

 

 

 

 

 

 

 

 

 


Рис. 1

через множества вершин V1 и ребер E1.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2.      На рис. 2 изображены графы.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


Рис. 2

Сравнить графы (на предмет ориентированности, полноты, изолированности вершин, и т.д.).

3.      На рис. 3 изображены графы.

 

 

 

 

 

 

 

 

 

 


Рис. 3

Чему равны степени вершин графов?

4.      Задать графы на рис. 3 множествами их вершин и ребер.

5.      Является ли граф G3 на рис. 1 связным, сильно связным?

6.      Является ли граф G11 на рис. 2 связным, сильно связным?

7.      Является ли граф G3 на рис. 3 связным, сильно связным?

8.      На рис. 4 изображены графы.                                                                                       Рис.4

 

 

 

 

 

 

 

 


Содержат ли графы Эйлеровы циклы (цепи)? Обоснуйте ответ.                                                

 

                                              ТЕСТ.

 

  1. Алфавитное упорядочение натуральных чисел в десятичной записи совпадает с упорядочением их по возрастанию для множества

чисел, имеющих одинаковое число разрядов

2. Алфавитное упорядочение слов в русском алфавите

1) антисимметрично, 2) транзитивно,

3.  Арифметическая операция вычитания чисел X – Y является

1) некоммутативной, 2) неассоциативной,

4.  Арифметическая операция сложения чисел X + Y является

1) коммутативной,2) ассоциативно,

5.  Арифметическая операция умножения чисел X • Y является

1) коммутативной,2) ассоциативной,

6.  Без разделителей можно использовать код алфавита

1) {a: 01, b: 11, c: 100},2) {a: 0, b: 100, c: 11},

7.  Без разделителей можно использовать код алфавита

1) {a: 00, b: 10, c: 110},2) {a: 1, b: 01, c: 001},

8.  Бинарное отношение . Транзитивному замыканию принадлежит пара

(7, 19)

9.  Бинарное отношение «правее» между точками на числовой прямой является

1) транзитивным,2) антисимметричным,

10.  Бинарное отношение P: X < Y на множестве действительных чисел является

1) антисимметричным,2) транзитивным,

11.  Бинарное отношение R(x, y) есть отношение нестрогого порядка, если оно

транзитивно, антисимметрично и рефлексивно

  1.  Бинарное отношение R(x, y) есть отношение строгого порядка, если оно

транзитивно, антисимметрично и антирефлексивно

  1.  Бинарное отношение R(x, y) есть отношение эквивалентности, если оно

рефлексивно, симметрично и транзитивно

15.  Бинарное отношение между окружностями и на плоскости: "окружность пересекается с окружностью " является

1) симметричным,2) нетранзитивным,

16.  Бинарное отношение между окружностями и на плоскости: "окружность находится внутри окружности " является

1) транзитивным,2) антисимметричным,

17. Бинарному отношению удовлетворяют пары:

(13,17) и (6,10)

18.  Бинарному отношению удовлетворяют пары:

(12,16) и (17,21)

19.  Бинарному отношению удовлетворяют пары:

(8,12) и (14,18)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Балльно-рейтинговая система оценки успеваемости студентов по дисциплине

Методика формирования результирующей оценки:
Выполнение каждой письменной контрольной работы оценивается от 0 до 12 баллов.
Выполнение студентом заданий на каждом практическом занятии оценивается от 0 до 4 баллов.
Рейтинговая оценка работы студента в семестре равна сумме баллов за 3 контрольные работы и практические занятия, и может достичь 72 баллов. Студент, набравший в результате текущего семестрового контроля менее 20 баллов, к зачету не допускается; ему выставляется итоговая пятибалльная оценка "неудовлетворительно".
Зачет по дисциплине проводится в письменном виде. Зачетный билет содержит 5 пунктов, содержащих как теоретические вопросы, так и задачи. Ответ студента на каждый пункт билета оценивается от 0 до 8 баллов.
Итоговая рейтинговая оценка знаний студента равна сумме баллов, полученных в течение семестра за выполнение контрольных работ, и до 40 баллов, полученных за письменную экзаменационную работу в конце семестра (но не более 100 баллов).
Итоговая пятибалльная оценка по дисциплине определяется в соответствии со следующей схемой: если количество баллов не меньше 91, то выставляется оценка "отлично", иначе, если количество баллов не меньше 71, то выставляется оценка "хорошо", иначе, если количество баллов не меньше 60, то выставляется оценка "удовлетворительно".
В семестре студенты сдают зачет. Для получения зачета необходимо получить семестровую оценку не ниже "удовлетворительно".