У вас вопросы?
У нас ответы:) SamZan.net

тематичні основи представлення знань Дніпропетровськ 2007

Работа добавлена на сайт samzan.net: 2016-03-13

Поможем написать учебную работу

Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.

Предоплата всего

от 25%

Подписываем

договор

Имя

Выберите тип работы:

Принимаю Политику конфиденциальности

Скидка 25% при заказе до 29.4.2025

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

Дніпропетровський національний університет

Факультет фізики, електроніки та комп’ютерних систем

Кафедра автоматизованих систем обробки інформації

„ЗАТВЕРДЖУЮ”

Декан ФФЕКС

____________ Долгов В.М.

___.____.200__р.

НАВЧАЛЬНА ПРОГРАМА

Теорія алгоритмів та математичні основи представлення знань

Дніпропетровськ − 2007

Теорія алгоритмів та математичні основи представлення знань. Програма навчальної дисципліни. — ДНУ, 2007. — 7 с.

Розробники: Вовк С.М., к.ф.-м.н., доцент, зав. кафедри

Рецензенти: (профільна кафедра іншого ВНЗ та два рецензенти: із установи, в якій викладається навчальний курс, та з іншого ВНЗ або НДІ)

Затверджено вченою радою факультету

Протокол № від __.___._____200_ р.

СТРУКТУРА ПРОГРАМИ НАВЧАЛЬНОЇ ДИСЦИПЛІНИ

„Теорія алгоритмів та математичні основи представлення знань”

ОПИС ПРЕДМЕТА НАВЧАЛЬНОЇ ДИСЦИПЛІНИ

Предмет: (вказати назву предмета дисципліни)

Курс:

Підготовка бакалаврів

Напрям,

спеціальність, освітньо-кваліфікаційний рівень

Характеристика навчальної дисципліни

Кількість кредитів, відповідних ЄСПК: 4,5

Модулів: 2

Змістових модулів: 4

Шифр та

назва напряму

0804 «Комп’ютерні науки»

Шифр та назва спеціальності: 6.080400 «Інформаційні управляючі системи та технології»

Освітньо-кваліфікаційний рівень: бакалавр

За вибором ВНЗ

Рік підготовки: 3

Семестр: 5

Лекції: 36

Практичні: 36

Самостійна робота: 90

Вид контролю: залік

МЕТА

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

ЗАВДАННЯ

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

У результаті вивчення дисципліни фахівець повинен знати основні положення теорії алгоритмів, основні положення проблеми представлення знань, методи створення ефективних чисельних та напівчисельних алгоритмів, моделі представлення знань та особливості їх застосування у галузі штучного інтелекту.

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

ЗМІСТ ДИСЦИПЛІНИ:

Вступ

МОДУЛЬ 1.

ЗМІСТОВИЙ МОДУЛЬ I. Основи теорії алгоритмів.

ТЕМА 1. Основні поняття теорії алгоритмів.

Предмет, мета та задачі курсу.

Основні поняття теорії алгоритмів. Дескриптивна та метрична сторони теорії алгоритмів. Визначення алгоритму. Властивості алгоритму. Алгоритм Евкліда. Поняття ефективного алгоритму (за Марковим).

ТЕМА 2. Доведення правильності довільного алгоритму.

Математична iндукцiя як метод доведення правильності довільного алгоритму. Застосування математичної iндукцiї для дослідження алгоритмів. Загальний метод доведення правильності довільного алгоритму.

ЗМІСТОВИЙ МОДУЛЬ ІІ. Формальні системи.

ТЕМА 1. Формальні системи на основі теорії множин.

Загальні поняття. Теорія множин як формальна система. Множина. Система множин та розбиття множини. Множина-степінь. Упорядкована множина (кортеж). Прямий добуток множин. Степені множин. Проекція множини.

Відповідності. Композиція відповідностей. Відображення. Функції, функціонали, оператори.

Відношення (бiнарнi, тернарнi, n-арнi). Властивості відношень. Операції над бінарними відношеннями.

