Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Документ'
Муниципальное бюджетное образовательное учреждение Красивская средняя общеобразовательная школа, 393345, Тамбовская область, Инжавинский район, с.Крас...полностью>>
'Пояснительная записка'
• освоение знаний о механических, тепловых явлениях, величинах, характеризу­ющих эти явления; законах, которым они подчиняются; методах научного позна...полностью>>
'Документ'
При подтверждении резервации (в случае неподтверждения резервации Вам необходимо сразу же связаться с агентством Эволюсьон Вояж в Париже по телефону 0...полностью>>

Главная > Программа для подготовки

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

МОСКОВСКАЯ ФИНАНСОВО-ЮРИДИЧЕСКАЯ АКАДЕМИЯ

Согласовано на 2008-2009 уч.год

Начальник УМУ

__________________С.В. Щедроткина

«_____»_______________2009 г.

Дисциплина: Дискретная математика и теория нечетких множеств

Специальность (направление): Информатика в экономике

Форма обучения: все

Программа для подготовки к зачету

КОМПЛЕКТЫ МАТЕРИАЛОВ ДЛЯ ПОДГОТОВКИ К ЗАЧЕТУ.

ДЛЯ ВСЕХ ФОРМ ОБУЧЕНИЯ

ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

Список тем, выносимых на зачет.

  1. Понятие множества. Пустое множество. Наиболее употребляемые множества.

  2. Множества и отношения. Подмножество.

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

  4. Алгебра множеств.

  5. Сравнение множеств.

  6. Упорядоченные множества.

  7. Свойства и отношения.

  8. Отображения.

  9. Решетки.

  10. Основные правила комбинаторики.

  11. Перестановки, сочетания, размещения, размещения с повторениями.

  12. Биноминальные коэффициенты.

  13. Алгебра Буля.

  14. Формулы алгебры логики.

  15. Функции алгебры логики.

  16. Нормальные формы булевой функции (КНФ, ДНФ).

  17. СДНФ. СКНФ.

  18. Двойственность алгебры логики.

  19. Многочлен Жегалкина, классы Поста, теорема Поста.

  20. Полнота логических связок.

  21. Электронные логические элементы.

  22. Язык логики высказываний.

  23. Понятие семантики в логике высказываний.

  24. Операции логики высказываний.

  25. Нормальные формы логики высказываний (КНФ, ДНФ).

  26. Таблица истинности для формулы.

  27. Метод резолюции.

  28. Теоретико-множественная форма представления предложения.

  29. Понятие предиката.

  30. Кванторы.

  31. Язык логики предикатов.

  32. Подстановка. Композиция.

  33. Интерпретация и истинность в логике предикатов.

  34. Унификация в логике предикатов.

  35. Тавтология, выполнимость и противоречие в логике высказываний и предикатов.

  36. Предварённая нормальная форма.

  37. Сколемовская нормальная форма.

  38. Метод резолюции в логике предикатов..

  39. Графы. Основные понятия и определения.

  40. Изоморфизм графов.

  41. Маршруты, цепи и циклы.

  42. Матричное задание графов.

  43. Связность. Компоненты связности.

  44. Степень вершин графа, орграфа.

  45. Поиск маршрута в графе.

  46. Поиск путей (маршрутов) с минимальным числом дуг (рёбер).

  47. Минимальные пути (маршруты) в нагруженных орграфах (графах).

  48. Эйлеровы графы.

  49. Гамильтоновы графы.

  50. Деревья.

  51. Остовное дерево графа.

  52. Понятия неопределенности и четкости.

  53. Функция принадлежности.

  54. Частично упорядоченные множества.

  55. Нечеткие множества.

  56. Нечеткие логики.

  57. Нечеткие отношения.

  58. Нейро-нечеткие системы.

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

ПРАКТИЧЕСКАЯ ЧАСТЬ

Типовые задачи.

Множества.

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

а) (АВ)(А)=А; б) А\В=А

2. Найдите множество Х, удовлетворяющее следующему равенству .

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

(АВ)(А)=А

  1. Верно ли, что .

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

(В)А=АВ

  1. Верно ли, что .

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

(А\В)\С=(А\С)\(В\С)

  1. Верно ли, что если и , то, В = С.

  1. Докажите (символ означает «тогда и только тогда, когда»).

  1. Докажите (символ означает «тогда и только тогда, когда»).

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

А(В\С)=(АВ)(А)

  1. Докажите (символ означает «тогда и только тогда, когда»).

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

(А\В)()=(АВ)\(АВ)

  1. Докажите и (символ означает «тогда и только тогда, когда»).

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

()()=(АВ)\(АВ)

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

1. Сколько существует способов разместить 3 человека на скамейке?

