Теоретичні основи та методи розробки
інформаційних систем


Галузь знань: 12 Інформаційні технології
Спеціальність: 121 Інженерія програмного забезпечення
Освітня програма: Програмне забезпечення систем

Викладачі: Викладається: в 1-му семестрі магістратури.
Загальний обсяг: 126 год, з яких:
  • Лекції – 34 год.
  • Лабораторні роботи – 17 год.
  • Самостійна робота – 75 год.

Мета та завдання дисципліни

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

Предмет дисципліни

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

В результаті вивчення навчальної дисципліни студент повинен
знати:
  • основні етапи розробки програмного забезпечення,
  • методи аналізу складності програмного забезпечення,
  • методи верифікації програмного забезпечення,
  • методи оптимізації програмного забезпечення.
та вміти:
  • виконувати аналіз проблеми, що виникає,
  • формулювати постановку задачі,
  • будувати математичну модель предметної області, до якої відноситься задача,
  • аналізувати математичну модель,
  • будувати алгоритм розв'язання задачі.

Вимоги до знань та вмінь

Для вивчення курсу Теоретичні основи та методи розробки інформаційних систем студент повинен повинен прослухати наступні курси:
  • основи програмування,
  • дискретна математика,
  • алгебра та геометрія,
  • загальна алгебра,
  • алгоритми та складність,
  • теорія алгоритмів та математична логіка,
  • програмування з обмеженнями.
та повинен вміти:
  • оцінювати складність алгоритмів та програм,
  • праціювати з формальними логічними мовами,
  • використовувати основні алгоритмічні системи,
  • програмувати на мовах C++/Java.

Зв'язок з іншими дисциплінами.

Навчальна дисципліна Теоретичні основи та методи розробки інформаційних систем є базовою для вивчення таких спеціальних дисциплін як:
  • Формальні методи побудови програм.
  • Автоматизація пошуку доведень.
  • Проектування мультиагентних систем.
  • Моделе-орієнтована побудова програмних систем.

Програма курсу

Змістовий модуль 1: Сучасний стан методів розробки програмного забезпечення: повний процес розробки.

Тема 1: Предмет курсу та проблеми, які розглядатимуться
  • Поняття алгоритму та та його уточнення у вигляді алгоритмічної системи.
  • Частково рекурсивні функції та машини Тюрінга.
Тема 2: Складність алгоритмів і програм: асимптотика
  • Асимптотичне порівняння функцій.
  • Теорема майстрів.
  • Приклади застосування теореми та оцінок росту функцій.
  • Основні етапи процесу проектування алгоритмів.
Тема 3: Характеристика основних етапів проектування
  • Побудова математичної моделі.
  • Аналіз моделі.
  • Розробка алгоритму.
  • Обґрунтування та оцінка складності.
  • Тестування та відлагодження програмного забезпечення.
Тема 4: Обґрунтування та якісна оцінка
  • Складність у моделі Тьюрінга.
  • Складність у арефметичній моделі.
  • Основні проблеми, можливості автоматизації.
Тема 5: Найпростіші методи розробки
  • Рекурентні співвідношення та рекурсивні означення.
  • Приклади розробки простих програм чисельних та символьних обчислень.
Тема 6: Основні методи розробки
  • Метод «поділяй та владарюй». Приклади застосування.
  • Динамічне програмування. Приклади застосування та порівняння з попереднім методом.
Тема 7: Жадібний вибір: теоретичні підстави
  • Жадібні алгоритми та теоретичні основи цих алгоритмів.
  • Приклади застосування.
  • Метод пошуку з поверненням.
  • Приклади застосування.
  • Метод структурного проектування, програмування та обґрунтування.
  • Приклади застосування.
Тема 8: Метод пошуку з поверненням (backtracking)
  • Пошук з поверненням.
  • Метод структурного проектування, програмування та обґрунтування.
  • Приклади застосування.
Модульна контрольна робота 1

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

Тема 9: Алгоритми типу поділяй та владарюй: загальна схема та її аналіз.
  • Приклади застосування:
    • сортування злиттям,
    • уніфікація термів в абсолютно вільній алгебрі.
Тема 10: Динамічне програмування та жадібний вибір
  • Чисельні алгоритми:
    • обчислення значень поліномів,
    • операцій на матрицях
    • розв'язання системи лінійних рівнянь.
Тема 11: Алгоритми текстової ідентифікації
  • Стандартний алгоритм порівняння із зразком.
  • Алгорими Ахо-Корасіка та Кнута-Морріса-Пратта.
  • Паралельні алгоритми та методи їх аналізу.
  • Моделі паралельних обчислень.
  • Приклад множення матриць в моделі CRCW PRAM.
Тема 12: Паралельні алгоритми та методи їх аналізу
  • Моделі паралельних обчислень: RAM, PRAM.
  • Приклад множення матриць в моделі CRCW PRAM.
Тема 13: Методи верифікації
  • Верифікація програм: загальна характеристика підходів.
  • Програмні динамічні логіки.
  • Методи потокового аналізу та їх застосування. Приклади.
Тема 14: Оптимізація програм: оптимізація на етапах розробки та трансляції
  • Оптимізація процедур на основі інваріантних співвідношень.
  • Оптимізація на етапі трансляції: вилучення надлишкових конструкцій.
  • Оптимізація на етапі компіляції: розподіл регістрів.
Тема 15: Структури даних
  • АТД та їх властивості.
  • Скалярний тип даних та його властивості. Приклади.
  • Структурний тип даних:
    • підпрограми,
    • спів програми,
    • процедури-функції.
