Робоча навчальна програма



Скачати 182.07 Kb.
Дата конвертації26.12.2016
Розмір182.07 Kb.


Київський національний університет імені Тараса Шевченка
Факультет кібернетики

Кафедра теорії та технології програмування
Укладач: Доктор фіз.-мат. наук, ст. н. сп. Буй Д.Б.



ТЕОРІЯ ОБЧИСЛЕНЬ

РОБОЧА НАВЧАЛЬНА ПРОГРАМА ДИСЦИПЛІНИ

для студентів спеціальності 6.040302 “Інформатика”

Затверджено

на засіданні кафедри теорії

та технології програмування

Протокол № 10

від “25” травня 2012 р.
Завідувач кафедри

Нікітченко М.С.
Затверджено

на засіданні Вченої Ради

факультету кібернетики

Протокол № 9

від “28” травня 2012 р.

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



Анісімов А.В

КИЇВ-2012


Робоча навчальна програма з дисципліни “Теорія обчислень”

Укладач: доктор фіз.-мат. наук, ст. н. сп. Буй Дмитро Борисович


Лектор: доктор фіз.-мат. наук, ст. н. сп. Буй Д.Б.



Погоджено

з науково-методичною комісією

“___” _______________ 2012 р.

Голова НМК факультету

Хусаїнов Д.Я

ВСТУП

Дисципліна “Теорія обчислень” є базовою нормативною дисципліною спеціальності “Інформатика”, що викладається на четвертому курсі в 7 семестрі в обсязі 4 кредитів - 144 години, з них 34 години лекційних, 34 години практичних занять і 76 годин самостійної роботи. Викладання дисципліни за результатами навчального семестру закінчується іспитом.



Мета і завдання. Мета курсу полягає у дослідженні теоретико-множинних конструкцій повного образу, обмеження, проекції, конфінальності, сумісності, ін’єктивності та операції узагальненого прямого добутку і узагальненого з’єднання множини функцій.

Предмет навчальної дисципліни “Теорія обчислень” включає в себе розгляд та дослідження базових теоретико-множинних конструкцій з метою застосування їх в теорії табличних баз даних.

Вимоги до знань та вмінь. Для засвоєння курсу необхідні знання основ елементарної математики, основи теорії алгебри, теорії алгоритмів та теорії баз даних. Студент повинен вміти виконувати доведення теоретичних тверджень (теорем), використовувати результати теорії алгебри, розробляти власні системи управління базами даних.

Місце в структурно-логічній схемі спеціальності. Нормативна навчальна дисципліна “Теорія обчислень” є складовою циклу професійної підготовки фахівців освітньо-кваліфікаційного рівня “бакалавр”, є базовою для засвоєння всіх інших курсів та спецкурсів програмістського спрямування.
Контроль знань здійснюється за модульно-рейтинговою системою.

Робота в семестрі розділена на 2 змістових модулі. Результати навчальної діяльності студентів оцінюються за 100-бальною шкалою.



Оцінювання за формами контролю.

Семестрова оцінка – 70 балів; із них модульні контрольні роботи – 30 балів, самостійні роботи – 30 балів, активна робота студентів – 10 балів. Підсумкова екзаменаційна робота – 30 балів. Максимальна підсумкова оцінка – 100 балів.



Порядок розрахунку загальної оцінки.

Модульні контрольні роботи – 30 = 15+15 балів.

Самостійні роботи – 30 = 2*10+1*10 балів.

За активну роботу студента на практичних заняттях та на самостійній роботі до семестрової оцінки може бути додано до 10 балів.

Якщо студент з поважних причин, які підтверджено документально, був відсутній при написанні модульної контрольної роботи, він має право на одне перескладання з можливістю отримання максимальної кількості балів.

Термін перескладання визначається викладачем.

Розрахунок балів по модулях:

Модуль 1: 40 балів (модульна контрольна робота – 15, дві самостійні роботи – 20, за активну роботу – 5).

Модуль 2: 30 балів (модульна контрольна робота – 15, самостійна робота – 10, за активну роботу – 5).

Студент допускається до складання іспиту, якщо кількість набраних за семестр балів не менше 30.


Підсумкова екзаменаційна робота – 30 балів.
Шкала оцінювання