Відношення еквiвалентностi. Класи еквiвалентностi та розбиття множини. Відношення порядку. Відношення строгого порядку. Відношення нестрогого порядку. Порiвняннiсть елементів множини. Відношення домінування.

ТЕМА 2. Формальні системи на основі теорії груп.

Поняття групи. Мультиплікативна група. Адитивна група. Групоїд, напівгрупа, моноїд, група. Приклади груп (доказово). Степені елементів групи. Порядок елемента групи. Підгрупа. Справжні та тривіальні підгрупи. Відтворюючі елементи групи. Циклічна група. Кільце. Поле. Просте поле GF(p), p – просте число.

ЗМІСТОВИЙ МОДУЛЬ ІІІ. Алгоритмічні системи.

ТЕМА 1. Абстрактні алгоритмічні системи.

Поняття абстрактного алфавіту. Визначення алфавітного оператора. Однозначні та багатозначні алфавiтнi оператори. Кодуючi відображення; приклади кодування. Умови обернення кодування. Відображення в стандартному алфавiтi. Спряжений алфавітний оператор.

Визначення алгоритму через алфавітний оператор. Способи подання алфавітного оператора (таблиця вiдповiдностей, скінченна система правил). Різниця в поняттях алгоритму та алфавітного оператора.

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

ТЕМА 2. Рекурсивні та обчислювальні функції. Теза Черча.

Загальне поняття рекурсивної та обчислювальної функції. Часткові функції та всюди визначені функції. Теза Черча.

Елементарні арифметичні функції (функції, що тотожно дорівнюють нулю, що повторюють значення своїх аргументів та функції безпосереднього слідування).

Операція суперпозиції. Операція примітивної рекурсії. Примітивно рекурсивні функції. Операція найменшого кореня. Частково-рекурсивні функції та загально-рекурсивнi функції та їх застосування в теорії алгоритмів.

ТЕМА 3. Машина Тьюрiнга-Поста.

Машина Поста. Машина Тьюрінга. Принцип роботи машини Тьюрінга та приклади розробки програм. Значення машини Тьюрiнга (розв’язнiсть/нерозв’язнiсть алгоритмів). Універсальна машина Тьюрінга.

Композиція (добуток, ітерація) машин Тьюрінга.

ТЕМА 4. Нормальні алгорифми А.А.Маркова.

Поняття елементарного оператора та елементарного розпiзнавача.

Узагальнений нормальний алгоритм. Приклади нормальних алгоритмів Маркова. Принцип нормалізації. Нормальні алгоритми у даному алфавитi та над даним алфавітом. Композиція алгоритмів Маркова. Універсальний алгоритм Маркова.

Алгоритмічно нерозв’язуванi проблеми. Теореми Геделя.

МОДУЛЬ 2.

ЗМІСТОВИЙ МОДУЛЬ IV. Представлення знань.

ТЕМА 1. Основні моделі представлення знань.

Проблеми штучного інтелекту (представлення знань, комп’ютерна логіка, комп’ютерна лінгвістика). Основні властивості знань (внутрішня інтерпретація, рекурсивна структура, взаємозв’язок одиниць, існування семантичного метричного простору, активність). Декларативний та процедурний опис знань. Моделі представлення знань. Семантичні мережі. Фреймові моделі представлення знань (фрейм, слот фрейму, фрейм-описувач, рольовий фрейм, фрейм-інтенсіонал, фрейм-екземпляр, тощо).

ТЕМА 2. Логічні моделі представлення знань та продукційні системи.

Логічні моделі представлення знань та їх опис (силогістика, логіка висловлень, числення предикатів; атомарні формули, замкнені формули). Індуктивні та дедуктивні моделі знань. Виведення теорем.

Продукції. Продукційні системи.

Сучасні системи здобуття знань (експертні системи, KDD-системи).

Практичні заняття

Тема 1. Словесне представлення алгоритмів.

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

Тема 2. Аналіз та розробка алгоритмів.