2. Сколько существует способов расставить 8 книг на полке так, чтобы 3 данные книги стояли вместе?

3. Сколькими различными способами можно выбрать три лица на три различных должности из 8 кандидатов?

4. Сколькими способами можно выбрать 3 лица на 3 одинаковые должности из 8 кандидатов?

5. Сколько различных 6-ти значных чисел можно записать с помощью цифр 1;1;2;2;2;3?

6. Cколько различных перестановок букв можно сделать в словах: замок, ротор, топор, колокол?

7. Сколько прямых можно провести через 8 точек, никакие 3 из которых не лежат на одной прямой, так чтобы каждая прямая проходила через 2 точки?

  1. Сколько различных шестизначных чисел, начинающихся цифрой 2 и оканчивающихся цифрой 5, можно составить из цифр 1, 2, 3, 4, 5, 6 при условии, что каждая цифра в обозначении числа встречается 1 раз?

  1. Найти m и n, если .

10. Вычислить: .

11. Сколько существует кодовых комбинаций в замке, имеющем 5 дисков и на каждом диске 6 цифр.

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

1. Привести к СДНФ с помощью таблицы истинности и равносильных преобразований. Записать в виде многочлена Жегалкина и построить логическую схему в базисе “И-НЕ”.

2. Доказать, что формула тождественно равна 0 или 1.

3. Привести к СДНФ с помощью таблицы истинности и равносильных преобразований.

Записать в виде многочлена Жегалкина и построить логическую схему в базисе “И-НЕ”.

4. Доказать, что формула тождественно равна 0 или 1.

5. Привести к СКНФ с помощью таблицы истинности и равносильных преобразований. Записать в виде многочлена Жегалкина и построить логическую схему в базисе “И-НЕ”.

6.. Упростить формулу.

7. Привести к СКНФ с помощью таблицы истинности и равносильных преобразований. Записать в виде многочлена Жегалкина и построить логическую схему в базисе “И-НЕ”.

8. Упростить формулу.

9. Привести к СКНФ с помощью таблицы истинности и равносильных преобразований. Записать в виде многочлена Жегалкина и построить логическую схему в базисе “ИЛИ-НЕ”.

10. Доказать равносильность.

11. Привести к СДНФ с помощью таблицы истинности и равносильных преобразований. Записать в виде многочлена Жегалкина и построить логическую схему в базисе “ИЛИ-НЕ”.

12. Доказать равносильность.

. 13. Известно, что х=1. Что можно сказать о значении:

и .

14. Известно, что . Что можно сказать о значении:

.

15. Известно, что , а . Что можно сказать о значении:

Логика высказываний.

  1. Доказать, что высказывание логически ложно.

а. АВ)(ВС)(АС);

б. ((АВ)(АВ)А;

в. А(ВВ))А.

2. Доказать, что высказывание логически истинно.

а. (АВ)(АВ).

б. (А(АВ))В.

в. (АВ)АВ

3. Докажите, что высказывание является тавтологией.

а. (А→В)(АВ)

б. АВВА.

в. (АВ)(ВА).

4. Найти означивания при которых формула истинна.

а. А(АВ).

б. (АВ)(ВА).

в. (АВ)(АВ).

5. Методом резолюции доказать, что множество S противоречиво.

а. S={ABD, BDA, DA, AB, BD, AB}.

б. S={AB, BC, CA, AC, AC}.

в. S={ABC, ABC, AB, AC, AC}.

6. Методом резолюции доказать, что

а. {AB, CD, DB, BCD}├ BC.

б. {ABC, AB} ├ AC.

7. Представьте следующее высказывание как множество дизъюнктов.

а. А(ВС).

б. ((АВ)С).

8. Определить выполнимо ли множество. Если да, то найти означивания подтверждающие его выполнимость.

а. {{A,B}, {A,B}}.

б. {{A}, {A,B}, {B}}.

9. Определить множество резольвент дизъюнктов S.

а. S={{A,B}, {A,B}, {A}}

б. S={{A}, {B},{A,B}}

в. S={{A}, {B},{A,B}}

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

1. Выявить логическую форму предложения и записать её на языке логики предикатов.

а. “Каждый студент знает хотя бы некоторых преподавателей”.

б. “Неверно, что никто не знает русского языка.”

в. “Все любят Джейн, но она не любит ни кого.”

г. “Ничто не вечно”.

д. “Разность любых двух положительных чисел меньше суммы этих чисел”.

е. Если он мой отец , то он старше и мудрее меня.”

2. Запишите следующие высказывания на языке логики предикатов:

а. х – мать у, если х – женщина и родитель у.

б. х – отец у, если х – мужчина и родитель у.