100-бальна система

Національна шкала

90-100

Відмінно

5

85-89

Добре

4

75-84

65-74

Задовільно

3

60-64

35-59

не задовільно

2

1-34

не задовільно

2





ТЕМАТИЧНИЙ ПЛАН ЛЕКЦІЙ ТА ЛАБОРАТОРНИХ ЗАНЯТЬ


№ лекції

Назва лекції

Кількість годин

Лекції

Практ.занять

Сам. р-та

Змістовий модуль 1. Повний образ, обмеження, проекція, відношення сумісності. Відношення конфінальності та устрій сім’ї часткових функцій, впорядкованих за включенням графіків.

1

Повний образ множини відносно бінарного відношення. Основні властивості конструкції

2

2

4

2

Розповсюдження функцій з елементів на множини елементів за допомогою повного образу. Вкладення алгебри тризначної (сильної) логіки Кліні

2

2

4

3

Достатні умови дистрибутивності повного образу відносно перетину і різниці

2

2

4

4

Успадкування комутативності та асоціативності, критерії комутативності та асоціативності операції вигляду .

2

2

4

5

Обмеження. Властивості обмеження

2

2

4

6

Проекція та відношення сумісності

2

2

4

7

Відношення конфінальності та коіціальності множин

2

2

4

8

Устрій частково впорядкованої сім’ї часткових функцій

2

2

4

9

Індуктивні множини, повні частково впорядковані множини, когерентні множини

2

2

4

10

Умовно повні часткові впорядковані множини та повні піврешітки

2

2

4

Модульна контрольна робота 1








4

Змістовий модуль 2. Монотонність та неперервність функції. Теореми про нерухому точку. Ін’єктивні відношення та узагальнений прямий добуток.

11

Монотонність та неперервність функції

2

2

4

12

Теорема про нерухому точку неперервної функції на індукованій множині

2

2

4

13

Теорема про нерухому точку монотонної функції на повній решітці (теорема Тарського)

2

2

4

14

Критерій ін’єктивності відношень

2

2

4

15

Узагальнений прямий добуток

2

2

4

16

Властивості відношення сумісності

2

2

4

17

Операція узагальненого з’єднання множин функцій

2

2

4

Модульна контрольна робота 2








4




ВСЬОГО

34

34

76



Загальний обсяг годин – 144, у тому числі


Лекцій – 34 год.

Практичних занять – 34 год.

Самостійна робота – 76 год.

ТЕМАТИЧНО-ЗМІСТОВНА ЧАСТИНА КУРСУ


Змістовий модуль 1.

Повний образ, обмеження, проекція, відношення сумісності. Відношення конфінальності та устрій сім’ї часткових функцій, впорядкованих за включенням графіків.
Лекція 1. Повний образ множини відносно бінарного відношення. Основні властивості конструкції. – 2 год.

Вводиться означення повного образу множини відносно відношення U. Розглядаються основні властивості повного образу, а саме: монотонність за сукупністю аргументів, дистрибутивність відносно об’єднань, верхня оцінка повного образу перетину, повний образ відносно композиції відношень, критерій порожності повного образу, нижня та верхня оцінки повного образу різниці [3, 11].

Практичне заняття 1. Властивості конструкції повного образу. [3, 11] – 2 год.

Завдання для самостійної роботи. Доведення розглянутих властивостей [3]. – 4 год.
Лекція 2. Розповсюдження функцій з елементів на множини елементів за допомогою повного образу. Вкладення алгебри тризначної (сильної) логіки Кліні. – 2 год.

Вводиться – унарна тотальна операція на булеані універсуму та – бінарна часткова операція на D. Демонструється природність саме таких розповсюджень унарних та бінарних операцій з елементів на множини елементів, показується, як на такому шляху природно виникає відома сильна тризначна логіка Кліні [3].

Практичне заняття 2. Логічний звя’зок між властивостями ін’єктивності відношення та індукованої операції. [3]– 2 год.

Завдання для самостійної роботи. Доведення частини властивостей, розглянутих на практичному занятті. [3]. – 4 год.
Лекція 3. Достатні умови дистрибутивності повного образу відносно перетину і різниці. – 2 год.

