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

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


Смотрите также:
Программа и учебно-методические материалы по специальности 021100 ю риспруденция...
Материалы для подготовки к зачету по дисциплине «правоведение»...
Вопросы для подготовки к зачету (заочное обучение) для 1 курса заочного обучения по курсу...
Методическое пособие Организационно-методический раздел II. Основной раздел III...
Методические указания по самостоятельному изучению дисциплины «Контракты в международной...
Программа, вопросы к зачету ( для студентов всех специальностей) Общие указания и задания на...
Программа для подготовки к зачету теоретическая часть...
Методическое пособие составлено с учетом дистанционного обучения для подготовки специалистов...
План учебных занятий...
План учебных занятий...
Методические указания к изучению курса «Политология» для студентов всех специальностей и всех...
Программа для подготовки к зачету...



Загрузка...
скачать
МОСКОВСКАЯ ФИНАНСОВО-ЮРИДИЧЕСКАЯ АКАДЕМИЯ



Согласовано на 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 с.




Скачать 91,52 Kb.
оставить комментарий
Дата29.09.2011
Размер91,52 Kb.
ТипПрограмма для подготовки, Образовательные материалы
Добавить документ в свой блог или на сайт

Ваша оценка этого документа будет первой.
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

наверх