- •Що виносяться на державний іспит в 2014 р. (спеціалісти спеціальності «інформатика»)
- •1. Програмування, системне програмування
- •Системнепрограмування
- •1. Мови програмування та їх класифiкацiя.
- •2. Системнепрограмування
- •2. Типи даних, скалярні та структурованi типи. Оператори; оператор присвоєння, структурнi оператори. Засоби вводу-виводу.
- •3. Структуризація програм та даних. Підпрограми, функцiї.
- •4. Динамічні структури даних. Списки, стеки, черги. Дерева, бінарні дерева. Дерева пошуку.
- •5. Поняття про функцiональне програмування, структурне програмування, об'єктно-орiєнтоване програмування.
- •6. Інструментальні засоби розробки інформаційних технологій, case-технології
- •2. Системнепрограмування
- •7. Cучасні технології програмування та тенденції їх розвитку.
- •2. Системнепрограмування
- •8. Об’єктно-орієнтоване програмування. Мова Java.
- •2. Системнепрограмування
- •9. Поняття мовного процесора. Типи мовних процесорів. Основні фази мовного процесора.
- •2. Системнепрограмування
- •10. Скінченні автомати. Методика побудови лексичного аналізатора на основі скінченного автомата.
- •2. Системнепрограмування
- •11. Синтаксичний аналіз та породжувальні граматики. Виведення в граматиці, дерево виведення. Лівостороння та правостороння стратегії виведення.
- •2. Системнепрограмування
- •12. Ll(k)-граматики. Перевірка ll(1)-умови. Побудова ll(1)-таблиці для управління синтаксичним ll(1)-аналізатором.
- •2. Системнепрограмування
- •13. Методи денотацiйної та операційної семантики. Метод семантичних підпрограм. Атрибутний метод визначення семантики програм. Семантичний терм програми.
- •2. Системнепрограмування
- •14. Машинно-орієнтовані мови програмування. Асемблери. Структура асемблера, перегляди тексту програми та відповідні бази даних.
- •2. Інформаційні технології
- •1. Уніфікована мова моделювання uml. Діаграми прецедентів
- •2. Використання діаграм послідовностей та діаграм класів при проектуванні програмних систем.
- •3. Патерни проектування
- •Класифікації патернів:
- •4. Платформа .Net Framework.
- •5. Сервісно-орієнтована архітектура
- •6. Огляд технологій j2ee. Технологія Java rmi.
- •8. Патерн Model-View-Controller у Web-проектах.
- •9. Патерн (принцип) ioc&di та його підтримка у фреймворку Spring
- •10. Проблема валідації даних у Web-проектах. Підтримка ajax.
- •3. Інформаційні мережі
- •1. Інформаційна глобальна мережа internet (написано много, выбрать главное)
- •Internet надає такі основні види послуг:
- •2. Система доменних імен глобальної мережі internet.
- •3. Система електронної пошти глобальної мережі internet.
- •4. Системи інтерактивних комунікацій глобальноїмережі internet (на прикладі Skype, icq).
- •5. Системи електронних спільнот глобальної мережі internet (на прикладі Facebook, Twiter).
- •6. Поняття універсального вказівника ресурсу. Основні типи ресурсів.
- •7. Мережі tcp/ip.Стек протоколів tcp/ip: топологічні особливості, функції рівнів.
- •8. Поняття раутінгу в мережах tcp/ip. (аккуратно, перевод через гугл транслейт!!!)
- •9. Технології, що забезпечують відмовостійкість мереж tcp/ip. (ответ не очень)
- •10.Класифікація комп’ютерних мереж.
- •11. Системи захисту інформації в глобальній мережі internet (на прикладі pgp).
- •4. Математична логіка та теорія алгоритмів, теорія програмування
- •9. Основні поняття програмування, відношення між ними. Основні програмні поняття Розвиток основних понять програмування
- •Композиції
- •11. Методи подання синтаксису мов програмування.
- •4.8.1. Нормальні форми Бекуса–Наура
- •4.8.2. Модифіковані нормальні форми Бекуса–Наура
- •4.8.3. Синтаксичні діаграми
- •Визначення основних понять формальних мов
- •4.3. Операції над формальними мовами
- •13. Неперервні відображення.Теореми про найменшу нерухому точку (Кнастер-Тарський-Кліні); теорема про неперервність оператора нерухомої точки.
- •14. Методи формальної семантики мов програмування (композиційна, натуральна, денотаційна, аксіоматична).
- •5. Штучний інтелект
4. Математична логіка та теорія алгоритмів, теорія програмування
1. Основні поняття логіки. Предикати, висловлення. Пропозиційна логіка.
2. Логіки 1-го порядку, їх семантичні моделі та мови. Виразність предикатів, множин, функцій в семантичних моделях. Істинність, виконуваність, логічний наслідок, логічна еквівалентність.
3. Aксіоматичні системи логік 1-го порядку (теорії 1 порядку). Несуперечливість, повнота, розв’язність теорій 1 порядку. Теорема Гьоделя про повноту, теорема компактності.
4. Методи пошуку доведень. Метод резолюцій. Секвенційні числення, їх коректність та повнота.
5. Нетрадиційні логіки. Багатозначні логіки. Інтуїціоністська логіка. Модальні логіки, їх різновидності (алетичні, темпоральні, епістемічні).
6. Поняття алгоритму. Формальні моделі алгоритмів та алгоритмічно обчислюваних функцій. Частково рекурсивні, рекурсивні функції. Теза Чорча.
7. Рекурсивні та рекурсивно перелічні множини, рекурсивні та частково рекурсивні предикати. Нерозв’язність проблем зупинки і самозастосовності, наслідки.
8. Оператори на функціях та множинах. Оператори переліку, рекурсивні оператори. Теореми Кліні про нерухому точку, їх застосування.
9. Основні поняття програмування, відношення між ними. Основні програмні поняття.
10. Номінативні дані. Структури даних мов програмування як конкретизації номінативних даних. Основні композиції програм.
11. Методи подання синтаксису мов програмування.
12. Формальні (породжувальні) граматики та мови; їх визначення та класифікація.
13. Неперервні відображення. Теореми про найменшу нерухому точку (Кнастер-Тарський-Кліні); теорема про неперервність оператора нерухомої точки.
14. Методи формальної семантики мов програмування (композиційна, натуральна, денотаційна, аксіоматична).
15. Формальні методи розробки програм.
9. Основні поняття програмування, відношення між ними. Основні програмні поняття Розвиток основних понять програмування
У процесі уточнення програмних понять будемо часто використовувати тріаду розвитку: теза – антитеза – синтез.
Розвиток понять програмування почнемо з найвищого (філософського) рівня. На цьому рівні основним є категорії суб’єкта та об’єкта. Діяльність суб’єкта має бути цілеспрямованою. Тобто, ціль є антитезою суб’єкта. Їх синтезом є категорія засіб. Таким чином, отримано першу тріаду: суб’єкт – ціль – засіб. Розвиваючи далі цю тріаду отримуємо ще дві категорії – використання засобів та створення засобів. Отримуємо пентаду: суб’єкт – ціль – засіб – використання засобів – створення засобів.
Переходимо тепер до наукового рівня розгляду. Тут найважливішим чинником буде поняття користувача (його елементами будуть конкретні користувачі). Саме це поняття – користувача – і є початковим пунктом розвитку. Тому можна вважати, що ціллю користувача є розв’язок певної проблеми. Згідно з тріадою розвитку наступний крок приведе до поняття, яке є синтезом понять користувача і проблема і яке може також розглядатися як розвиток користувача. Це – розв'язок проблеми. У цій області розв'язком вважається програма (яка повинна допомогти користувачу розв’язати його проблему).
Ця тріада вперше вводить термін «програма», і саме ця тріада задає умови існування і ціль (мету) програм. Тому цю тріаду доцільно назвати тріадою цільового призначення програм. Мета програм полягає утому, що вони є засобами розв’язку певних проблем користувача.
Далі розглянемо, який зв’язок між проблемами та програмами. Якщо користувач обрав для розв’язку актуальну для нього проблему, то йому бажано мати програму, яка найбільш відповідним чином (найбільш адекватно) розв’язує цю проблему. Тому поняття проблеми і програми пов’язані відношенням адекватності (відповідності, правильності програми для розв’язку проблеми).
Поняття користувача і проблеми пов’язує відношення прагматичності (від грецького pragma – діло, дія».
Перейдемо до наступного кроку розвитку. Цей крок полягає в тому, щоб розкрити відношення адекватності.. Таким поняттям буде програмування (як процес), яке повинно пов’язати разом проблему і відповідну їй програму. Таким чином, побудовано нову тріаду розвитку: проблема (теза) – програма (антитеза) – процес програмування (синтез). Цю тріаду назвемо тріадою основних понять програмування, бо саме в ній уперше з'являється поняття програмування.
поняття програмування та проблеми з’єднує відношення орієнтованості процесу програмування на розв'язок певної проблеми (проблемно-орієнтованість). Що ж стосується взаємодії понять програми та програмування, то тут виділимо два відношення:
відношення генетичностіпрограм (відношення «програма – процес програмування»);
відношення експлікативності процесу програмування (відношення «процес програмування – програма»).
Уведені відношення також пов'язані одне з одним. Так, можна говорити про те, що відношення адекватності програми проблемі є певним «добутком» відношень проблемно-орієнтованості та уточнюваності: чим вони кращі, тим кращою є адекватність програми. Тобто можна записати таку символічну (але не формальну) формулу:
(адекватність програми проблемі)=
=(проблемно-орієнтованість процесу програмування) *
*(експлікативність процесу програмування)
Пентада основних понять програмування виділяє основні аспекти понять програмування. Так, для поняття програми основними аспектами будуть
адекватність;
прагматичність;
обчислюваність;
генетичність.
Для процесу програмування основні аспекти це
проблемна орієнтованість;
експлікативність.
програмування є процес побудови програм, що має на меті розв’язання певних проблем, актуальних для користувача, шляхом їх виконання.
Побудована пентада фактично відображає будь-який процес програмування, зокрема, процес підготовки програм для телебачення і т.д.
Почнемо подальший розвиток із конкретизації поняття програми..
тріада «користувач – проблема – програма». З цієї тріади ми бачимо, що поняття програми є діалектичним запереченням (антитезою) поняття проблеми, тобто програми не є проблемами, але зберігають у собі проблеми у якійсь іншій формі.
.
спочатку досліджується зовнішня сторона інформації – тобто дані (пригадайте структури даних мов програмування, бази даних тощо), далі акцент переноситься на інформацію (інформаційні технології, інформаційне суспільство), після чого мають прийти технології обробки знань та бази знань (суспільство, засноване на знаннях
Повертаючись назад до поняття проблеми, бачимо, що найважливішою властивістю проблем є властивість інформаційності, тобто та обставина, що для розв’язання проблеми необхідно визначити (обчислити) деяку нову інформацію (на підставі наявної інформації). Цю властивість проблем назвемо принципом інформаційності проблем. Таким чином, програми застосовуються для одержання деяких нових даних (на підставі наявних даних), які у предметній області інтерпретуються як деяка нова інформація, що використовується для розв’язання проблеми.
У математиці об’єкти, що обчислюють нові дані на підставі вхідних даних, називають функціями, а сам процес застосування функцій до даних – аплікативністю.
Отже, основною (істотною) властивістю програм є властивість аплікативності (функціональності): програми застосовують до вхідних даних для одержання результатів. Внутрішня властивість аплікативності знаходить своє зовнішнє відображення у відношенні прагматичності програм, оскільки вона задає спосіб використання програм користувачем. Ця властивість дозволяє на гранично високому рівні абстракції трактувати програми як функції, які переводять вхідні дані у вихідні
Принцип аплікативності (функціональності). програми можуть розглядатися як функції, які при застосуванні до вхідних даних можуть виробляти вихідні дані.
Пов’язуються ці поняття аплікацією (застосуванням функції до даного, у результаті якого утворюється вихідне дане
Принцип номінативності програм. Програми можна представляти як імена, що позначають функції, які відображають вхідні дані в результати.
Поняття функції, імені і денотації, які є дуже абстрактними, мають широке коло застосування. До цього моменту розвитку був встановлений зв’язок між даними і функціями за допомогою аплікації і між функціями та іменами функцій за допомогою відношення денотації. Їх зв’язок задається похідним відношенням інтерпретації, що за ім’ям функції та даним визначають результат застосування функції, що позначається цим іменем, до обраного даного. Відзначимо, що якщо зазначену впорядковану пару (ім’я, дане) розглядати як структуроване дане, то операція (відношення) інтерпретації підпадає під поняття функції, що дозволяє будувати «універсальні» операції інтерпретації як «звичайні» функції. Додатковий аспект операції інтерпретації стосується її обчислюваності. Подальший розвиток цих аспектів призводить до побудови інтерпретаторів мов програмування і, зокрема, комп’ютерів.
Рисунок 2.8. Тріада основних програмних понять
Принцип композиційності. Програми (функції) будуються з більш простих програм за допомогою композицій.
У якості одного з наслідків цього принципу одержуємо, що повинні існувати деякі базові функції (програми), які використовуються для побудови більш складних функцій.
Принцип дескриптивності. Програми можна представляти у вигляді дескрипцій (складних зображень), побудованих з використанням дескрипцій більш простих програм і композицій, та які описують функції, що відображають вхідні дані в результати.
Дескрипції можуть розглядатися як імена, побудовані за допомогою більш простих імен. Правила побудови таких імен (дескрипцій) звичайно називаються граматикою. Граматика задає закони побудови правильних синтаксичних конструкцій.
У процесі розвитку поняття програми були введені п’ять програмних понять: дане – функція – ім’я функції – композиція – дескрипція.
чітко просліджуються три напрямки (три програмні аспекти):
програмний аспект, що пов’язує дані, функції та композиції, який називають семантичним аспектом;
програмний аспект, що пов’язує дані, імена та дескрипції, який називають синтаксичним аспектом;
програмний аспект, що пов’язує імена та дескрипції з функціями та композиціями, який називають денотаційним аспектом.
.
Рисунок 2.9. Пентада основних програмних понять
10. Номінативні дані. Структури даних мов програмування як конкретизації номінативних даних. Основні композиції програм.