Розглядається твердження про достатні умови дистрибутивності повного образу відносно перетину та різниці. А також окремими твердженнями наводяться критерії дистрибутивності повного образу відносно перетину та відносно різниці [3].

Практичне заняття 3. Детальний розгляд критеріїв дистрибутивності повного образу. [3]. 2 год.

Завдання для самостійної роботи. Доведення розглянутих тверджень[3]. 4 год.
Лекція 4. Успадкування комутативності та асоціативності, критерії комутативності та асоціативності операції вигляду . – 2 год.

Розглядається твердження про успадкування комутативності та асоціативності, критерії комутативності та асоціативності операції вигляду . Показується, що розширення , які виникають при розгляді тризначної логіки Кліні, являються комутативними та асоціативними, успадковуючи ці властивості від початкових операцій [3].

Практичне заняття 4. Зв'язок між властивостями вихідних та індукованих операцій на булеані. [3] – 2 год.

Завдання для самостійної роботи. Доведення розглянутих тверджень[3] – 4 год.
Лекція 5. Обмеження. Властивості обмеження. – 2 год.

Вводиться означення обмеження. Розглядаються властивості обмеження, а саме: монотонність обмеження, критерій порожності обмеження, збереження обмеження порожнього відношення та порожньої множини, дистрибутивність обмеження відносно об’єднань за обома аргументами, дистрибутивність обмеження відносно перетинів за обома аргументами, повний образ відносно обмеження [2, 3].

Практичне заняття 5. Властивості обмеження. [2, 3] – 2 год.

Завдання для самостійної роботи. Доведення деяких властивостей обмеження[2, 3] – 4 год.
Лекція 6. Проекція та відношення сумісності. – 2 год.

Розглядаються властивості проекції, а саме: верхня оцінка проекції перетину, проекції декартового добутку, критерій порожності проекції, верхня оцінка відношення в термінах декартового добутку проекцій, вираз проекції за другою компонентою через повний образ, достатня умова дистрибутивності проекції за першою компонентою відносно різниці функцій, монотонність проекції за першою та другою компонентами. Вводиться бінарне відношення сумісності. Розглядається критерій сумісності відношень [3, 11].

Практичне заняття 6. Властивості проекції. Критерії дистрибутивності проекції. Критерій сумісності відношень. [2, 3] – 2 год.

Завдання для самостійної роботи. Характеристична властивість відношення сумісності функцій.

[2, 3] – 4 год.


Лекція 7. Відношення конфінальності та коіціальності множин. – 2 год.

Вводяться відношення конфінальності та коіціальності. Розглядається твердження про властивості конфінальних підмножин. Показується, що відношення конфінальності та коіціальності частково впорядковують сім’ю дискретних множин [4, 11].

Практичне заняття 7. Відношення конфінальності та його основні властивості. [2, 3] – 2 год.

Завдання для самостійної роботи. Застосування відношення конфінальності в табличних базах даних. [2, 3]– 4 год.
Лекція 8. Устрій частково впорядкованої сім’ї часткових функцій. – 2 год.

Розглядається устрій частково впорядкованої множини часткових функцій, впорядкованих за включенням їхніх графіків. Вводиться поняття сумісної множини функцій. Розглядається критерій функціональності об’єднання двох функцій [4].

Практичне заняття 8. Критерій функціональності об’єднання двох функцій [4] – 2 год.

Завдання для самостійної роботи. Твердження про атоми частково впорядкованої множини часткових функцій [4]– 4 год.
Лекція 9. Індуктивні множини, повні частково впорядковані множини, когерентні множини. – 2 год.

Наводяться означення направленої та сумісної множини. Також вводяться поняття індуктивної множини, повної частково впорядкованої множини та когерентної множини. Розглядається взаємне положення когерентних та індуктивних множин [4].

Практичне заняття 9. Конфінальні ланцюги направлених множин та конфінальні підмножини ланцюгів. [4] – 2 год.

Завдання для самостійної роботи. Доведення частини твердження, розглянутого на практичному занятті. [4]– 4 год.
Лекція 10. Умовно повні часткові впорядковані множини та повні піврешітки. – 2 год.

