Прикладне програмне забезпечення
ЗАТВЕРДЖУЮ
Перший проректор університету,
професор
_____________О. Співаковський
ПРОГРАМА КОМПЛЕКСНОГО
ДЕРЖАВНОГО ЕКЗАМЕНУ
ДЛЯ БАКАЛАВРІВ
Модулі:
1. Прикладна математика.
2. Програмування.
Спеціальність:
6.040302. Інформатика
ОБГОВОРЕНО
На засіданні кафедри інформатики
Протокол №3 від 11.11.2010 р.
Завідувач кафедри інформатики
_______ проф. Співаковський О.В.
СХВАЛЕНО
Науково-методичною радою
Факультету фізики, математики та інформатики
Протокол №3 від 25.11.2010 р.
Херсон – 2011
Пояснювальна записка
Метою державної атестації студента є визначення фактичної відповідності його підготовки вимогам освітньо-кваліфікаційної характеристики. Державна атестація здійснюється державною екзаменаційною комісією (ДЕК) після завершення навчання на певному освітньо-кваліфікаційному рівні. ДЕК оцінює рівень науково-теоретичної і практичної підготовки студентів, вирішує питання про здобуття певного освітнього рівня, присвоєння відповідної кваліфікації та видачу документа про вищу освіту.
Державний екзамен проводиться в усній формі за білетами, укладений на основі робочих програм.
До державної атестації допускаються студенти, які успішно виконали всі вимоги навчального плану зі спеціальності «Інформатика» освітньо-кваліфікаційного рівня «Бакалавр» (не мають академічної заборгованості).
Державний іспит із спеціальності повинен засвідчити, що випускник оволодів необхідними теоретичними знаннями та навичками їх практичного застосування в конкретних умовах.
Державний іспит передбачає показати:
· вміння систематизувати теоретичні знання і практичні навички, отримані студентом за весь період навчання;
· вільно володіти методиками теоретичного дослідження при розв'язанні конкретних задач з різних предметних областей;
· вміння працювати на рівні сучасних інформаційних технологій;
· підготовленість студента для самостійного аналізу та викладу матеріалу, вміння захищати свої знання перед Державною екзаменаційною комісією;
· вміння аналізувати, досліджувати проблему (задачу) за допомогою нових методів, будувати математичну модель синтезувати та узагальнювати накопичений в процесі аналізу матеріал, а також розробляти для цього програмне забезпечення.
Критерії оцінювання знань і вмінь студентів
Система контролю якості навчального процесу та критерії оцінок, які використовуються у Херсонському державному університеті, основана на "Положенні про організацію навчального процесу у вищих навчальних закладах", затвердженим наказом Міністерства освіти України від 02.06.1993р. № 161 (розділ Контрольні заходи). Метою контролю є оцінка якості організації та проведення навчально-виховного процесу та його кінцевих результатів, а також подальше вдосконалення форм та методів роботи. Основним завданням системи контролю є систематична оцінка якості засвоєння студентами навчальної інформації у повному обсязі курсів, проведення всіх форм занять, підготовки спеціалістів у цілому.
Результати складання державного екзамену визначаються оцінками “відмінно”, “добре”, “задовільно”, “незадовільно” та виставляється по семибальній системі шкали ECTS, яка переводиться у національну шкалу:
| Національна система оцінювання | ECTS | Критерії оцінювання навчальних досягнень студентів |
| F | Студент може розрізняти об'єкти вивчення, відтворює незначну частину навчального матеріалу, має нечіткі уявлення про об'єкт вивчення | |
| FX | Студент відтворює частину навчального матеріалу; з допомогою викладача виконує елементарні завдання | |
| E | Студент за допомогою викладача відтворює основний навчальний матеріал, може повторити за зразком певну операцію, дію; відтворює основний навчальний матеріал, здатний з помилками й неточностями дати визначення понять | |
| 3,5 | D | Студент виявляє знання й розуміння основних положень навчального матеріалу; відповідь його правильна, але недостатньо осмислена; вміє наводити окремі власні приклади на підтвердження певних думок, застосовувати знання при виконанні завдань за зразком. |
| C | Студент добре володіє вивченим матеріалом, він застосовує вивчений матеріал у стандартних ситуаціях, уміє аналізувати й систематизувати інформацію; використовує загальновідомі докази із самостійною і правильною аргументацією; відповідь його логічна, хоч і має неточності | |
| 4,5 | B | Студент має міцні знання, здатний аргументовано використовувати їх у практичній діяльності, робити висновки, узагальнення, уміє знаходити інформацію та аналізувати її, ставити і розв'язувати проблеми |
| A | Студент має системні глибокі знання в обсязі та в межах вимог навчальних програм, усвідомлено використовує їх у стандартних та нестандартних ситуаціях. Уміє самостійно аналізувати, оцінювати, узагальнювати опанований матеріал, самостійно користуватися джерелами інформації, приймати рішення |
Рішення державної комісії про оцінювання рівня підготовки студентів, а також про присвоєння студентам кваліфікації «Бакалавр» та видачу їм державних документів про неповну вищу освіту приймається державною комісією на закритому засіданні відкритим голосуванням звичайною більшістю голосів членів комісії, які брали участь у засіданні.
1. Прикладна математика
Математична логіка і теорія алгоритмів
1. Висловлення. Логічні операції. Пропозиційні формули. Тавтології. Основні тавтології. Рівносильні формули. Основні рівносильності.
2. Диз’юнктивне (кон’юнктивне) розкладання пропозиційної формули по змінній. Нормальні форми. Досконалі нормальні форми. Правила одержання досконалих нормальних форм. Двоїстість. Закон двоїстості.
3. Булеві функції. Застосування булевих функцій до аналізу й синтезу дискретних пристроїв. Застосування булевих функцій у теорії релейно-контактних схем. Логічне слідування. Деякі застосування тавтологій.
4. Формальне доведення і вивідна пропозиційна формула. Приклади виведених формул.
5. Вивідність з гіпотез. Прості властивості вивідності з гіпотез. Теорема про дедукцію. Подальші властивості виводності з гіпотез. Несуперечністьчислення висловлень. Повнота числення висловлень.
6. Предикати. Операції над предикатами. Операція навішування кванторів. Предикатні формули. Рівносильні формули. Основні рівносильності логіки предикатів.
7. Предикатні формули в приведеній формі. Випереджена нормальна форма. Рівносильні формули.Тотожно-істинні формули. Проблема розв’язності для логіки предикатів.
8. Формули числення предикатів. Аксіоми числення предикатів і правила виводу. Формальне доведення і вивідність з гіпотез. Теорема про дедукцію для числення предикатів. Несуперечність числення предикатів. Повнота числення предикатів. Теорема Геделя.
9. Інтуїтивне поняття алгоритму. Машини Т’юринга. Опис машини Т’юринга. Визначення машини Т’юринга. Обчислювальні за Т’юрингом числові функції.
10. Обчислювальні функції. Примітивно рекурсивні функції. Частково рекурсивні функції. Загальнорекурсивні функції. Рекурсивні множини.
11. Приклади алгоритмічно нерозв’язних проблем. Проблема самозастосовності. Проблема застосовності. Проблема перевідності. Проблема еквівалентності слів в асоціативних численнях. Нормальні алгорифми А. Маркова. Про масові проблеми.
Методи оптимізації
12. Постановка задачі лінійного програмування. Графічний метод розв’язання. Графічний аналіз чутливості.
13. Канонічна форма, опорні розв’язки задачі лінійного програмування. Симплекс-метод розв’язання задачі лінійного програмування.
14. Взаємно двійкові задачі, їх економічна сутність Основні теореми двійковості лінійного програмування.
15. Транспортні задачі. Економічна та математична постановка задачі. Опорний план (розв’язок). Метод північно-західного кута, метод найменшої вартості.
16. Метод потенціалів в транспортних задачах. Реалізація транспортних задач в EXCEL.
17. Мережеві моделі. Алгоритм побудови мінімального остового дерева.
18. Задача знаходження найкоротшого шляху. Алгоритм Дейкстри. Алгоритм Флойда. Задача про максимальній потік.
19. Методи мережевого планування. Побудова мережі проекту. Метод критичного путі.
20. Знаходження потоку найменшої вартості. Зведення мережевих моделей до задач лінійного програмування.
21. Цілочисельні задачі лінійного програмування. Приклади цілочисельних задач лінійного програмування в плануванні та управлінні.
22. Цілочисельні задачі лінійного програмування. Моделі управління запасами. Розв’язування їх за допомогою модулю „ Пошук рішення ”.
Дискретна математика
23. Теорія множин. Відношення.Поняття множини. Операції над множинами. Діаграми Венна. Булеві алгебри. Відношення еквівалентності. Фактор-множина за відношенням еквівалентності.
24. Логіка, цілі числа і доведення. Числення предикатів. Основні положення теорії доведень і теорії цілих чисел. Математична індукція. Подільність. Прості числа. Порівняння.
25. Графи, орієнтовані графи й дерева.Миттєве божевілля. Шляхи та цикли Ейлера. Матриці інцидентності й суміжності. Гіперкуби та код Грея.
26. Комбінаторика та ймовірність.Основні комбінаторні принципи. Комбінаторний принцип додавання. Перестановки й сполучення. Введення ймовірності. Узагальнені перестановки і сполучення. Перестановки й сполучення з повторенням. Теорема Байеса. Ланцюги Маркова.
27. Алгебраїчні структури.Частково впорядковані множини. Напівгрупи і напіврешітки. Решітки. Групи. Групи і гомоморфізми.
28. Твірні функції та комбінаторні підрахунки.Твірні функції й рекурентні відношення та комбінаторні підрахунки. Розбиття. Експонентні твірні функції.
29. Теорія графів. Алгебраїчні властивості графів. Планарні графи. Розфарбування графів. Шляхи та цикли Гамільтона. Зважені графи та алгоритми пошуку найкоротшого шляху. Алгоритми Форда та Дейкстра.
30. Дерева. Властивості дерев. Бінарні дерева пошуку. Зважені дерева. Обхід бінарних дерев. Остовні дерева. Мінімальні остовні дерева.
31. Мережі та потоки. Паросполуки. Мережі Петрі.
32. Теорія обчислень. Регулярні мови. Автомати. Граматики.
33. Теорія кодів. Породжуючі матриці. Коди Хемінга. Перерахування кольорів. Теорема Бернсайда. Теорема Пойа.
Програмування
Основи алгоритмізації та програмування
1. Змістовне поняття алгоритму. Основні властивості алгоритмів. Виконавець алгоритмів та його система команд. Абстракція даних. Команди управління. Базові управляючі структури.
2. Формалізація поняття алгоритму. Поняття обчислювальності. Примітивно-рекурсивні функції. Мю-оператор. Частково-рекурсивні функції як формалізація поняття обчислювальної функції. Схеми обчислень частково-рекурсивної функції в термінах алгоритмічної мови. Тезис Черча.
3. Мови програмування (МП) як формальні мови описів алгоритмів. Структура МП. Синтаксис і семантика описів алгоритмів. Оператори управління МП. Складений оператор. Оператори вибору. Техніка програмування розгалужень. Оператори повторення. Техніка програмування циклів.
4. Методологія процедурного програмування. Структуризація алгоритму в термінах процедур і функцій. Синтаксис описів і семантика виконання. Організація обміну даними між процедурами. Локалізація даних. Техніка програмування в термінах процедур і функцій.
5. Рекурсивні описи процедур і функцій. Схеми для рекурсивного опису функцій. Форми рекурсії. Лінійна рекурсія. Повторна, каскадна та удалена рекурсії. Взаємна рекурсія. Рекурсивні та ітеративні описи алгоритмів. Графічні задачі і рекурсія.
6. Статичні типи даних: регулярний тип даних. Масиви. Одномірні та багатомірні масиви і загальні типи індексів. Динамічні і гнучкі масиви. Задачі обробки масивів. Лінійний пошук у масиві. Бінарний пошук у масиві.
7. Алгоритми сортування масивів. Прості алгоритми сортування: сортування обмінами (бульбашкове), сортування вибором, сортування вставками. Швидкі алгоритми сортування.
8. Посилальний тип даних. Операції над покажчиками. Розподіл пам’яті. Рекурсивні об’яви типів. Динамічні інформаційні структури та їх реалізація. Послідовності як абстрактні типи даних. Обчислювальні структури послідовностей.
9. Списки. Лінійні списки. Рекурсивно-оголошені спискові типи. Реалізація послідовностей у вигляді списків. Двонаправлені списки. Кільцеві списки. Узагальнені часткові структури.
Об’єктно-орієнтоване програмування
10. Концепція об’єктно-орієнтованого (ОО) програмування. Структурний та ОО підходи у програмуванні. Базові елементи ОО підходу. Поняття класу. Атрибути, методи. Класифікація атрибутів. Дані-члени, функції-члени. Статичні члени класу.
11. Приватні, захищені, відкриті члени класу. Конструктор, деструктор, функції-селектори, модифікатори, помічники. Конструктор копії. Вказівники та посилання на класи. Спадкування, його види. Перевизначення методів у похідних класах.
12. Поняття поліморфізму. Раннє та пізнє зв’язування. Віртуальні функції.
13. Відношення наслідування. Відкрите та закрите (приватне) наслідування. Множинне спадкування, його види та правила застосування.
14. Друзі класу. Правила визначення та засоби використання. Подружні класи, та функції.
15. Ієрархії наслідування. Абстрактні та конкретні класи. Приклади. Проблема класифікації об’єктів.
16. Перевантаження операторів. Правила реалізації. Вибір між оператором-членом и оператором-помічником. Перетворення типів та мішані операції. Перевантаження операторів =, [ ], ( ), → (<<,>>, ++, -- постфіксного и префіксного).
17. Standard Template Library: принципи, вимоги, типи. STL Ітератори. Типи ітераторів. Вимоги та реалізація. STL Алгоритми та функції..
18. MFC. Каркас додатку. MFC – відображення та друк даних.
19. Введення в COM. Інтерфейси COM.
Ефективні алгоритми та структури даних
20. Основні абстрактні типи даних АТД Список. Реалізація списків. АТД Стек. Реалізація стеків. АТД Черга. Реалізація черг. АТД Відображення. Реалізація відображень.
21. Дерева Означення дерева. Різні стратегії обходу дерев. АТД Дерево. Реалізація дерев. Бінарні дерева. Представлення бінарних дерев. Реалізація бінарних дерев.
22. Основні оператори множин Введення в множини. Оператори АТД, засновані на множинах. Реалізація множин за допомогою бінарних векторів.
23. Реалізація множин за допомогою зв’язаних списків. Словники. Реалізація словників.
24. Хешування. Структури даних, засновані на хеш-теблицях. Відкрите хешування. Закрите хешування. Оцінка ефективності хеш-функцій.
25. Орієнтовані графи. Основні означення. Представлення орграфів. Задача пошуку найкоротшого шляху. Обґрунтування та аналіз алгоритму Дейкстри.
26. Пошук найкоротших шляхів між парами вершин. Порівняння алгоритмів Флойда та Дейкстри. Транзитивне замикання. Обхід орграфів. Аналіз процедури пошуку в глибину.
27. Неорієнтовані графи. Основні означення. Представлення неорієнтованих графів. Остовні дерева мінімальної вартості. Алгоритм Прима. Алгоритм Краскала. Обходи неорієнтованих графів: пошук в глибину та ширину.
28. Сортування. Модель внутрішнього сортування. Прості схеми сортування. Швидке сортування. Пірамідальне сортування. Час виконання сортувань порівняннями. Порядкові статистики.
29. Методи розробки алгоритмів. Метод «Розподіляй і володій». Складення графіка проведення тенісного турніру. Баланс підзадач.
30. Динамічне програмування. Ймовірність перемоги в спортивних турнірах. Задача тріангуляції. Пошук рішень на основі таблиці. Жадібні алгоритми. Жадібні алгоритми як евристики.
Прикладне програмне забезпечення
31. Основи програмування для ОС Windows. Структура Windows-додатку. Функція WinMain. Реєстрація класу вікна. Створення вікна. Вікна, що означені в Windows. Цикл обробки повідомлень. Віконна процедура. Створення додатку. Вікна, меню, блоки діалогу.
32. Ієрархія класів MFC. Класи даних MFC. Клас CObject. Класи простих типів даних. Інтерфейсні класи МFC. Вікна, діалоги та елементи управління.
33. Класи для роботи в Intertnet і мережах. Модель COMM IDL. Класи для налагодження і опрацювання виключень. Шаблон додатків MFC. Клас CWinApp. Реєстрація класу вікна. Мінімальна програма для Windows. Створення та відображення вікна.
34. Обробка повідомлень MFC. Цикл обробки повідомлень MFC. Основні типи повідомлень Windows. Типи повідомлень MFC. Карта повідомлень та її компоненти. Стандартний маршрут команди. Команди поновлення і клас CCmdUI. Функції для роботи з повідомленнями. Багатовіконний інтерфейс. Типи додатків SDI та MDI додатки.
35. Відображення текстової і графічної інформації. Графічні об’єкти. Доступ до графічного об’єкту. Редагування графічних об’єктів. Контексти пристроїв.
36. Графічні режими. Режими відображення. Перетворення координат. Типи контекстів пристроїв. Контексти екрану, принтера. Контекст пристроїв в пам’яті. Класи для виведення на екран та друкування.
37. Сценарії та протоколи CGI. Модель активних серверних сценаріїв.
38. Програмування ASP. Серверні вставки. Об’єкти Request та Response.
39. Програмування ASP. Масиви, переліки і асоційовані переліки.
40. Програмування ASP. Класи для роботи з файлами та базами даних.
41. Історія появи Інтернет. Всесвітня павутина-World Wide Web. Гіпертекстові системи. Уніфікація мови HTML.
42. Структура HTML документу. Форматування html документу.
43. Мова HTML. Фрейми та їх використання.
44. Мова HTML. Теги, контейнери та атрибути. Тегова модель.
45. Мова HTML. Посилання в html документах.
46. Мова HTML. Форми та їх використання.
47. Мова HTML. Таблиці стилів їх використання.
48. Мова HTML. Списки, таблиці, шрифти.
49. Динамічний HTML. Сценарії Java Script.
50. Мова програмування C#. Типи даних С#. Змінні та константи. Клас object. Приведення типів. Області бачення змінних. Типи користувача. Перечислення.
51. Мова програмування C#. Оператори та їх приорітети. Використання класу Match. Структури вибору. Цикли.
52. Мова програмування C#. Класи. Властивості та методи. Передача параметрів методам. Створення та знищення об’єктів. Конструктори. Керування пам’яттю.
53. Мова програмування C#. Інтерфейси. Стандартні інтерфейси .Net.Framework. Інформація о типах під час виконання програми.
54. Мова програмування C#. Простір імен. Важливіші простори імен .Net.Framework та їх призначення.
55. Мова програмування C#. Обробка помилок. Виключення. Генерація та обробка виключень. Ієрархія класів виключень. Клас Exception.
56. Мова програмування C#. Текстові та бінарні потоки. Класи для роботи з каталогами та файлами. Серіалізація об’єктів.
57. Мова програмування C#. Масиви. Властивості та методи класу масивів. Строки. Інтерфейси та класи колекцій.
58. Мова програмування C#. Делегати та події. Програмування з використанням подій. Події в Windows Forms.
59. Мова програмування C#. Елементи управління Windows Forms. Кнопки. Текстові поля. Надписи. Перемикачі. Прапорці. Рамки. Списки.
60. Мова програмування C#. Елементи управління Windows Forms. Рисунки. Графічні поля. Таймери. Колії прокрутки. Списки дисків. Списки каталогів. Списки файлів. Дерева.