Тема 16: Фундаментальні структури даних I
  • Множини.
  • Відображення.
  • Послідовності.
  • Графи.
Тема 17: Фундаментальні структури даних II
  • Черги.
  • Черги з приорітетами.
  • Словники.
  • Чорно-білі дерева та їх властивості.
Тема 18: Підведення підсумків
  • Дискусія на тему: що таке хороша програма і хороший програміст?
Модульна контрольна робота 2

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

Основна:

  1. Кривий С.Л. Дискретна математика: вибрані питання. – Вид. дім «Києво-Могилянська академія». – 2007. – 570 с.
  2. Лекции по дискретной математике. Капитонова Ю.В., Кривой С.Л., Летичевский А.А., Луцкий Г.М., Санкт-Петербург. – БХВ. – 2005. – 634 стр.
  3. Глушков В.М., Цейтлин Г.Е, Ющенко Е.Л. Алгебра, язики, программирование. К.: Наукова думка, 1989. – 376 с.
  4. Кривий С.Л. Вступ до методів створення програмних продуктів. Чернівці: Букрек. – 2013 р.. – 424 с.
  5. Донец Г.А. Решение задачи о сейфе на (0,1) матрицах. // Кибернетика и сист. анализ. – 2002. – № 1. – С. 98-105.
  6. Манна З. Семантика неподвижной точки функциональных программ. // Киб. сборник. Вып. 15. – М. Мир. – 1979. – С. 38-100.
  7. Зикман Й., Сабо Р. Универсальная унификация и классификация эквациональных теорий. // Кибернетический сборник (новая серия). – 1986. – вып. 21. – С. 213-234.
  8. Филд А., Харрисон П. Функциональное программирование. – М. Мир. – 1993. – 742 с.
  9. Коблиц И. Курс теории чисел и криптографии. – М. Научное издат. ТВП. – 2001. – 260 с.
  10. Крывый С.Л. Алгоритмы решения систем линейных диофантовых уравнений в полях вычетов. // Кибернетика и сист. анализ, 2007. – № 2. – С. 15-23.
  11. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – М.: Мир, – 1979. – 535 с.
  12. Ахо А., Ульман Дж. Теория синтаксического анализа и комриляции, т. 2 Компиляция. – М.: Мир, – 1978. – 486 с.
  13. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. – М.: Издат. дом "Вильямс". – 2000. – 382 с.
  14. Вирт Н. Систематическое программирование. Введение. – М.: Мир. – 1977. – 183 с.
  15. Вирт Н. Алгоритмы + структуры данных = программы. – М.: Мир. – 1985. – 406 с.
  16. Гери М.Р., Джонсон Д.С. Вычислительные машины и трудновычислимые задачи. – М.: Мир. – 1982. – 416 с.
  17. Глушков В.М. Теория автоматов и формальные преобразования микропрограмм. // Кибернетика. – 1965. – № 5. – C. 1-9.
  18. Годлевский А.Б., Кривой С.Л. Трансформационный синтез эффективных алгоритмов с учетом дополнительных спецификаций. // Кибернетика. – 1986. – № 6. – C. 37-43.
  19. Годлевский А.Б., Капитонова Ю.В., Кривой С.Л., Летичевский А.А. Итеративные методы анализа программ. // Кибернетика. – 1989. – № 2. – C. 9-19.
  20. Капитонова Ю.В., Летичевский А.А. Об основных парадигмах программирования. // Кибернетика и сист. анализ. – 1994. – № 6. – C. 3-20.
  21. Кривий С.Л. Дискретна математика. – Київ-Чернівці: Букрек. – 2014. – 568 с.
  22. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ (второе издание). – Издательский дом "Вильямс". – 2005. – 1290 с.
  23. Мальцев А.И. Алгоритмы и рекурсивные функции. – М.: Наука. – 1986. – 367 с.

Додаткова:

  1. Седжвик Р. Фундаментальные алгоритмы на C++. Части 1-4. – M.: DiaSoft. – 2002. – 687 с.
  2. Аtallach M. J. (editor). Algorithms and Theory of Computation Handbook. CRC Pres. – 1999. – v.1 (Searching). – P. 29-34.
  3. Ershov A.P. Mixed computation: potential applications and problem for study. // Theor. Comput. Science. – 1982. – 18. – pp. 41-68.
  4. Fisher M.J., Ladner R.E. Propositional Modal Logic of Programs. // In Proc. 9-th ACM Ann. Symposium on Theory of Computing. – 1977. – pp. 286-294.
  5. Fisher M.J., Ladner R.E. Propositional Dynamic Logic of regular programs. // J. Comp. System Sci. – 1979. – Vol. 18. – No. 2. – pp. 194-211.
  6. Goldblatt R. Logics of Time and Computation. – Lecture Notes. – № 7. Center for the Study of Language and Information. – 1987. – pp. 1-27.
  7. Johnson D.S. A Catalogue of Complexity Classes. – In J. van Leeuwen., ed. "Handb. of Theoret. Computer Science". – Vol. A. – 1990: Elsevier. – pp. 67-161.
  8. Kam J.B., Ullman D.J. Monotone data flow analysis frame works. // Acta Inform. – 1978. – No. 3. – P. 305-318.
  9. Kildall G.A. A unified approach to program optimization. // Conf. Rec. of ACM Symp. on Prince. of Program Languages Boston, Massachusetts. – Oktober 1-3. – 1973. – pp. 194-206.
  10. Papadimitriou C.H. Computational complexity. – Addison-Wesley. – 1994. – 532 p.
  11. Winograd S. On the number of multiplications necessary to compute certain functions. // J. Pure and Applied Mathematics. – 1970. – P. 165-179.