Вводяться визначення умовно повної множини та повної піврешітки. Розглядається лема про зв'язок між верхніми гранями. Наводиться характеристична ознака повних піврешіток. Розглядається взаємне положення обмежених зверху та сумісних множин, а також взаємне положення когерентних множин та повних піврешіток [1, 4, 12].

Практичне заняття 10. Умовно повні часткові впорядковані множини та повні піврешітки. – 2 год.

Вводяться визначення умовно повної множини та повної піврешітки. Розглядається лема про зв'язок між верхніми гранями. Наводиться характеристична ознака повних піврешіток. Розглядається взаємне положення обмежених зверху та сумісних множин, а також взаємне положення когерентних множин та повних піврешіток [1, 4, 12].
Завдання для самостійної роботи. Характеристична ознака повних піврешіток, звя’зок з повними решітками. [1, 4, 12]– 4 год.

Завдання для самостійної роботи. Модульна контрольна робота. Звя’зок між точними гранями.

[1, 4, 12]– 4 год.


Контрольні запитання до змістового модуля  1.

  1. Означення повного образу множини.

  2. Тризначна логіка Клінні.

  3. Ін’єктивні та функціональні відношення.

  4. Обмеження відношення за множиною.

  5. Проекція відношення та його властивості.

  6. Відношення сумісності.

  7. Відношення конфінальності та коіціальності.

  8. Індуктивні множини, повні частково впорядковані множини, когерентні множини.

  9. Умовно повні часткові впорядковані множини.

  10. Повні піврешітки.



Змістовий модуль 2.

Монотонність та неперервність функції. Теореми про нерухому точку. Ін’єктивні відношення та узагальнений прямий добуток.
Лекція 11. Монотонність та неперервність функції. – 2 год.

Вводяться означення неперервності та монотонності функцій. Розглядаються властивості неперервних та монотонних функцій. Показується зв’язок між класами неперервних та монотонних функцій [5, 8, 9].

Практичне заняття 11. Зв’язок між класами неперервних та монотонних функцій. [5, 8, 9] – 2 год.

Завдання для самостійної роботи. Еквівалентні означення монотонних функцій. [5, 8, 9] – 4 год.
Лекція 12. Теорема про нерухому точку неперервної функції на індукованій множині. – 2 год.

Розглядається теорема про нерухому точку неперервної функції на індукованій множині [10].

Практичне заняття 12. Устрій множини нерухомих точок монотонної функції на індуктивній множині. [10]– 2 год.

Завдання для самостійної роботи. Доведення розглянутих тверджень. [10] – 4 год.
Лекція 13. Теорема про нерухому точку монотонної функції на повній решітці (теорема Тарського). – 2 год.

Розглядається теорема про нерухому точку монотонної функції на повній решітці [1, 10].

Практичне заняття 13. Устрій множини нерухомих точок монотонної функції на повній решітці

[1, 10]– 2 год.



Завдання для самостійної роботи. Доведення розглянутих тверджень. [1, 10] 4 год.
Лекція 14. Критерій ін’єктивності відношень. – 2 год.

Розглядаються два окремих твердження щодо критерію ін’єктивності відношень. Розглядається критерій ін’єктивності об’єднання ін’єктивних відношень, критерій ін’єктивності об’єднання ін’єктивних сумісних відношень та критерій ін’єктивності функцій [3].

Практичне заняття 14. Критерій ін’єктивності об’єднання ін’єктивних сумісних відношень. Критерій ін’єктивності об’єднання ін’єктивних сумісних функції. [3] – 2 год.

Завдання для самостійної роботи. Критерій ін’єктивності відношень в термінах обмежень.

[3] – 4 год.


Лекція 15. Узагальнений прямий добуток. – 2 год.

Вводиться поняття узагальненого прямого добутку. Розглядається розклад прямого добутку. Окремо розглядаються розклад прямого добутку для скінченної індексної множини. Наводяться властивості узагальненого прямого добутку [3].

Практичне заняття 15. Розклад прямого добутку. Властивості узагальненого прямого добутку.

[3]  2 год.



Завдання для самостійної роботи. Доведення розглянутих тверджень[3] – 4 год.
Лекція 16. Властивості відношення сумісності. – 2 год.

Вводиться визначення відношення сумісності. Розглядаються властивості відношення сумісності [3].

Практичне заняття 16. Доведення частини властивостей відношення сумісності. [3] – 2 год.

