Первая страница
Наша команда
Контакты
О нас

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



Кафедра автоматизації проектування енергетичних процесів та систем

Скачати 174.37 Kb.

Кафедра автоматизації проектування енергетичних процесів та систем




Скачати 174.37 Kb.
Сторінка1/2
Дата конвертації10.06.2017
Розмір174.37 Kb.
ТипПротокол
  1   2

НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ "КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ"

ТЕПЛОЕНЕРГЕТИЧНИЙ ФАКУЛЬТЕТ


Кафедра автоматизації проектування енергетичних процесів та систем

Затверджую”


Декан теплоенергетичного факультету


__________ Є.М.Письменний

(підпис) (ініціали, прізвище)


«____»_______________ 2011р.

__________ Є.М.Письменний

(підпис) (ініціали, прізвище)

«____»_______________ 2012р.



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


КРЕДИТНОГО МОДУЛЯ

Теорія алгоритмів”, код НФ-04

для напряму підготовки 6.050101 комп’ютерні науки”

програма професійного спрямування “Інформаційні технології проектування ”

«Комп'ютерний еколого-економічний моніторинг»



денної форми навчання



Програму рекомендовано


кафедрою АПЕПС

Протокол № ___

від __ .__.2011 р.

Завідувач кафедри АПЕПС


_________С.О. Лук’яненко

Київ – 2011




  1. ЗАГАЛЬНІ ВІДОМОСТІ