в. х – человек, если его родитель человек.

г. х – человек, если отец х – человек.

д. Никто не родитель самому себе.

3. Привести к ПНФ и далее записать предложения в СНФ

а. (х)Р(х)(х)Q(х).

б. (х)(у)[(z)P(x,y)Р(x,z)](u)Q(x,y,u).

в. (x)(y)[(z)P(x,y,z)[(u)Q(x,u)(u)Q(y,u)]].

4. Записать предложение в теоретико-множественной форме.

а. (x)(y)(z)[(P(x,y)Q(x)R(z))(P(x,y)Q(x))(P(x,y)R(z))].

б. (х)(y)[P(x,y)Q(y)].

в. [(x)P(x)(y)(z)Q(y,z)].

5. Если множество дизъюнктов S предложения унифицируемо, то найти НОУ

а. S={{P(a, x, h(g(z)))}, P(z, h(y), h(y))}}.

б. S ={{любит(w,(у))}, {любит(Джон, футбол)}}.

в. S={{Q((w), a, z)}, Q(w, b, (z))}.

г. S={{R(w,y), Q(w, (z),z), R(w,w)}, {R(w,z), Q((w),w,z)}}.

д. S={{P((x),a)},{P(y,(w))}}.

Графы.

  1. Найти минимальный путь из v1 в v6 методом «фронта волны».

  1. Найти минимальный путь из v1 в v7 в орграфе, заданном матрицей смежности методом «фронта волны».

А(D) =

  1. Определить минимальный путь из v1 в v7 в нагруженном орграфе D с числом дуг не более 5.

С(D) =

  1. Проверить существуют ли в мультиграфе, заданном матрицей смежности, эйлеровы цепи и циклы, если да то найти их.

A(G) = , A(G) =

УЧЕБНО-МЕТОДИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ.

Базовые учебные пособия.

  1. 20. Нефедов В.Н., Осипова В. А. Курс дискретной математики. М.: Изд. МАИ. 1992. 264 с.

  2. С.В. Судоплатов, Е.В. Овчинникова Элементы дискретной математики. М.: ИНФРА-М, Новосибирск: Изд-во НГТУ 2002. 280 с.

  3. Ф.А. Новиков Дискретная математика для программистов. СПб: ПИТЕР. 2001. 304 с.

4. Куликов Л. Я., Москаленко А. И., Фомин А. А. Сборник задач по алгебре и теории чисел. М.: Просвещение. 1993. 288 с.

5. Лавров И. А., Максимова Л. Л. Задачи по теории множеств, математической логике и теории алгоритмов. М.: ФИЗМАТЛИТ. 2001. 256 с.

6. Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов. М. Академия. 2005.- 304 с.



Похожие документы:

  1. Методические рекомендации по изучению дисциплины «Стратегический менеджмент» Для студентов и преподавателей экономических вузов и специальностей, всех форм обучения

    Методические рекомендации
    ... Для студентов и преподавателей экономических вузов и специальностей, всех форм обучения ... студентов для подготовки к семинарским ... предусмотренных программой для самостоятельного изучения ... к зачету по дисциплине ... сырье, материалы, комплектующие? Кто ...
  2. Учебное пособие предназначено для студентов экономических вузов всех форм обучения, аспирантов, преподавателей, может быть полезно работникам инвестиционной сферы. © Попков В. П., Семенов В. П., 2001 © Издательский дом "Питер", 2001

    Документ
    ... для студентов экономических вузов всех форм обучения ... в сырье, материалах, комплектующих изделиях с указанием ... направлениях инвестиционных программ; * ... * подготовка проспекта эмиссии; * подготовка и ... торгов происходит зачет обязательств, оформление ...
  3. Учебно-практическое пособие для студентов всех специальностей и всех форм обучения www

    Учебно-практическое пособие
    ... для студентов всех специальностей и всех форм обучения ... для подготовки ... программу. Самостоятельно отладить программу ... материалов, необходимых для ... сдающих зачет ... - P0)(1/ψ + 1). Пусть задан комплект машин «экскаватор - автосамосвалы». Экскаватор погружает ...
  4. Образовательная программа муниципального бюджетного дошкольного образовательного учреждения

    Образовательная программа
    ... для всех ... обучение детей с фонетико-фонематическим недоразвитием. Программа и методические рекомендации для ... материалы для ... формами подготовки детей ... обучение детей с задержкой психического развития. М.: Ника-пресс, 1998 Комплект рабочих тетрадей для ... зачеты ...
  5. Учебное пособие предназначено для студентов специальности «Прикладная информатика» всех форм обучения.  Ростовский Государственный Экономический Университет «ринх», 2003

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

Другие похожие документы..