Завдання для самостійної роботи. Доведення решти властивостей відношення сумісності. [3] – 4 год.
Лекція 17. Операція узагальненого з’єднання множин функцій. – 2 год.

Розглядається властивості часткової функції об’єднання сумісних функцій. Вводиться означення узагальненого з’єднання та розглядаються властивості узагальненого з’єднання [3].
Практичне заняття 17. Операція узагальненого з’єднання множин функцій.– 2 год.

Розглядається властивості часткової функції об’єднання сумісних функцій. Вводиться означення узагальненого з’єднання та розглядаються властивості узагальненого з’єднання [3].

Завдання для самостійної роботи. Властивості узагальненого з’єднання. [3] – 4 год.

Завдання для самостійної роботи. Модульна контрольна робота. Доведення розглянутих властивостей. [3,4] – 4 год.

Контрольні запитання до змістового модуля  2.

  1. Монотонність функцій.

  2. Неперервність функцій.

  3. Теорема про нерухому точку неперервної функції на індукованій множині.

  4. Теорема Тарського.

  5. Критерій ін’єктивності відношень.

  6. Узагальнений прямий добуток.

  7. Властивості відношення сумісності.

  8. Операція узагальненого з’єднання множин функцій.

Перелік питань на іспит: VII семестр.
Основні теоретичні питання

  1. Індуктивні множини та п.ч.в.м. (означення, взаємне положення).

  2. Означення повного образу множини.

  3. Тризначна логіка Клінні.

  4. Ін’єктивні та функціональні відношення.

  5. Обмеження відношення за множиною.

  6. Проекція відношення та його властивості.

  7. Відношення сумісності.

  8. Відношення конфінальності та коіціальності.

  9. Індуктивні множини, повні частково впорядковані множини, когерентні множини.

  10. Умовно повні часткові впорядковані множини.

  11. Повні піврешітки.

  12. Монотонність та неперервність функцій.

  13. Теореми про нерухому точку.

  14. Критерій ін’єктивності відношень.

  15. Узагальнений прямий добуток.

  16. Властивості відношення сумісності.

  17. Операція узагальненого з’єднання множин функцій.



Рекомендована література


  1. Биркгоф Г. Теория решеток. – М.: Наука, 1983. – 566 с.

  2. Буй Д. Б., Брона Ю. И. Операторы замыкания в теории реляционных баз данных // Тезисы докладов XI Международной конференции по проблемам теоретической кибернетики. Под ред. С. В. Яблонского. – Ульяновск: Изд-во СВНЦ, 1996. – С. 29-30.

  3. Буй Д.Б. Властивості теоретико-множинних конструкцій повного образу та обмеження / Д.Б. Буй, Н.Д. Кахута // Вісник Київського університету. Сер.: фіз.-мат. науки. – 2005. – Вип. 2. –С. 232-240.

  4. Буй Д.Б. Властивості відношення конфінальності та устрій множини часткових функцій / Д.Б. Буй, Н.Д. Кахута // Вісник Київського університету. Сер.: фіз.-мат. науки. – 2006. – Вип. 2. – С. 125-135.

  5. Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. – М.: Мир, 1983. – 256 с.

  6. Клини С. К. Введение в метаматематику. – М.: ИЛ, 1957. – 526 с.

  7. Мальцев А. И. Алгебраические системы. – М.: Наука, 1969. – 392 с.

  8. Мальцев А. И. Алгоритмы и рекурсивные функции. – М.: Наука, 1965. – 391 с.

  9. Мальцев А. И. Алгоритмы и рекурсивные функции. – М.: Наука, 1986. – 367 с.

  10. Манна З. Теория неподвижной точки программ // Киб. сб. Нов. сер. – М.: Мир, 1978. – Вып. 15. – С. 38-100.

  11. Риге Ж. Бинарные отношения, замыкания, соответствия Галуа // Киб. сб.: Сб. переводов. – М.: ИЛ, 1963. – Вып. 7. – С. 129-185.

  12. Скорняков Л. А. Элементы теории структур. – М.: Наука, 1982. – 159 с.






База даних захищена авторським правом ©lecture.in.ua 2016
звернутися до адміністрації

    Головна сторінка