Дисципліна “ Теорія алгоритмів ” - це одна з важливих складових дисциплін підготовки спеціалістів напряму «Комп'ютерні науки» тому, що знання та програмна реалізація алгоритмів є невід'ємною частиною діяльності інженера по створенню та застосуванню нових інформаційних технологій та програмуванню перспективних інноваційних програмних продуктів.
Застосунок Застосунок, застосовна програма або прикладна програма (англ. application, application software, app) - користувацька комп'ютерна програма, що дає змогу вирішувати конкретні прикладні задачі користувача.
Теорія алгоритмів (англ. Theory of computation) - окремий розділ математики, що вивчає загальні властивості алгоритмів. Виникла в 30-х роках 20 століття.
Інформаційні технології Інформаці́йні техноло́гії, ІТ (використовується також загальніший / вищий за ієрархією термін інформаційно-комунікаційні технології (Information and Communication Technologies, ICT) - сукупність методів, виробничих процесів і програмно-технічних засобів, інтегрованих з метою збирання, опрацювання, зберігання, розповсюдження, показу і використання інформації в інтересах її користувачів.

Зазначена дисципліна включена до циклу «Професійної та практичної підготовки».

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

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

Інформацíйна систéма (англ. Information system) - сукупність організаційних і технічних засобів для збереження та обробки інформації з метою забезпечення інформаційних потреб користувачів.
Математи́чне моделюва́ння (рос. моделирование математическое; англ. mathematical simulation, нім. mathematische Modellierung f) - метод дослідження процесів або явищ шляхом створення їхніх математичних моделей і дослідження цих моделей.


II. РОЗПОДІЛ НАВЧАЛЬНОГО ЧАСУ


Семестр/код

кредитного

модуля

Всього годин




Розподіл годин за видами занять

Кількість МКР

Вид індивідуального завдання

Семестрова атестація

Лекції

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

Семінарські заняття

Лабораторні роботи

Комп 'ютерний практикум

СРС

Всього

Утому числі

на виконання

індивідуального

завдання

3/НФ-04



144

36

-



-


-

18

90

-

1

-

Іспит


III. МЕТА І ЗАВДАННЯ ДИСЦИПЛІНИ


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

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

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

графіки, розпізнавання образів тощо.

Тео́рія розпізнава́ння о́бразів - розділ кібернетики, що розвиває теоретичні основи й методи класифікації і ідентифікації предметів, явищ, процесів, сигналів, ситуацій і т. п. об'єктів, які характеризуються кінцевим набором деяких властивостей і ознак.
Систе́мне програмува́ння (або програмування систем) - це вид програмування, який полягає у розробці програм, які взаємодіють з системним програмним забезпеченням (операційною системою), або апаратним забезпеченням комп'ютера.
Аналіз даних - розділ математики, що займається розробкою методів обробки даних незалежно від їх природи.
Прикладна математика - галузь математики, що розглядає застосування математичних знань в інших сферах діяльності. Прикладами такого застосування будуть: чисельні методи, математична фізика, математична хімія, лінійне програмування, оптимізація і дослідження операцій, моделювання суцільних середовищ (механіка суцільних середовищ), біоматематика і біоінформатика, теорія інформації, теорія ігор, теорія ймовірності і статистика, фінансова математика і теорія страхування, aктуарна математика,криптографія, а також комбінаторика і деякою мірою кінцева геометрія, теорія графів в додатку до мережевому плануванню, і багато в чому те, що називається інформатикою. У питанні про те, що є прикладною математикою, не можна скласти чітку логічну класифікацію. Математичні методи звичайно застосовуються до специфічного класу прикладних завдань шляхом складання математичної моделі системи.
Електро́нна обчи́слювальна маши́на (ЕОМ) - загальна назва для обчислювальних машин, що є електронними (починаючи з перших лампових машин, включаючи напівпровідникові тощо) на відміну від електромеханічних (на електричних реле тощо) та механічних обчислювальних машин.
Математи́чна ло́гіка - розділ математики, що вивчає мислення за допомогою числень, застосовуючи математичні методи та спеціальний апарат символів. Предметом математичної логіки є математичні теорії в цілому, які вивчаються за допомогою логіко-математичних мов.
Штучний інтелект Шту́чний інтеле́кт (англ. Artificial intelligence, AI) - розділ комп'ютерної лінгвістики та інформатики, що займається формалізацією проблем та завдань, які нагадують завдання, виконувані людиною.


В результаті вивчення дисципліни студент повинен
ЗНАТИ:

  • Алгоритми та їх властивості, прикладну теорію алгоритмів, теорію множин та обчислень і математичну логіку;
    Тео́рія множи́н - розділ математики, в якому вивчаються загальні властивості множин (переважно нескінченних). Виділення теорії множин в самостійний розділ математики відбулося на рубежі XIX і XX століть.


  • Алгоритмічні проблеми, що виникають при розв’язанні стандартних та нестандартних задач і засоби їх подолання


ВМІТИ:

  • програмувати алгоритми розв’язання задач перелічених типів

  • оцінювати точність одержаних результатів та використовувати математичні моделі та методи

IV.

Математи́чна моде́ль - система математичних співвідношень, які описують досліджуваний процес або явище. Математична модель має важливе значення для таких наук, як: економіка, екологія, соціологія, фізика, хімія, механіка, інформатика, біологія та ін.
ТЕМАТИЧНИЙ ПЛАН

IV.I. РОЗПОДІЛ НАВЧАЛЬНОГО ЧАСУ ЗА ТЕМАМИ

Найменування розділів, тем




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


Всього


Лекції

Практ. зан. (контр. раб.)

Комп’ютерний практикум


СРС


Розділ 1. Алгоритми та їх властивості

40


14




6


20

Тема 1.1. Алгоритми їх класифікація, типи та можливості

24

10




2

12

Тема 1.2. Алгоритми та алгоритмічні мови

16

4




4

8

Розділ 2. Прикладна теорія алгоритмів


42


16




6


20


Тема 2.1. Основні етапи розробки алгоритмів


30


12




4

14


Тема 2.2. Методи розробки алгоритмів

12

4




2

6


Контрольна робота з розділів 1,2

2







1

1

Розділ 3.

Теорія обчислень і математична логіка




25

6




6

13

Тема 3.1. Універсальні обчислювальні машини


13


4




2


7


Тема 3.2. Основи мат логіки

12


2




4


6


Підготовка до іспиту

36










36

Всього в 3 семестрі


144


36




18


90


Тема 1. Алгоритми та їх властивості

Неформальне поняття і визначення алгоритму. Алгоритм пошуку мінімуму в масиві як приклад алгоритму. Блок_схема алгоритму. Основні властивості алгоритмів: функціональність,

результативність, визначеність, елементарність. Алгоритмічні мови високого рівня. Оператор присвоювання. Умовний оператор. Оператор умовного та безумовного циклу. Виклик процедури. Чисельні алгоритми. Алгоритм Евкліда пошуку найбільшого спільного дільника двох чисел.

Алгоритм пошуку - алгоритм, котрий знаходить інформацію, що зберігається в певній структурі даних. Структури даних можуть бути реалізовані за допомогою зв'язаних списків, масивів, дерев пошуку, хеш-таблиць чи інших методів зберігання інформації.
Алгоритм Евкліда (також називається евклідів алгоритм) - ефективний метод обчислення найбільшого спільного дільника (НСД). Названий на честь грецького математика Евкліда, котрий описав його в книгах VII та X Начал.
Чи́сельні ме́тоди - методи наближеного або точного розв'язування задач чистої або прикладної математики, які ґрунтуються на побудові послідовності дій над скінченною множиною чисел. Основні вимоги до чисельних методів, щоб вони були стійкими та збіжними.
Мо́ва програмува́ння (англ. Programming language) - це штучна мова, створена для передачі команд машинам, зокрема комп'ютерам. Мови програмування використовуються для створення програм, котрі контролюють поведінку машин, та запису алгоритмів.
Найбі́льший спі́льний дільни́к (НСД) двох або більше невід'ємних цілих чисел - найбільше натуральне число, на яке ці числа діляться без остачі.
Доведення правильності та результативності алгоритму Евкліда. Алгоритм помнож на три і додай одиницю” і проблемні (не результативні) алгоритми. Алгоритм пошуку шляху в лабіринті (нитка Аріадни) як приклад алгоритму на графі. Операції зі стеком.

Література [1; 2; 4; 6]

Тема 2. Прикладна теорія алгоритмів

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

В програмуванні та комп'ютерних науках структу́ри да́них - це способи організації даних в комп'ютерах. Часто разом зі структурою даних пов'язується і специфічний перелік операцій, що можуть бути виконаними над даними, організованими в таку структуру.
Зображення дерев, графів і множин. Методи розробки алгоритмів: структурне програмування, рекурсія, обходи дерев, “поділяй і пануй”, балансування, динамічне програмування, програмування з відходом назад, метод “гілок і меж”, евристичні та наближені алгоритми.
Динамічне програмування - розділ математики, який присвячено теорії і методам розв'язання багатокрокових задач оптимального управління.
Структурне програмування - методологія програмування (модель конструювання програмного забезпечення) запропонована в 1970-х роках голландським науковцем Дейкстрою (Edsger Wybe Dijkstra), була розроблена та доповнена Ніклаусом Віртом.
Проходження повного циклу розробки на прикладі алгоритму пошуку кістякового дерева мінімальної ваги.
Кістякове дерево (англ. Spanning tree) зв'язаного неорієнтованого графа - ациклічний зв'язний підграф цього графа, який містить всі його вершини. Неформально кажучи, кістякове дерево складається з деякої підмножини ребер графа, таких, що рухаючись цими ребрами можна з будь-якої вершини графа потрапити до будь-якої іншої.
Алгоритми комп’ютерної математики. Алгоритми додавання і множення чисел. Аналіз та обчислення арифметичних і логічних виразів. Алгоритми на графах, пошук у глибину, пошук найкоротшого шляху. Сортування і пошук даних. Ігрові та комбінаторні алгоритми. Чисельні методи, обчислення дійсних констант і функцій. Ймовірнісні алгоритми. Алгоритми ідентифікації текстових рядків і скінченні автомати.



Література [1; 2; 4; 6]
Тема 3. Теорія обчислень і математична логіка

Універсальні обчислювальні моделі: машини Тьюрінга і Поста, алгоритми Маркова, машини з вільним доступом до пам’яті, рекурсивні функції. Формальне визначення алгоритму, тезис Черча. Масові алгоритмічні проблеми, які неможливо розв’язати.

Елементи математичної логіки, обчислення висловлень, поняття логічного висновку, недетерміновані алгоритми. Теорема про повноту для обчислення висловлювань.

Маши́на Тю́рінга - математичне поняття, введене для формального уточнення інтуїтивного поняття алгоритму. Названа на честь англійського математика Алана Тюрінга, який запропонував це поняття у 1936. Аналогічну конструкцію машини згодом і незалежно від Тюрінга ввів американський математик Еміль Пост.
Скінче́нний автома́т - особливий різновид автомату - абстракції, що використовується для описання шляху зміни стану об'єкта в залежності від поточного стану та інформації отриманої ззовні. Його особливістю є скінченність множини станів автомату.
Рекурсивні функції - клас функцій, введений як уточнення класу обчислюваних функцій. В математиці загальноприйнятою є теза про те, що клас функцій, для обчислення яких існують алгоритми, при найширшому розумінні алгоритму, збігається з класом рекурсивних функцій.
Чи́слення висло́влень (логіка висловлень, пропозиційна логіка, англ. propositional logic) - формальна система в математичній логіці, в якій формули, що відповідають висловленням, можуть утворюватись шляхом з'єднання простих висловлень із допомогою логічних операцій, та система правил виводу, які дозволяють визначати певні формули як «теореми» формальної системи.
Обчислення предикатів, формальна арифметика.
Формальна арифметика - це формулювання арифметики у вигляді формальної (аксіоматичної) системи. Мова формальної арифметики містить константу ‰ }} , числові змінні, символ рівності, функціональні символи + }} , × , (збільшення 1) і логічні зв'язки.
Теорема Геделя про неповноту

арифметики.



Література [3; 5; 6]
  1   2


Скачати 174.37 Kb.

  • Декан теплоенергетичного факультету
  • «____»_______________ 2012р.
  • Найменування розділів, тем