Аналіз алгоритмів (визначення усереднених характеристик алгоритму Евкліда, аналіз характеристик інших відомих алгоритмів). Синтез алгоритмів (побудова ефективних чисельних алгоритмів на прикладі алгоритмів швидкого дискретного перетворення Фур’є за модулем 2 з децимацією у часі та з децимацією за частотою).

Тема 3. Відповідності, відображення, відношення та їх властивості.

Загальний опис об’єктів, класів об’єктів, дій над ними та композиції дій через множини, кортежі, графи, операції, оператори, тощо.

Тема 4. Абстрактні алгоритмічні системи.

Алфавітний оператор (задачі на кодування та декодування інформації в абстрактному та стандартному двійковому алфавітах).

Тема 5. Рекурсивні та обчислювальні функції

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

Тема 6. Алгоритмічна система Маркова.

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

Тема 7. Алгоритмічна система Тюрінга-Поста.

Задачі на побудову машин Тюрінга, універсальних машин Тюрінга та композицій (добуток, ітерація) машин Тюрінга.

Тема 8. Абстрактні автомати.

Задачі на побудову абстрактних автоматів 1-го та 2-го роду.

Тема 9. Семантичні мережі.

Задачі на побудову семантичних мереж, наприклад, певних висловлювань.

Тема 10. Логічні моделі представлення знань

Задачі на логіку предикатів, замкнені формули, вивід теорем, побудову індуктивних та дедуктивних моделей.

СТРУКТУРА НАВЧАЛЬНОЇ ДИСЦИПЛІНИ

Тема	Кількість годин, відведених на:
	Лекції	Практичні заняття	Лабораторні заняття	Самостійну роботу
Модуль 1
Змістовий модуль I. Основи теорії алгоритмів.
Тема 1.	2	2	-	10
Тема 2.	2	2	-	10
Змістовий модуль II. Формальні системи.
Тема 1.	6	6	-	10
Тема 2.	6	6	-	10
Змістовий модуль ІІI. Алгоритмічні системи.
Тема 1.	2	4	-	5
Тема 2.	2	4	-	5
Тема 3.	4	4	-	10
Тема 4.	4	4	-	10
Модуль 2
Змістовий модуль IV. Представлення знань.
Тема 1.	4	2	-	10
Тема 2.	4	2	-	10
Усього	36	36	-	90

ЗАВДАННЯ ДЛЯ САМОСТІЙНОЇ РОБОТИ

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

Загальні вимоги до виконання розрахункових завдань.

Розрахункове завдання з навчальної дисципліні “Теорія алгоритмів та математичні основи представлення знань” виконується студентом протягом семестру у встановлений термін. Звіт про виконання завдання повинен містити:

Титульний аркуш з вказівкою теми завдання.
Аркуш зі змістом варіанту завдання.
Аркуші з текстом, де наводяться теоретичні відомості, пов'язані з постановкою задачі, методом її рішення, особливістю одержуваних результатів і т.д., а також певні математичні розрахунки, ілюстрації, графіки, схеми.
Аркуші з текстом, де приводяться результати розробки відповідного до завдання алгоритму і дається його опис на природній мові (словесний опис) та у вигляді блок-схеми чи іншої графічної схеми. Також приводяться результати аналізу розробленого алгоритму з вказівкою на область визначення та область значень розробленого алгоритму, його обчислювальної складності, результативності і ефективності застосування. Зазначений текст повинен завершуватися результатами чисельного моделювання на ЕОМ, що підтверджують правильність виконання завдання.
Аркуш з висновками.
Аркуш зі списком використаної літератури.

Загальний обсяг звіту повинен складати 10-15 сторінок друкованого тексту шрифтом Times New Roman 12 з міжрядковим інтервалом 1,5. Текст розроблених програм розміщується в додатку і приводиться у разі потреби.

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

МЕТОДИ НАВЧАННЯ: розв’язування практичних і розрахункових завдань з розробки алгоритмів, складання схем алгоритмів в різних алгоритмічних системах.

