Темы, выносимые на самостоятельное изучение
МИНОБРНАУКИ РОССИИ
Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
«Тульский государственный университет»
Кафедра «Автоматика и телемеханика»
Методические указания
По САМОСТОЯТЕЛЬНОЙ РАБОТЕ СТУДЕНТА
по дисциплине
Математика
Направление подготовки: 230100 «Информатика и вычислительная техника»
Профиль : «Программное обеспечение средств вычислительной техники и автоматизированных систем»
Направление подготовки: 230400 «Информационные системы и технологии»
Профиль : «Информационные системы»
Направление подготовки: 220400 «Управление в технических системах»
Профиль : «Управление и информатика в технических системах»
Формы обучения: очная
Тула 2012 г.
Методические указания по СРС составлены доцентом, к.ф.-м.н. Красоткиной О.В. и обсуждены на заседании кафедры автоматики и телемеханики факультета кибернетики,
протокол № 6 от " 31 " января 2012 г.
Зав. кафедрой________________А.А. Фомичев
Методические указания по ККР (РГР, СРС, КРЗ, ТР, проведению индивидуальных занятий с магистрантами) пересмотрены и утверждены на заседании кафедры автоматики и телемеханики факультета кибернетики,
протокол №___ от "___"____________ 20___ г.
Зав. кафедрой________________А.А. Фомичев
Содержание
1 Цель и задачи самостоятельной работы......................................................... 4
2. Работа по самостоятельному изучению отдельных тем................................ 4
3. Методические указания по работе над рефератом...................................... 13
Цель и задачи самостоятельной работы
Целью самостоятельной работы является изучение тем, не рассмотренных в течение практических занятий (29 час), а также подготовка к текущим аттестациям (28 час).
Работа по самостоятельному изучению отдельных тем
Трудоемкость самостоятельного изучения тем в четвертом семестре составляет 29 часов.
Темы, выносимые на самостоятельное изучение, их трудоемкость и контрольные вопросы по каждой из них приведены ниже
Темы, выносимые на самостоятельное изучение
Номера тем проставлены согласно рабочей программе по данной дисциплине.
Тема 1.3 Метод дедуктивного вывода
Общая трудоемкость 7 часа, из них 2 часа – аудиторные занятия, 5 ч - самостоятельные занятия.
В ходе аудиторных занятий рассматриваются аксиоматика и правила вывода исчисления высказываний, рассматривается процедура дедуктивного вывода с примерами. В ходе самостоятельной работы студенты тренируются в решении задач на применение дедуктивного вывода для доказательства следования заключения из комплекса посылок в логике высказываний [1] ., разд 4.3
Задачи для самоконтроля
Составить таблицу истинности. Доказать истинность заключения методом дедукции и нарисовать граф дедуктивного вывода.
| Вариант | Доказать истинность заключения |
| 1. | (B®A); (B®(ùAÚC)) |¾ (B®(ùBÚC)) |
| (ùAÚB); (CÚùB) |¾ (A®C)Ú(A®ùC) | |
| 3. | (ùAÚùB) |¾ (ù B®A)Ú(А®С) |
| 4. | (A®B) |¾ ((ùBÚC)®(ùAÚC)) |
| (A®B); (C®D) |¾ (A&C®B&D) | |
| (A®B); (ù A®B) |¾ BÚ (A®C) | |
| 7. | (B®A); (B®(A®C)) |¾ (B®C) |
| 8. | (A®B) |¾ (ùC®A)®( ùC®B) |
| (A®B); (A®(ùBÚC)) |¾ (A®C) | |
| 10. | (A&BÚùA&ùB) |¾ (A®C)«(B®C) |
| 11. | (A®(B®C));(A®B);A |¾ C |
| 12. | (A&B®C) |¾ (A®(B®C)) |
| 13. | (B®(A®C)); (B®A) |¾ (B®(B®C)) |
| (A&BÚC&D); (A®ù A) |¾ C | |
| 15. | (A®(B®C)); (ù DÚA);B |¾ (D®C) |
| 16. | (AÚB); (A®C); (B®D) |¾ CÚD |
| 17. | (A®B); (C®B); (D®(AÚC)); D |¾ B |
| 18. | (A®B); (B®C); (C®D) |¾ (A®D) |
| (B®(A®C)); (B®A) |¾ (B®(B®C)) | |
| (A®(C®B)); (ù DÚA); C; D |¾ D®B | |
| (A«B) |¾ (CÚA)«(CÚB) | |
| 22. | A; (A®B) |¾ (C&A®B&C) |
| (A®B); ù (BÚC) |¾ ù A | |
| (A®(B®C)); (ù DÚA);B |¾ (D®C) | |
| (AÚC); (A®B);A |¾ (AÚC)®(BÚC) | |
| (A®(B®C)); (A®B) |¾ (A®C) | |
| (ù AÚB); (C®ù B) |¾ A®ù C | |
| C; (A®B) |¾ ((C®A)®(C®B)) | |
| (A®(B®C)) |¾ ((A&B)® C) | |
| (A®B) |¾ A&C®B&C | |
| 31. | (A®(B®C)); (ù DÚA);B |¾ (D®C) |
| 32. | (A®B); (B®C); (C®D) |¾ (A®D) |
| 33. | (B® (A®C)); (B®A) |¾ (B®C) |
| 34. | (A®B) |¾ (A&C)®B&C) |
| 35. | (B®(A®C)); (B®A) |¾ (B®(B®C)) |
| 36. | (A®(B®C); (A®B) |¾ (A®(A®C)) |
| 37. | (B®(A®C)); (B®A) |¾ (B®(B®C) |
| 38. | (A®C); (B®A) |¾ (ù C&B) |
| 39. | (A®B); (C®B); (D®(AÚC)); D |¾ B |
| 40. | (A®B)|¾ (ù AÚù CÚB&C) |
| 41. | (B®(A®C)); (B®A) |¾ (B®(B®C)) |
| 42. | (A&B®C) |¾ (A®(B®C)) |
| (A®(B®C)); (ù DÚA);B |¾ (D®C) | |
| 44. | (A®(B®C));(A®B);A |¾ C |
| 45. | (A®(B®C)); (A®B) |¾ (A®C) |
| 46. | (A®(B®C)) |¾ (B®(A®C)) |
| 47. | (A®B); (B®C); (C®D) |¾ (A®D) |
| 48. | (A®B) |¾ (AÚC)®(BÚC) |
| 49. | (A®B); B |¾ ù A&ù CÚBÚC |
| 50. | (A«B) |¾ (A®C)«(B®C) |
Тема 1.1.5 Совершенные нормальные формы формул логики высказываний
Общая трудоемкость 7 часа, из них 2 часа – аудиторные занятия, 5 ч - самостоятельные занятия.
На аудиторных занятиях студенты изучают преобразование формул логики высказываний к совершенному виду, учатся записывать совершенные формулы по заданной таблице истинности. В ходе самостоятельной работы студенты тренируются в решении задач на построение совершенных формул логики высказываний по таблице истинности, проектируют схему цифрового устройства по полученной совершенной нормальной форме, отличающуюся минимумом. минимальным числом логических элементов [1] параграф 13.
Задачи для самоконтроля по теме 1.1.5
Задан алгоритм функционирования некоторого комбинационного цифрового устройства в виде связи между входными и выходными сигналами. Эта связь представлена таблицей истинности (задан последний столбец таблицы истинности, первые три столбца значений переменных имеют стандартный вид
| X | y | z |
Спроектируйте схему этого цифрового устройства, отличающуюся минимумом. минимальным числом логических элементов.
| № варианта | F(X,Y,Z) | |||||||
Тема 2.1.4 Перевод выражений логики предикатов в клаузальную форму.
Общая трудоемкость 11 часа, из них 6 час – аудиторные занятия, 5 ч - самостоятельные занятия.
В ходе аудиторных занятий студенты изучают алгебру предикатов, процесс получения предваренной, замкнутой, сколемовской и клаузальных нормальных форм логики предикатов [1], глава IV, параграф 7.
Задачи для самоконтроля по теме 2.1.4:
. Найти предваренную и клаузальную нормальные формы формул.
| Вариант | Формула |
| "x(A(x)®ù B(y))®$y(B(y)®ù A(x)) | |
| "x(ù A(x)®$x(ù C(x)))®"x((C(x)®A(x)) | |
| "x(A(x)®$x(B(x)))®$y(ù A(x)Úù C(y)ÚC(y)&B(x)) | |
| "x(A(x)®$x(B(y)))®$x(ù A(x)®ù B(y)) | |
| "x(A(x)®B(y))&"y(A(x)®(B(y)®C(z))®$z(A(x)®C(z)) | |
| "x(A(x)®$y(B(y)®C(z)))®"z(A(x)&B(y)®C(z)) | |
| "x(A(x)®B(z))&"y(C(y)®A(x))®$z(C(y)®B(z)) | |
| "x(A(x)®B(y))®"y((C(y)ÚA(x))®(C(y)Ú$y(B(y))) | |
| "x(A(x)®B(y))&"y(A(x)®(B(y)®C(z)))®(A(x)®$z(C(z))) | |
| "x(A(x)®B(y)&A(x)®"y(B(y)®C(z)))®(A(x)®$z(C(z))) | |
| "x(A(x)®$z(B(y)®C(z)))®"y(B(y)®(A(x)®C(z))) | |
| ("x(A(x))®$x(B(x)))®"z((B(x)®C(z))®(A(x)®C(z))) | |
| ($x(ù A(x))®"x(ù B(x)))®(ù B(x)ÚA(x)) | |
| ("x(A(x)))®("x(B(x)))®$y(C(y)&A(x)®C(y)&B(x)) | |
| "ч(ù Ф(ч)®$н(И(н)))®(ù И(н)®Ф(ч)) | |
| ("x(B(x))®$x(A(x)))&$y((A(x)®C(y))®(ù C(y)&B(x))) | |
| "x(ù A(x)®$y(B(y)))®(B(y)ÚA(x)) | |
| "x(ù A(x)®$y(ù B(y)))®(B(y)®A(x)) | |
| "x(A(x)®B(x))&$y(B(x)®C(y)&$z(C(y)®D(z))) | |
| ("x(A(x)®B(x))&"z(C(z)®A(x)))®$y(C(z)®B(y)) | |
| ("x(B(x)®"y(A(y)))&("y(B(y)®(A(x)®C(z))))®$z(C(z)) | |
| "x(B(x))®$y(A(y)®B(x)) | |
| "x(A(x)®B(x))®("y(C(y)®A(x))®$z(C(z)®B(x))) | |
| "x(B(x)®A(y))&(B(x)®"y(A(y)®C(z)))®$z(C(z))) | |
| $x(A(x)®B(z))®$y(C(y)ÚA(x)®"z(C(y)ÚB(z))) | |
| ("x(B(x))®$x(A(x)))&(A(y)®$yC(y))®(ù A(x)ÚC(y)) | |
| ("x(A(x))®$x(B(x)))®$y((A(x)ÚC(y))®(B(x)ÚC(y))) | |
| $x(A(x)®"y(B(y)))&(ù A(x)®"y(B(y)))®B(y) | |
| "x(A(x)®$y(B(y)))&(ù A(x)®B(x))®B(x) | |
| "x(ù A(x))®(A(x)®$y(B(y))) | |
| ($x(B(x))®"x(A(x)))&(ù B(x)®A(x))®A(x) | |
| ("x(B(x))®$x(C(x)))®(A(y)&B(x)®A(y)&C(x)) | |
| $ч(Ф(ч)®И(н))®"н"я((С(я)®Ф(ч))®(С(я)®И(н))) | |
| ("x(A(x))®$x(C(x)))&"y(C(x)®B(y))®(A(x)®B(y)) | |
| "x(A(x))®$y(B(y))&"y(C(y)®$xD(x))®(A(x)&C(y)) &D(y)) | |
| "x(A(x))®(ù A(x)®$y(B(y))) | |
| "x(B(x))®$y(A(y)®B(x)) | |
| "x(B(x)®"y(A(y)))&"y(B(y)®(A(x)®C(z)))®$z(B(z) C(z)) | |
| "x(B(x)®A(y))&(B(x)®"y(A(y)®C(z)))®$z(B(x)®C(z)) | |
| "x(A(x)®B(x))®"y((C(y)®A(x))®(C(y)®B(x))) | |
| ("x(ù A(x)®$y(ù C(y)))®(C(x)®A(x)) | |
| "x(A(x)®ù B(y))®$y(B(y)®ù A(x)) | |
| $x(A(x)®B(z))®$y((C(y)ÚA(x))®"z(C(y)ÚB(z))) | |
| "x(A(x)®B(y))&"z(C(z)®A(x))®$y(C(z)®B(y)) | |
| "ч(Ф(ч)®И(ч))&$н(И(ч)®С(н))&$я(С(н)®В(я))) | |
| "x(ù A(x)®$y(ù B(y)))®(B(x)®A(x)) | |
| "x(ù A(x)®$x(B(x)))®(B(x)ÚA(x)) | |
| ("x(B(x)®$y(A(y))))&$y(A(x)®C(y))®ù C(y)&B(x) | |
| ("x(ù A(x)®$y(B(y))))®(ù B(x)®A(x)) | |
| "x(A(x)®B(y))&"y(A(x)®(B(y)®C(z)))®$z(A(x)®C(z)) |
Тема 4.1 Вычислительная сложность алгоритмов
Общая трудоемкость 9 час, в том числе аудиторная работа 2 часа, самостоятельная работа 7 часов .
В ходе аудиторных студенты знакомятся с понятием вычислительной сложности алгоритмов, ее видами и способами расчета. В ходе самостоятельной работы студенты учатся вычислять временную и емкостную вычислительную сложность в соответствии с равномерным и логарифмическим весовым критериями [1].
Задачи для самоконтроля по теме 4:1
Определить временную и емкостную сложность следующего алгоритма при равномерном и логарифмическом весовых критериях:
1. Алгоритм метода поиска перебором в квадратной матрице.
2. Алгоритм метода бинарного поиска в квадратной матрице.
3. Алгоритм метода сортировки вставками для одномерного массива.
4. Алгоритм метода сортировки Хоара для одномерного массива.
5. Алгоритм метода сортировки слиянием для одномерного массива.
6. Алгоритм метода сортировки расческой для одномерного массива.
7. Алгоритм метода сортировки Шелла для одномерного массива.
8. Алгоритм построения таблицы истинности логической функции трёх переменных (на примере конкретной функции).
9. Алгоритм построения таблицы значений функции (на примере конкретной функции).
10. Алгоритм поиска минимального элемента в матрице.
11. Алгоритм вычисления суммы элементов главной диагонали матрицы.
12. Алгоритм суммирования элементов квадратной матрицы, расположенных в нечётных строках.
13. Алгоритм умножения двух матриц.
14. Алгоритм вычисления суммы элементов матрицы, выделенных на рисунке символом х (m = n):
15. Алгоритм вычисления суммы элементов матрицы, выделенных на рисунке символом х (m = n):
16. Алгоритм поворота квадратной матрицы против часовой стрелки на 90 градусов.
17. Алгоритм нахождения одного из седловых элементов квадратной матрицы (наибольший в строке и наименьший в столбце).
18. Алгоритм проверки, является ли матрица магическим квадратом (суммы элементов всех строк и столбцов одинаковы).
19. Алгоритм нахождения суммы последних элементов каждой строки и каждого столбца квадратной матрицы.
20. Алгоритм перестановки левой и правой половин квадратной матрицы (размер n матрицы является четным числом).
Тема 3.4. Машины Тьюринга.
Общая трудоемкость 7 часов в том числе аудиторные занятия 2 часа, самостоятельная работа 5 часов.
В ходе аудиторных занятий студенты изучают понятие машины Тьюринга, способы построения машин Тьюринга для решения алгоритмических задач, в ходе самостоятельной работы студенты учатся составлять программу машины Тьюринга в заданном алфавите и показsdfnm ее работоспособность на примерах. В ходе самостоятельной работы студенты тренируются в составлении программ машины Тьюринга [1], Дополнительные главы. Глава 1.
Задачи для самоконтроля по теме 2.5:
Составить программу машины Тьюринга в заданном алфавите и показать ее работоспособность на примере
1 A={a,b,c}. Приписать слева к слову P символ b (P → bP).
2 A={a,b,c}. Приписать справа к слову P символы bc (P → Pbc).
3 A={a,b,c}. Заменить на a каждый второй символ в слове P.
4 A={a,b,c}. Оставить в слове P только первый символ (пустое слово не
менять).
5 A={a,b,c}. Оставить в слове P только последний символ (пустое слово не
менять).
6 A={a,b,c}. Определить, является ли P словом ab. Ответ (выходное слово):
слово ab, если является, или пустое слово иначе.
7 A={a,b,c}. Определить, входит ли в слово P символ a. Ответ: слово из
одного символа a (да, входит) или пустое слово (нет).
8 A={a,b,c}. Если в слово P не входит символ a, то заменить в P все символы
b на с, иначе в качестве ответа выдать слово из одного символа a.
9 A={a,b,0,1}. Определить, является ли слово P идентификатором (непустым
словом, начинающимся с буквы). Ответ: слово a (да) или пустое слово (нет).
10 A={a,b,0,1}. Определить, является ли слово P записью числа в двоичной
системе счисления (непустым словом, состоящем только из цифр 0 и 1). Ответ:
слово 1 (да) или слово 0.
11 A={0,1}. Считая непустое слово P записью двоичного числа, удалить из
него незначащие нули, если такие есть.
12 A={0,1}. Для непустого слова P определить, является ли оно записью
степени двойки (1, 2, 4, 8, …) в двоичной системе счисления. Ответ: слово 1
(является) или слово 0.
13 A={0,1,2,3}. Считая непустое слово P записью числа в четверичной
системе счисления, определить, является оно чётным числом или нет. Ответ: 1
(да) или 0.
14 A={0,1}. Считая непустое слово P записью числа в двоичной системе, полу-
чить двоичное число, равное учетверенному числу P (например: 101 → 10100).
15 A={0,1}. Считая непустое слово P записью числа в двоичной системе,
получить двоичное число, равное неполному частному от деления числа P на 2
(например: 1011 → 101).
16 A={a,b,c}. Если P – слово чётной длины (0, 2, 4, …), то выдать ответ a,
иначе – пустое слово.
17 A={0,1,2}. Считая непустое слово P записью числа в троичной системе
счисления, определить, является оно чётным числом или нет. Ответ: 1 (да) или 0.
(Замечание: в чётном троичном числе должно быть чётное количество цифр )
18 A={a,b,c}. Пусть P имеет нечётную длину. Оставить в P только средний
символ.
19 A={a,b,c}. Если слово P имеет чётную длину, то оставить в нём только
левую половину.
20 A={a,b,c}. Приписать слева к непустому слову P его первый символ.
21 A={a,b}. Для непустого слова P определить, входит ли в него ещё раз его
первый символ. Ответ: a (да) или пустое слово.
22 A={a,b}. В непустом слове P поменять местами его первый и последний
символы.
23 A={a,b}. Определить, является P палиндромом (перевёртышем, симмет-
ричным словом) или нет. Ответ: a (да) или пустое слово.
24 A={a,b}. Заменить в P каждое вхождение a на bb.
25 A={a,b,c}. Заменить в P каждое вхождение ab на c.
26 A={a,b}. Удвоить слово P (например: abb → abbabb).
27 A={a,b}. Удвоить каждый символ слова P (например: bab → bbaabb).
28 A={a,b}. Перевернуть слово P (например: abb → bba).
29 A={0,1}. Считая непустое слово P записью двоичного числа, получить это
же число, но в четверичной системе. (Замечание: учесть, что в двоичном числе
может быть нечётное количество цифр.)
30 A={0,1,2,3}. Считая непустое слово P записью числа в четверичной
системе счисления, получить запись этого числа в двоичной системе.
31 A={0,1,2}. Считая непустое слово P записью положительного числа в
троичной системе счисления, уменьшить это число на __
СПИСОК РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ ПО РАЗДЕЛУ 2
1. Новиков, Ф. А. Дискретная математика для программистов : учеб. пособие для вузов / Ф. А. Новиков .— 3-е изд. — М. [и др.] : Питер, 2009 .— 384 с. : ил. — (Учебник для вузов) .— Библиогр.: с. 368-369 .— Предм. указ.: с. 370-383 .— ISBN 978-5-91180-759-7 ((в пер.))
2. Лихтарников Л. M., Сукачева Т. Г. Математическая логика. Курс лекций. Задачник-практикум и решения. Серия "Учебники для вузов. Специальная литература" / Оформление обложки С. Л. Шапиро, А. А. Олексенко. — СПб.: Издательство "Лань", 1999. — 288 с.
3. Ахо, А. Построение и анализ вычислительных алгоритмов / А.Ахо,Д.Хопкрофт,Дж.Ульман;Пер.с англ.А.О.Слисенко;Под ред.Ю.В.Матиясевича .— М. : Мир, 1979 .— 536с. — Библиогр.в конце кн
4. Колмогоров А.Н., Драгалин А.Г. Математическая логика. Серия "Классический университетский учебник". Изд.3, стереот.2006. Твердый переплет. 240 с. ISBN 5-484-00520-5