МЕТОДИ ОЦІНЮВАННЯ: поточне тестування, оцінка за розрахункову роботу.

МЕТОДИЧНЕ ЗАБЕЗПЕЧЕННЯ: електронний конспект лекцій; методичні матеріали з розробки розрахункових завдань.

ЛІТЕРАТУРА

Алферова З.В. Теория алгоритмов. – М.: Статистика, 1973. - 164 с.
Марков А.А., Нагорный Н.М. Теория алгорифмов. – М.: Наука. 1984. – 390 с.
Успенский В.А., Семенов А.Л. Теория алгоритмов: основные открытия и приложения. – М.: Наука, 1987. – 288 с.
Кнут Д. Искусство программирования для ЭВМ. Т.1. Основные алгоритмы. – М.: Мир, 1976. – 736 с.
Кнут Д. Искусство программирования для ЭВМ. Т.2. Получисленные алгоритмы. – М.: Мир, 1977 – 800 с.
Кнут Д. Искусство программирования для ЭВМ. Т.3. Сортировка и поиск. – М.: Мир, 1978. – 848 с.
Мальцев А.И. Алгоритмы и рекурсивные функции. – М.: Наука, 1986. – 368 с.
Пападимитриу Х.Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. –М.: Мир, 1985. – 510 с.
Свами М., Тхуласираман К. Графы, сети, алгоритмы. - М.: Мир, 1984. – 455 с.
Управление, информация, интеллект /Под ред. А.И.Берга и др. – М.: Мысль, 1976. – 383 с.
Хант Э. Искусственный интеллект. – М.: Мир, 1978. – 560 с.
Мендельсон Э. Введение в математическую логику. – М.: Наука, 1971. – 320 с.
Поспелов Г.С. Искусственный интеллект – основа новой информационной технологии. – М.: Наука, 1988. – 280 с.
Минский М. Фреймы для представления знаний. – М.: Энергия, 1979. – 151 с.
Представление знаний. Тематический выпуск журнала ТИИЭР. – М.: Мир, 1986. ТИИЭР, т.74, N 10. С. 3-179.
Кокорєва Л.В., Перевозчикова О.Л., Ющенко К.Л. Діалогові системи та представлення знань. – Київ: Наукова думка, 1992. – 448 с.
Маслов С.Ю. Теория дедуктивных систем и ее применение. – М.:Радио и связь,1986. – 135 с.
Уинстон П. Искусственный интеллект. – М.: Мир, 1980. –519 с.
Нильсон Н. Принципы искусственного интеллекта. – М.: Радио и связь, 1985. –373 с.
Гриценко В.И., Паньшин Б.Н. Информационная технология: вопросы развития и применения. – Киев: Наукова думка, 1988. – 272 с.
Сибуя М., Ямамото Т. Алгоритмы обработки данных. М.: Мир, 1986. – 218 с.
Данилевский Ю.Г., Петухов И.А., Шибанов В.С. Информационная технология в промышленности. – Л.: Машиностроение, 1988. – 282 с.

Автор програми Вовк С.М.

Завідувач кафедри Вовк С.М.

1. экономических дисциплин ИНФОРМАЦИОННАЯ ЭВРИСТИКА Учебнометодический комплекс Для
2. Кобзар Тараса Григоровича Шевченка.html
3. Курсовая работа- Вода очищена як розчинник в аптечній практиці
4. ВИЗАРДСОФТ предлагает пройти дистанционный курсы по направлению
5. і. О36.0 Резусізоімунізація при якій мати потребує надання медичної допомоги О36
6. Кориолан с участием Тома Хиддлстона и Марка Гэтисса
7. «Русскость» как топос «локального текста»- случай Мурома
8. основа жизни человека
9. Пояснительная записка Основной образовательной программы начального общего образования I
10. модерн Розчарування в життєвій дійсності та художньому реалістичному способі її відтворення спричини

Материалы собраны группой SamZan и находятся в свободном доступе