Теория, половина нам подходит


Contents
TOC \o "1-3" \h \z \u 1. Інформаційні технології та інформаційні системи PAGEREF _Toc389947998 \h 41. Інструментальні засоби розробки інформаційних технологій, CASE-технології PAGEREF _Toc389947999 \h 42. Критерії надійності та якості інформаційних систем. PAGEREF _Toc389948000 \h 63. Застосування інформаційних технологій у виробництві PAGEREF _Toc389948001 \h 8Управленческий учет и отчетность PAGEREF _Toc389948002 \h 8Автоматизированные информационные системы PAGEREF _Toc389948003 \h 94. Застосування інформаційних технологій у банківській та фінансовій справі PAGEREF _Toc389948004 \h 125. Безпека функціонування інформаційних систем PAGEREF _Toc389948005 \h 156. Засоби моделювання автоматизованих інформаційних систем PAGEREF _Toc389948006 \h 187. Моделі життєвого циклу програмних засобів. PAGEREF _Toc389948007 \h 208. ER–модель. PAGEREF _Toc389948008 \h 219. Класифікація запитів PAGEREF _Toc389948009 \h 2310. Реляційна модель Кодда. Реляційна алгебра PAGEREF _Toc389948010 \h 2411. Функціонально повна залежність. 2-нормальна форма (2НФ). PAGEREF _Toc389948011 \h 2712. Мінімальна структура функціональних залежностей PAGEREF _Toc389948012 \h 2813. Аксіоми Армстронга PAGEREF _Toc389948013 \h 2914. Третя нормальна форма та третя нормальна форма Бойса-Кодда PAGEREF _Toc389948014 \h 3015. Багатозначні залежності. 4-нормальна форма PAGEREF _Toc389948015 \h 3116. Стратегії розподілу даних в розподілених базах даних PAGEREF _Toc389948016 \h 322. Системне програмування PAGEREF _Toc389948017 \h 331. Поняття мовного процесора. Типи мовних процесорів. Основні фази мовного процесора. PAGEREF _Toc389948018 \h 332. Скінченні автомати. Методика побудови лексичного аналізатора на основі скінченного автомата. PAGEREF _Toc389948019 \h 343. Регулярні множини та регулярні вирази, їх звязок із скінченними автоматами. Основні тотожності в алгебрі регулярних виразів. PAGEREF _Toc389948020 \h 354. Вивід у граматиці. Дерево виводу. Лівостороння та правостороння стратегії виводу. PAGEREF _Toc389948021 \h 365. LL(k)-граматики. Перевірка LL(1)-умови для довільної КВ- граматики PAGEREF _Toc389948022 \h 376. Побудова LL(1)-таблиці для управління LL(1)-синтаксичним аналізатором PAGEREF _Toc389948023 \h 387. Атрибутний метод визначення семантики програм. Синтезовані та успадковані атрибути. Порядок та правила обчислення атрибутів. PAGEREF _Toc389948024 \h 398. Машинно-орієнтовані мови програмування. Асемблери. Структура асемблера, перегляди тексту програми та відповідні бази даних. PAGEREF _Toc389948025 \h 403. Архітектура ЕОМ, комп’ютерні та інформаційні мережі PAGEREF _Toc389948026 \h 411. Розподіл оперативної пам’яті, поняття сегменту та зсуву. Сторінкова організація пам’яті. PAGEREF _Toc389948027 \h 412. Канали та порти вводу-виводу PAGEREF _Toc389948028 \h 423. Поняття про переривання та їх класифікація PAGEREF _Toc389948029 \h 434. Поняття про відеосистему. Режими роботи відеосистеми PAGEREF _Toc389948030 \h 455. Структура таблиці розміщення файлів на магнітних дисках. Фізичний та логічний формати магнітних дисків. Коренева директорія. PAGEREF _Toc389948031 \h 476. Системи телеобробки даних. Функціональне середовище для взаємодії систем телеобробки. Етапи у взаємодії систем телеобробки. PAGEREF _Toc389948032 \h 487. Модель відкритої системи, стек протоколів. Концепція еталонної моделі OSI. PAGEREF _Toc389948033 \h 498. Стек протоколів TCP/IP: топологічні особливості, функції рівнів. PAGEREF _Toc389948034 \h 509. Архітектура мережевої телеобробки: однорангова, клієнт/сервер, трирівнева PAGEREF _Toc389948035 \h 5210. Надійність систем телеобробки та комп’ютерних мереж. Класи безпеки. Міжмережеві екрани. Proxy-сервери, брандмауери. PAGEREF _Toc389948036 \h 5411. Мультиплексування цифрових каналів з розділенням у часі (TDM). Плезіохронні та синхронні цифрові ієрархії. Широкосмугові канали зв’язку. PAGEREF _Toc389948037 \h 5512. Повторювачі, мости, маршрутизатори, шлюзи та їх місце в профілі OSI PAGEREF _Toc389948038 \h 5613. Поняття мереж комутації: пакетів, каналів, повідомлень. Контроль перевантажень в мережах комутації пакетів. PAGEREF _Toc389948039 \h 5714. Інформаційна глобальна мережа INTERNET PAGEREF _Toc389948040 \h 5815. Система доменних імен глобальної мережі INTERNET PAGEREF _Toc389948041 \h 5916. Система електронної пошти глобальної системи INTERNET PAGEREF _Toc389948042 \h 6017. Поняття універсального вказівника ресурсу. Основні типи ресурсів PAGEREF _Toc389948043 \h 6118. Поняття раутінгу в мережах TCP/IP PAGEREF _Toc389948044 \h 6219. Технології, що забезпечують відмовостійкість мереж TCP/IP PAGEREF _Toc389948045 \h 6420. Класифікація комп’ютерних мереж. PAGEREF _Toc389948046 \h 654. Теорія програмування та обчислень PAGEREF _Toc389948047 \h 661. Основні аспекти програм PAGEREF _Toc389948048 \h 662. Основні поняття програмування PAGEREF _Toc389948049 \h 673. Методи подання синтаксису мов програмування PAGEREF _Toc389948050 \h 684. Класифікація породжувальних граматик PAGEREF _Toc389948051 \h 695. Автоматна характеристика основних класів мов PAGEREF _Toc389948052 \h 706. Метод нерухомої точки PAGEREF _Toc389948053 \h 717. Методи формальної семантики PAGEREF _Toc389948054 \h 738. Формальні методи програмування PAGEREF _Toc389948055 \h 749. Функції складності (сигналізуючі) за часом та за пам’яттю. Теорема про прискорення. PAGEREF _Toc389948056 \h 7510. Функції, елементарні за Кальмаром PAGEREF _Toc389948057 \h 7611. Співвідношення між класами примітивно рекурсивних та елементарних функцій PAGEREF _Toc389948058 \h 7712. Техніка слідів. Лема про заміщення PAGEREF _Toc389948059 \h 7813. Функції, обчислювані за реальний час PAGEREF _Toc389948060 \h 805. Системи штучного інтелекту PAGEREF _Toc389948061 \h 811. Знання. Класифікація знань PAGEREF _Toc389948062 \h 812. Фреймова модель задання знань PAGEREF _Toc389948063 \h 823. Семантичні мережі PAGEREF _Toc389948064 \h 834. Продукційна модель задання знань PAGEREF _Toc389948065 \h 855. Розпізнавання образів PAGEREF _Toc389948066 \h 866. Поняття діалогової системи та її компоненти PAGEREF _Toc389948067 \h 887. Теорія ігор. Експліцитні та імпліцитні дерева гри PAGEREF _Toc389948068 \h 898. Метод резолюцій як основа логічного виведення PAGEREF _Toc389948069 \h 929. Мова функціонального програмування ЛІСП PAGEREF _Toc389948070 \h 9310. Мова логічного програмування ПРОЛОГ PAGEREF _Toc389948071 \h 946. Обчислювальна геометрія, комп’ютерна графіка та комп’ютерна алгебра PAGEREF _Toc389948072 \h 951. Складність алгоритмів, зведення задач, нижні оцінки складності задач PAGEREF _Toc389948073 \h 952. Дерево відрізків та реберний список з подвійними зв’язками PAGEREF _Toc389948074 \h 963. Локалізація точки на планарному розбитті. Методи PAGEREF _Toc389948075 \h 974. Регіональний пошук. Методи PAGEREF _Toc389948076 \h 995. Побудова опуклої оболонки. Методи PAGEREF _Toc389948077 \h 1006. Найближча пара, метод «Розділяй та пануй» PAGEREF _Toc389948078 \h 1027. Означення та властивості діаграми Вороного. Побудова діаграми Вороного. PAGEREF _Toc389948079 \h 1038. Перетин та об’єднання опуклих многокутників. Перетин відрізків PAGEREF _Toc389948080 \h 1049. Поняття замкненого півкільця. Приклади PAGEREF _Toc389948081 \h 10610. Лінійні коди. Алгебраїчна характеризація лінійних кодів. Породжуюча та перевірочна матриці. PAGEREF _Toc389948082 \h 10710. Простий многочлен над скінченним полем та поле остач від ділення на цей многочлен PAGEREF _Toc389948083 \h 10811. Кільце остач від ділення на многочлен над скінченним полем PAGEREF _Toc389948084 \h 109

1. Інформаційні технології та інформаційні системи1. Інструментальні засоби розробки інформаційних технологій, CASE-технологіїТенденції розвитку сучасних інформаційних технологій ведуть до постійного зростання складностi розроблюваних інформаційних систем (ІС), що використовуються в різноманітних напрямках економіки та управління. Сучасні проекти ІС характеризуються, як правило, такими особливостями:
складність опису (досить велика кількість функцій, процесів, даних і складні взаємозв'язки між ними ), що вимагають ретельного моделювання та аналізу даних і процесів їх обробки;
наявність сукупності тісно пов'язаних компонентів (підсистем), кожна з яких має свої локальні задачі та методи функціонування (наприклад, прикладні системи, що пов'язані з обробкою запитів користувачів та виконанням регламентних завдань, автоматизовані системи аналітичної обробки даних для підтримки прийняття рішень);
відсутність прямих аналогів, що обмежує можливість використання накопичених в попередніх розробках типових проектних рішень і прикладних підсистем;
необхідність інтеграції існуючих і нових підсистем;
функціонування в неоднорідному середовищі на різних апаратних та операційних платформах;
розрізненість окремих розробників за їх спеціалізацією та використовуваними інструментальними засобами;
істотна протяжність проекту в часі, що зумовлена обмеженими можливостями колективу розробників і організації-замовника ІС.
Для успішної реалізації проекту ІС повинна бути адекватно описана, мають бути побудовані повні і несуперечливі функціональні і інформаційні моделі ІС. Накопичений до цього часу досвід проектування ІС показує, що це логічно складна, трудомістка і тривала в часі робота, що вимагає високої кваліфікації учасників розробки. Проте до недавнього часу проектування ІС виконувалося в основному на інтуїтивному рівні із застосуванням неформалізованих засобів, що засновані на мистецтві, практичному досвіді, експертних оцінках і дорогих експериментальних перевірках якості функціонування ІС. Крім того, у процесі створення і функціонування ІС інформаційні потреби користувачів можуть змінюватися або уточнюватися, що додатково ускладнює опрацювання і супровід таких систем і породжує наступні проблеми:
неадекватна специфікація вимог;
нездатність виявляти помилки в проектних рішеннях;
низька якість документації, що знижує її експлуатаційні якості;
затяжний цикл розробки і незадовільні результати тестування.
Перелічені чинники сприяли появі програмно-технологічних засобів спеціального класу - Case-засобів, що реалізують Case-технологію створення і супроводу ІС. Термін Case (Computer Aided Software Engineering ) використовують в цей час в надто широкому розумінні. Початкове значення терміну Case, обмежене питаннями автоматизації опрацювання тільки лише програмного забезпечення (ПЗ ), зараз придбало новий зміст, що охоплює процес опрацювання складних ІС в цілому. Тепер під терміном Case-засобу мають на увазі програмні засоби, що підтримують процеси утворення і супроводу ІС, включаючи аналіз та формулювання вимог, проектування прикладного ПЗ (додатків ) і баз даних, генерацію коду, тестування, документування, забезпечення якості, конфігураційне управління і управління проектом, а також інші процеси. Case-засоби разом із системним ПЗ і технічними засобами утворюють повне середовище опрацювання ІС.
Програмування перейняло риси системного підходу з опрацюванням і впровадженням мов високого рівня, засобів структурного і модульного програмування, мов проектування і засобів їх підтримки, формальних і неформальних мов опису системних вимог і специфікацій та ін. Крім того, появі Case-технології сприяли і такі чинники, як: підготовка аналітиків і програмістів, що сприймають концепції модульного і структурного програмування; широке впровадження і постійне зростання потужності комп'ютерів, що дозволили використати ефективні графічні засоби і автоматизувати більшість етапів проектування; впровадження мережної технології, що надала можливість об'єднання зусиль окремих виконавців в єдиний процес проектування шляхом використання розподіленої бази даних, що містить необхідну інформацію про проект.
Зважаючи на різноманітну природу Case-засобів було б помилково робити якісь беззастережні висновки щодо реального задоволення тих чи інших очікувань від їх впровадження. Можна перерахувати такі чинники, що ускладнюють визначення можливого ефекту від використання Case-засобів:
широка розмаїтість якості і можливостей Case-засобів;
надто невеликий час використання Case-засобів в різноманітних організаціях і відсутність досвіду їх застосування;
широка розмаїтість в практиці впровадження різноманітних організацій;
відсутність детальних метрик і даних для уже виконаних і поточних проектів;
широкий діапазон предметних областей проектів;
різноманітна міра інтеграції Case-засобів в різноманітних проектах.
Із-за цих складностей доступна інформація про реальні впровадження вкрай обмежена і протирiчлива. Вона залежить від типу засобів, характеристик проектів, рівня супроводу і досвіду користувачів. Деякі аналітики вважають, що реальна користь від використання деяких типів Case-засобів може бути одержана тільки після одно- або дворічного досвіду. Інші вважають, що вплив може реально виявитися лише у фазі експлуатації ІС, коли технологічні поліпшення можуть привести до зниження експлуатаційних витрат. Для успішного впровадження Case-засобів організація повинна володіти такими якостями:
Технологія. Розуміння обмеженості існуючих можливостей і спроможність прийняти нову технологію;
Культура. Готовність до впровадження нових процесів і взаємовідносин між розробниками і користувачами;
Управління. Чітке керівництво і організованість по відношенню до найбільш важливих етапів і процесів впровадження.
Прикладами Case-засобів можуть виступати:
засоби моделювання даних (DBMS, DDL);
засоби трансформації моделей;
засоби трансформації програм (Stratego/XT, TXL, DMS);
засоби для рефакторингу (Eclipse, NetBeans, ReSharper);
засоби автоматичної генерації коду (IDE);
засоби UML;
програмні специфікації;
документація.

2. Критерії надійності та якості інформаційних систем.Критерії якості ІС згідно до стандартів ISO:
З точки зору користувача З точки зору розробника
відповідність функціональним вимогам;
здатність взаємодіяти із середовищем (інтерфейс);
відповідність призначенню;
придатність до використання;
зрозумілість і точність інформації;
зручність і простота в роботі;
швидкодія та час відгуку;
споживання ресурсів;
захищеність від злому даних і інших злочинних зазіхань;
зрілість ("обкатаність");
переносимість;
легка інсталяція;
документованість ефективність;
надійність;
стійкість до відмов;
здатність відновлюватися після збоїв;
відтестованість;
аналізованість (можливість діагностики причин помилок і співставлення з вихідним кодом);
супровідність;
придатність до внесення змін та розвинення;
відповідність нормам із переносимості й інсталяції;
Критерії, які визначають надійність системи:
захищеність від помилок користувача (випадкових та навмисних);
стійкість до апаратних відмов;
система захисту від злому та крадіжки даних;
резервне копіювання даних;
здатність відновлюватися після збоїв.
Фундаментальні принципи побудови інформаційних систем, які визначають їх якість (перетинаються з вимогами стандарту ISO):
1. Адекватність відображення предметної області. Для дотримання цього очевидного принципу необхідно тісна взаємодія проблемного користувача й проектувальника. Оцінити адекватність може тільки кваліфікований фахівець проблемної області.
2. Можливість підготовки інформації для прийняття рішень в умовах творчого процесу, що слабо піддається формалізації. Тут, насамперед, система повинна давати можливість відповіді на невідомі заздалегідь запити користувача.
3. Можливість постійного розширення наданих користувачу зрізів інформації. У процесі використання системи зростають побажання користувача щодо розширення кола одержуваної інформації.
4. Здатність адаптуватись до умов, що змінюються. У процесі життя системи змінюються предметна область, бажання користувача, технічні й програмні засоби і таке інше.
5. Здатність функціонувати в реальних умовах людської діяльності. Людська діяльність у значній мірі здійснюється не за формальними правилами, багато чого залежить від конкретного суб'єкта. Система повинна функціонувати у відповідних умовах.
6. Забезпечення перевірки вірогідності даних при введенні в систему. При введенні даних користувач може робити як випадкові, так і навмисні помилки. Система повинна контролювати введення даних.
7. Можливість взаємодії з користувачами різних категорій і в різних режимах. Користувачі можуть розрізнятися за рівнем знань, по кваліфікації, за рівнем доступу, по ієрархії. Система повинна враховувати відповідні рівні й режими роботи.
8. Технологічність обробки даних (дружній інтерфейс, прийнятні часові характеристики об'єкта тощо) Припустимий час відгуку залежить від частоти запиту, складності запиту і може змінюватися в широких межах.
9. Забезпечення таємності даних, надійності, цілісності, захисту від випадкового чи навмисного руйнування або крадіжки. Професійні виробники програмних продуктів давно вже змогли переконатися, що найбільш вірний спосіб поліпшити програми – це удосконалити процеси їх створення.
Для визначення загального рівня розвитку технологічних процесів у програмних організаціях SEI і Університет Карнегі-Меллона розробили спеціальну систему оцінки зрілості технологічних процесів в організаціях, що спеціалізуються на випуску ПЗ. Запропонована ними модель Capability Maturity Model (CMM) заснована на так називаних рівнях зрілості (maturity levels). Усього їх п'ять, і кожний із них характеризує визначений ступінь якості, що випускаються виробів.
Рівень 1. Початковий (initial).
З цього рівня починає свою діяльність більшість організацій. На даному етапі процес розробки носить неструктурований і випадковий характер. Комерційний успіх, якщо він супроводжує проекти, визначається скоріше видатними здатностями якого-небудь талановитого розроблювача або менеджера, ніж організаційною інфраструктурою компанії. У організації відсутнє стабільне середовище розробки й супроводу. Терміни випуску продуктів, як правило, не витримують. У кризовій ситуації фірма "забуває" про попередньо складені плани і всі сили кидає на кодування й тестування програми. ПЗ оцінках SEI, у даний час біля 75% софтверних фірм перебувають на початковому рівні.
Рівень 2. Повторюваний (repeatable).
Успішна реалізація проектів стає можливою завдяки жорсткому управлінню, плануванню та контролю. Акцент у даному випадку робиться на виробітку вихідних вимог, методи оцінки і конфігураційний менеджмент. Розробка нових проектів ведеться на основі раніше накопиченого досвіду і відповідно до визначених стандартів на розробку ПО. Даний рівень може забезпечити біля 15% організацій. Як показує практика, перехід із першого рівня на другий найбільш складний, оскільки вимагає комплексного впровадження основних технологічних процедур.
Рівень 3. Фіксований (defined).
Процеси, що відносяться до сфери управління й інженерної діяльності, повністю документовані, стандартизовані й інтегровані в єдиний технологічний потік, контрольований керівним персоналом.
Цей рівень у стані підтримувати 8% софтверних компаній.
Рівень 4. Керований (managed).
Організації намагаються оцінити якість процесів і готового продукту кількісно. Для контролю над процесами використовуються кількісні показники (метрики). Усі процеси передбачувані й, укладаються в заздалегідь визначені рамки. Даного рівня досягло біля 1,5% організацій.
Рівень 5. Такий, що оптимізується (optimizable).
Компанії прагнуть поліпшити свою роботу, керуючись кількісними критеріями якості. Є засоби локалізації вузьких місць у виробничих процесах. Основна ціль - випуск бездефектних продуктів, у яких усі помилки усунуті ще на стадії внутрішнього тестування.
Тільки 0,5% компаній можуть підтримувати настільки високий рівень технологічної зрілості.


3. Застосування інформаційних технологій у виробництвіСовременные корпоративные информационные системы (КИС) играют очень важную роль в бизнесе. КИС отражает концептуальную и физическую архитектуры организации и сопровождает ее многофункциональную деятельность.
Основой КИС предприятий на современном этапе являются так называемые системы планирования ресурсов предприятий (Enterprise Recourse Planning - ERP). Мировой опыт свидетельствует, что умело выбранная и внедренная ERP-система существенно улучшает управляемость предприятием и повышает эффективность его работы.
Управленческий учет и отчетностьПостроение корпоративной информационной системы должно начинаться с анализа структуры управления организацией и соответствующих потоков данных и информации. Координация работы всех подразделений организации осуществляется через органы управления разного уровня. Под управлением понимают обеспечение поставленной цели при условии реализации следующих основных функций: организационной, плановой, учетной, анализа, контрольной, стимулирования (краткое содержание этих функций было рассмотрено выше).
В последние годы в сфере управления все активнее стали применяться понятие "принятие решения" и связанные с этим понятием системы, методы, средства поддержки принятия решений. Принятие и исполнение делового решения - акт формирования и целенаправленного воздействия на объект управления, основанный на анализе ситуации, определении цели, разработке политики и программы (алгоритма) достижения этой цели.
Первым шагом на пути к эффективному управлению является создание системы сбора, оперативной обработки и получения оперативной, точной и достоверной информации о деятельности предприятия - системы для реализации управленческого учета.
Управленческий учет представляет собой проблему для значительной части руководителей предприятий в основном из-за отсутствия соответствующей системы обработки и представления данных, на основе которых принимаются решения. Иногда сведения, получаемые руководством для контроля и принятия решений, формируются из системы финансовой отчетности, кадрового учета и т. д. Проблема состоит в том, что эти сведения служат специфическим целям и не отвечают потребностям руководства для принятия решений. Поэтому на многих предприятиях существуют параллельно две системы учета - бухгалтерский и управленческий (практический), т. е. служащий обеспечению выполнения повседневных рабочих задач сотрудников и руководителей предприятия. Как правило, такой учет ведется по принципу "снизу-вверх". Сотрудники для выполнения своей работы фиксируют необходимые им данные (первичную информацию). Когда руководству нужно получить какие-то сведения о положении дел на предприятии, оно обращается с запросами к менеджерам более низкого уровня, а те, в свою очередь, к исполнителям.
Следствием такого самопроизвольного подхода к формированию системы отчетности является то, что, как правило, возникает конфликт между той информацией, которую хочет получить руководство, и теми данными, которые могут предоставить исполнители. Причина этого конфликта очевидна - на разных уровнях иерархии предприятия требуется разная информация, а при построении системы отчетности "снизу-вверх" нарушается основной принцип построения информационной системы - ориентация на первое лицо. Исполнители обладают либо не теми видами данных, которые нужны руководству, либо нужными данными не с той степенью детализации или обобщения.
Большинство руководящих работников действительно получают отчеты о работе своих отделов, но эти сведения либо излишне пространны (например, подшивка договоров о продаже вместо сводного отчета с приведением цифр об общем объеме сбыта за указанный период), либо, наоборот, недостаточно полны. Кроме того, сведения поступают с запозданием - например, можно получить сведения о дебиторской задолженности через 20 дней по окончании месяца, а между тем отдел сбыта уже отгрузил товары заказчику с просроченным последним платежом. Неточные данные могут быть причиной неверных решений. Точные данные, полученные с запозданием, также теряют ценность.
Для того чтобы руководство предприятия могло получать данные, необходимые ему для принятия управленческих решений, необходимо строить систему отчетности "сверху вниз", формулируя потребности верхнего уровня управления и проецируя их на нижние уровни исполнения. Только такой подход обеспечивает получение и фиксирование на самом низшем исполнительском уровне таких первичных данных, которые в обобщенном виде смогут дать руководству предприятия ту информацию, в которой оно нуждается.
Важнейшими требованиями к системе управленческого учета являются своевременность, единообразие, точность и регулярность получения информации руководством предприятия. Эти требования могут быть реализованы при соблюдении ряда простых принципов построения системы управленческой отчетности:
система должна быть ориентирована на лиц, принимающих решения, и на сотрудников аналитического отдела;
система должна строиться "сверху вниз", руководители каждого уровня должны проанализировать состав и периодичность данных, необходимых им для выполнения своей работы;
исполнители должны иметь возможность фиксирования и передачи "наверх" установленных их руководством данных;
данные должны фиксироваться там, где порождаются;
информация разной степени детализации должна становиться доступной всем заинтересованным потребителям сразу же после ее фиксирования.
Очевидно, что эти требования наиболее полно могут быть реализованы с помощью автоматизированной системы. Однако опыт упорядочения систем управленческой отчетности на различных предприятиях показывает, что внедрению автоматизированной системы управленческого учета должна предшествовать достаточно большая "бумажная" работа. Ее выполнение позволяет промоделировать различные особенности управленческой отчетности предприятия и тем самым ускорить процесс внедрения системы и избежать многих дорогостоящих ошибок.
Автоматизированные информационные системыТермин "автоматизированные системы управления" (АСУ), впервые появился в России в 1960-е гг. ХХ века в связи с применением компьютеров и информационных технологий в управлении экономическими объектами и процессами, что дало возможность повысить эффективность производства, лучше использовать ресурсы, избавить управленцев от выполнения обязательных рутинных операций.
Для любого предприятия возможность повышения эффективности производства в первую очередь определяется эффективностью существующей системы управления. Скоординированное взаимодействие между всеми подразделениями, оперативная обработка и анализ получаемых данных, долговременное планирование и прогнозирование состояния рынка - вот далеко не полный перечень задач, которые позволяют решить внедрение современной автоматизированной системы управления.
В связи с этим, говоря о возросшем интересе российских предприятий к внедрению автоматизированных систем управления, нельзя не отметить, что в настоящее время на отечественном рынке преобладают две основные тенденции их разработки и внедрения.
Первая заключается в том, что предприятие пытается постепенно внедрить системы автоматизации лишь на отдельных участках своей деятельности, предполагая в дальнейшем объединить их в общую систему либо довольствуясь "кусочной" ("лоскутной") автоматизацией. Несмотря на то, что этот путь на первый взгляд кажется менее затратным, опыт внедрения таких систем показывает, что минимальные затраты в подобных проектах чаще всего оборачиваются и их минимальной отдачей, а то и вовсе не приносят желаемого результата. К тому же сопровождение и развитие таких систем чрезвычайно затруднено и затратно.
Вторая тенденция - комплексное внедрение систем автоматизации, что позволяет охватить все звенья системы менеджмента - от низового уровня производственных подразделений до верхнего управленческого уровня. В этом случае такая система включает в себя:
автоматизацию многих направлений деятельности предприятия (бухгалтерский учет, управление персоналом, сбыт, снабжение и т. д.);
автоматизацию основных технологических процессов предприятия;
автоматизацию собственно управленческих процессов, процессов анализа и стратегического планирования.
В настоящее время в мировой практике для обозначения полнофункциональных интегрированных АСУ, используемых предприятиями, применяют следующие названия:
MRP (Material Requirement Planning - Планирование материальных потребностей),
MRP II (Manufacturing Resource Planning - Планирование производственных ресурсов),
ERP-система (Enterprise Resource Planning -Планирование ресурсов предприятия),
ERP-II и CSRP (Customer Synchronized Relationship Planning - Планирование ресурсов, синхронизированное с покупателем).
Какая-либо однозначная и общепринятая общая классификация ИТ- предприятий отсутствует. Возможный вариант обобщенной структуры современных информационных технологий, внедряемых на промышленных производствах различного типа, приведен на рис., на котором сделаны следующие общепринятые сокращения (часть из них была представлена выше):

Рис.
САПР - системы автоматизированного проектирования/изготовления (Computer Aided Design / Computer Aided Manufacturing - CAD/CAM);
АСТПП - автоматизированные системы технологической подготовки производства (Computer Aided Engineering - CAE);
АСУТП - автоматизированные системы управления технологическими процессами (Supervisory Control And Data Acquisition - SCADA);
АСУП - комплексная автоматизированная система управления предприятием (Enterprise Resource Planning - ERP)
WF - потоки работ (WorkFlow);
CRM - управление отношениями с клиентами;
B2B - электронная торговая площадка ("онлайновый бизнес");
DSS - поддержка принятия управленческих решений;
SPSS - статистический анализ данных;
OLAP - анализ многомерных данных;
MIS - управляющая информационная система, (АРМ) руководителя;
SCM - управление цепями поставок;
PLM - управление жизненным циклом продукции (характерно для дискретного производства);
ERP-II - расширение ERP-системы за контуры производства (т. е. ERP + CRM + B2B + DSS + SCM+ PLM и т. п.);
HR - "Управление персоналом"; можно рассматривать и как самостоятельную задачу, и как входящую в состав ERP (что и отображено на рисунке в виде двух связей);
LAN - локальные вычислительные сети (Local Area Net);
WAN - глобальные (внешние) сети и телекоммуникации (Wide Area Net).
С точки зрения внедрения информационных технологий, все предприятия можно разделить на два больших класса: предприятия с дискретным типом производства (дискретное производство) и предприятия с непрерывным производством (непрерывное производство). Для непрерывного производства внедрение САПР (CAD/CAM) сводится в основном к внедрению графических систем.
В то же время возрастает роль ТПП, и задачи ТПП значительно расширяются в сторону технологических расчетов, моделирования технологических процессов. Автоматизированные системы технологической подготовки производства - АСТПП (CAE) - начинают играть решающую роль в организации производства (процесс в непрерывном производстве практически невозможно организовать без технологических расчетов и моделирования).
Для непрерывного производства весьма актуальным становится внедрение автоматизированных систем управления технологическими процессами - АСУТП (SCADA), от эффективности которых прямо зависит эффективность производства. Основу большинства SCADA-решений составляют несколько программных компонентов (база данных реального времени, устройства ввода/вывода, предыстории типовых и аварийных ситуаций и т. д.) и администраторов (доступа, управления, сообщений). Своя особая специфика присуща и внедрению на непрерывном производстве комплексной автоматизированной системы управления предприятием - АСУП.


4. Застосування інформаційних технологій у банківській та фінансовій справіСучасні можливості банківських інформаційних систем.
Аналіз практики показує, що в зарубіжних банках інформаційні технології охвачують тепер усі аспекти банківської справи, зокрема забезпечують:
клірингові операції (взаємні розрахунки банків);
торгові операції і маркетинг, управління касовими ресурсами;
управління діяльністю банку;
кредитні операції, включаючи аналіз заявок клієнтів на їх кредитоспроможність;
системи електронних платежів (SWIFT);
використання банківських автоматів;
банківські операції по телефону і обслуговування на дому;
використання різних платіжних карток;
електронну пошту і канцелярію;
безпаперовий документообіг у банку і при взаємодіях центр - філіали, банк клієнти;
фондовий ринок і операції з цінними паперами;
аналіз інвестицій і фінансового ринку;
автоматизацію розрахунків у торгових точках.
Автоматизація банківської справи передбачає широке використання комп'ютерних інформаційних систем у банках, автоматизацію обробки платіжних документів у відділах, які працюють із клієнтами, в операційних відділах, а також - автоматизацію фінансових операцій в рамках міжнародного банківського бізнесу.
Автоматизація банківських операцій дозволяє;
виконувати безпаперові платіжні операції з мінімальним залученням праці людей і скороченням організаційних витрат;
проводити обробку платежів переважно в реальному часі, за виключенням підведення бухгалтерських звітів у кінці дня і звітності по них;
прискорювати обмін інформацією між банками і клієнтами, банками і їх відділеннями за допомогою комунікаційних ліній зв'язку;
мінімізувати типові види банківського ризику (втрата документів, помилкова адресація, фальсифікація платіжних документів та ін.);
забезпечувати керівників стратегічними оцінками положення банку в умовах конкуренції, організації роботи і кадрової політики.
І саме важливе те, що банківські комп'ютерні системи відрізняються від інших в першу чергу тим, що інформація, яка опрацьовується ними повинна бути надійно захищеною від сторонніх зазіхань, а сама система повинна мати властивості підвищеної життєвості і безвідмовності в роботі.
Використання телекомунікацій у банківській справі
Потреба в оперативному зв'язку зі своїми партнерами по всьому світу суттєво підштовхнула розробку глобальних комп'ютерних мереж послугами яких сьогодні користується велика кількість людей самих різних спеціальностей. Можливість обробляти і передавати ділову інформацію з допомогою комп'ютерів у першу чергу оцінили діячі військово-промислового комплексу і банкіри. Одна з найбільш відомих комп'ютерних мереж, яка створена з ініціативи фінансових організацій - це мережа SWIFT.
Всі існуючі сьогодні в світі електронні системи обробки банківських операцій можна умовно розділити на системи банківських повідомлень і системи розрахунків. У рамках перших проводиться оперативна пересилка і зберігання міжбанківських документів, а функції других зв'язані безпосередньо з виконанням взаємних вимог і зобов'язань.
Під «банківською мережею», як правило розуміють логічну віртуальну мережу.
SWIFT є типовим прикладом використання в архітектурі мережі, мереж пакетної комутації.
Міжнародна міжбанківська мережа SWIFT
Уже в кінці 60-х років стало очевидним, що потужність систем обробки банківської інформації (систем розрахунків) недостатньо надійна і швидка. Ручна обробка документів не дозволяла швидко обмінюватися інформацією між більшістю банків, їх філіалами по всьому світу. Крім того ручна обробка приводила до помилок, збоїв у роботі. Різні банки застосовували різні системи розрахунків, що приводило до їх практичної несумісності. Це підштовхнуло фахівців європейських і північноамериканських банків до необхідності розробки і створення єдиної «мови» фінансових повідомлень, єдиної системи передачі банківської інформації.
Переваги SWIFT:
підвищення ефективності роботи банків за рахунок використання стандартизації і сучасних способів передачі інформації;
забезпечення надійності при передачі повідомлень (кодування і спеціальний порядок передачі і прийому);
прямий доступ банків - учасників SWIFT до своїх кореспондентів, відділень і філіалів, які розміщені по всьому світу за 20 хвилин, а термінові - за 5;
використання стандартизованих повідомлень, дозволяє усувати язикові бар'єри і зменшити відмінності в практиці виконання міжнародних банківських операцій;
гарантія безпеки передачі даних (захист від підробок, втрати інформації і залишення платіжних доручень і фінансових повідомлень без відповіді).
Концепція повідомлень у міжнародній міжбанківській мережі.
Система SWIFT представляє собою міжнародну міжбанківську мережу для зберігання і передачі фінансової інформації. Дані передаються в мережі у вигляді структурних повідомлень, кожна з яких призначена для виконання певної фінансової операції. Для підключення вузла система індивідуально підтверджує прийом повідомлень і їх обробку.
Безпека міжбанківської мережі.
Високий рівень безпеки забезпечується системою контролю доступу до мережі, яка включає в себе місцеві паролі двох вузлів і журнальні файли в яких зберігається інформація про підключення до мережі. Вся інформація, яка передається в системі SWIFT шифрується.
Надійність і безперервність роботи системи.
Система працює безперервно 24 години на добу і 365 днів у році. Щоденно всі користувачі отримують звіт, в якому міститься важлива інформація про роботу мережі. Такий звіт може розсилатися автоматично або по спеціальному запиту. Крім того в любий момент є можливість зв'язатись зі спеціалістом для вияснення питання, яке виникло в ході експлуатації системи.
До банковських технологій (або автоматизованих банківських систем - АБС) як приклад можна віднести як мінімум модуль для внутрішньої бухгалтерії ("операційний день"), ПО для роботи в S.W.I.F.T чи в режимі "клієнт-банк".
ПЗ, кваліфіковано розроблене тим чи іншому банку, як правило, краще враховує специфічні особливості його спектра операцій, чим придбане "на стороні". Однак сегмент ринку потенційних покупців такого ПЗ значно вже, і перспективи гарної технологічної підтримки з боку банку-розроблювача більш проблематичні. У фірми, що спеціалізується на розробці АБС - ПЗ, навпаки, більш універсально (доробка й адаптація можуть знадобитися тільки в окремих банках) і можливості технічної підтримки набагато вище. Бувають і більш складні випадки, коли ПЗ створюється спільними зусиллями. Тут потрібно врахувати і та обставина, що банк при продажі ПЗ власної розробки іншому банку в тім чи іншому ступені буде підтримувати свого конкурента. Видимо, тому найбільшу популярність таке ПЗ одержує тільки у власних відділеннях і філіях. Хоча число впроваджень закордонних АБС щодо вітчизняних розробок може показатися зовсім невеликим (за даними "CW-M", * 7, 1994, менш чим у 10% усіх банків), однак вони приходяться на досить великі банки, що мають чималу фінансову вагу.
Переважна більшість таких АБС інстальована в Росії на мейнфреймах і міні-комп'ютерах (у тому числі на RISC-станціях). Про постачання їхніх варіантів, орієнтованих на ПК, практично нічого не відомо (хоча пропозиції є), видимо, унаслідок високого рівня конкуренції у цьому сегменті значно більш дешевих вітчизняних розробок (більш 50 найменувань). ПЗ загальній думці, покупки закордонних АБС до цього часу стримувалися їхніми основними недоліками (з погляду російських банків): - орієнтація винятково на закордонні системи бухуобліку; - високий рівень складності й вартості покупки (і експлуатації); - відсутність, як правило, вихідних текстів для адаптації. Як основні недоліки вітчизняних АБС (з тієї ж позиції) можна привести наступні: - більш вузьке коло орієнтації в змісті комп'ютерних платформ (гнітюче число таких АБС застосовне тільки на ПК у середовищі DOS); - недостатня інтегрованість і повнота функцій; - застарілі методи розробки (без CASE-технологій), що знижують можливість технічної підтримки й розвитку системи.
Усі розробки, орієнтовані тільки на ПК, виконані в середовищі MS-DOS: Windows у них поки не застосовується через менші вимоги до графічного інтерфейсу при банківських операціях у порівнянні, наприклад, із ГІС. Випадки використання спеціальних DOS-подібних ОС, наприклад, QNX, практично одиничні, за винятком мультизадачних оболонок типу VM/386. Значна частина розробок АБС для DOS (по оцінці автора, близько 90%) має мережні версії для середовища NetWare фірми Novell. Більш складно оцінити, які саме інструментальні засоби в цьому сегменті найбільш популярні, тому що їхнє загальне число складає біля десяти і, крім того, застосовуються СУБД власної розробки. Важливість використання того або іншого засобу дуже велика: від цього часто залежать основні характеристики АБС (швидкодія при пошуку записів у БД і т.д.).
У 1993 р. у даному сегменті одержали розвиток АБС, орієнтовані на архітектуру клієнт/сервер. Для цього використовувалися різні SQL-засоби, наприклад, Sybase SQL Server for NetWare, Microsoft SQL Server і т.д.
Інша проблема АБС цього сегмента - гарантія надійного захисту даних. Для забезпечення більшої безвідмовності роботи в мережі використовують такі засоби, як NetWare Transaction Tracking System, NetWare 3.11 SFT III. Для забезпечення конфіденційності даних застосовують програмні засоби криптування й електронного підпису, а також різні апаратні засоби (найбільш популярна плата "Криптон-3"). АБС для ПК із MS-DOS характеризується, як правило, що випливають граничними параметрами: число робочих місць - від 15 до 50, клієнтів банку - від 3 тис. до 50 тис., оброблюваних документів у день - від 2,5 тис. до 50 тис. Загальна вартість такої вітчизняний АБС рідко перевищує 10 тис. дол., при цьому вартість навчання персоналу може складати 15 - 25% від цієї суми. Наявність у цьому сегменті явних лідерів із своєю дилерською мережею, видимо, приведе до зниження числа фірм-розроблювачів таких АБС (через їхню складність) при загальному рості обсягу їх постачань (тому що попит досить високий) і вартості (через розширення набору функцій, таких як робота з кредитними картками і т.д.).
Розроблювачі ПЗ для банків активно переводять свої розробки на платформи Unix. Число банків
України з інстальованими Unix- системами поки складає кілька відсотків від усього банківського сектора, але відносний розмір цієї частки постійно росте.
Схоже, що лідируюче місце ПЗ числу інсталяцій в Україні займають різні АБС на базі СУБД Informix. Успішний розвиток цього напрямку, видимо, зв'язано також із наявністю представництва Informix у Росії і розвитій дилерській мережі. Немаловажним фактором є і відносно низька вартість цієї СУБД. Судячи з даних різних джерел, друге місце в цьому сегменті займають АБС на базі СУБД Oracle. Це багато в чому зв'язане з тривалим періодом існування представників Oracle в Україні і більшій універсальності цієї СУБД стосовно комп'ютерних платформ (у тому числі і не тільки під ОС Unix).
Приблизно третє місце займає АБС на базі СУБД Progress.

5. Безпека функціонування інформаційних системВимоги по забезпеченню безпеки в різних ІС можуть істотно відрізнятися, однак вони завжди спрямовані на досягнення трьох основних властивостей: цілісність - інформація, на основі якої приймаються рішення, повинна бути достовірної і точної, захищеної від можливих ненавмисних і злочинних перекручень; приступність (готовність) - інформація і відповідні автоматизовані служби повинні бути доступні, готові до роботи завжди, коли в них виникає необхідність; конфіденційність - засекречена інформація повинна бути доступна тільки тому, кому вона призначена.
Для вирішення проблем інформаційної безпеки необхідне сполучення законодавчих, організаційних, технологічних і стандартизаційних заходів.
У той же час, на реальні складні системи впливають і випадкові (ненавмисні) дестабілізуючі фактори, здатні викликати аномалії функціонування і навіть катастрофічні наслідки, часом більш важкі, чим наслідки злочинних дій, наприклад, загибелі цивільного літака.
Найбільше повно безпека ІС характеризує величина збитку, можливого при прояві дестабілізуючих факторів і реалізації конкретних погроз безпеки, а також середній час між проявами погроз, що порушують безпеку. Однак описати і виміряти в досить загальному виді можливий збиток при порушенні безпеки для критичних ІС різних класів практично неможливо, тому реалізації погроз доцільно характеризувати інтервалами часу між їхніми проявами, чи наробітком на відмовлення, що відбиваються на безпеці. Це зближає поняття і характеристики ступеня безпеки з показниками надійності ІС.
Досить універсальним вимірюваним параметром при цьому залишається час відновлення нормальної працездатності.
Стійкість (живучість) найбільше широко характеризує здатність ІС до безвідмовного функціонування при наявності збоїв і відмовлень.
У різних ІС ресурси на забезпечення надійності і безпеки можуть складати від 5-20% до 100-300% від ресурсів, використовуваних на вирішення функціональних задач, тобто в особливих випадках (критичні військові системи) можуть перевищувати останні в 2-4 рази. У більшості цивільних систем засобу забезпечення безпеки звичайно вимагають 5-20% усіх видів ресурсів.
Засобу генерації тестів і імітації зовнішнього середовища призначені для підготовки вихідних даних при перевірці різних режимів функціонування ІС.
Внутрішніми джерелами погроз безпеки функціонування складних ІС є: системні помилки при постановці цілей і задач проектування ІС, формулюванню вимог до функцій і характеристик вирішення задач, визначенні умов і параметрів зовнішнього середовища, у якій має бути застосовувати ІС; алгоритмічна помилки проектування при безпосередній алгоритмізації функцій програмних засобів і баз даних, при визначенні структури і взаємодії компонентів комплексів програм, а також при використанні інформації баз даних; помилки програмування в текстах програм і описах даних, а також у вихідній і результуючій документації на компоненти ІС; недостатня ефективність використовуваних методів і засобів оперативного захисту програм і даних і забезпечення безпеки функціонування ІС в умовах випадкових негативних впливів.
Зовнішніми дестабілізуючими факторами, що створюють погрози безпеки функціонування перерахованих об'єктів уразливості ІС є: помилки оперативного й обслуговуючого персоналу в процесі експлуатації ІС; перекручування в каналах телекомунікації інформації, що надходить від зовнішніх джерел і передавала споживачів, а також неприпустимі зміни характеристик потоків інформації; збої і відмовлення апаратури; зміни складу і конфігурації ІС за межі, перевірені при іспитах чи сертифікації.
Повне усунення перерахованих погроз принципово неможливо. Завдання полягає у виявленні факторів, від яких вони залежать, у створенні методів і засобів зменшення їхнього впливу на безпеку ІС, а також в ефективному розподілі ресурсів для забезпечення захисту, що є однаково міцним відносно всіх негативних впливів.
Однак помилки персоналу, перекручування даних у каналах телекомунікації, а також випадкові (при відмовленнях частини апаратури) і необхідні зміни конфігурації обчислювальних засобів залишаються істотними погрозами безпеки ІС.
Безпосередньою метою тестування є виявлення, локалізація й усунення помилок у програмах і даних. Важливою особливістю тестування складних критичних ІС є необхідність досить повної їхньої перевірки при обмеженій тривалості іспитів.
Тому для забезпечення високої якості доцільно проводити іспити не тільки завершеної ІС, але на ряді проміжних етапів розробки перевіряти стан і характеристики компонентів проекту.
Для посвідчення якості і безпеки застосування складних критичних ІС використовувані в них ПЗ і БД варто піддавати обов'язковій сертифікації. Однак сертифікація засвідчує якість і безпеку застосування ІС тільки в умовах, обмежених конкретними стандартами і нормативно-технічними документами, із деякою кінцевою імовірністю.
Тестування ефективності захисту від перекручень вихідних даних служить для виявлення помилок у програмах, що виявляються при помилкових чи перекручених даних.
Тестування зручності і якості підготовки користувацьких версій ІС служить для виявлення помилок методів і засобів настроювання базових версій ІС до конкретних умов застосування.
Основою розвитку процесу стандартизації забезпечення технологічної безпеки ПЗ і БД є формування раціонального по складу, структурі і рівням вимог комплексу нормативно-технічної документації (НТД), що забезпечує нормативну основу створення і застосування інформаційних систем.
Таблиця 1. Міжнародні стандарти, спрямовані на забезпечення технологічної безпекиISO 09126:1991. ІТ. Оцінка програмного продукту. Характеристики якості і посібник з їхнього застосування.
DOD-STD-2168. Програма забезпечення якості оборонних програмних засобів.
ISO 09000-3:1991. Загальне керівництво якістю і стандарти по забезпеченню якості. Ч. 3: Провідні вказівки щодо застосування ISO 09001 при розробці, постачанні й обслуговуванні програмного забезпечення.
ISO 12207:1995. Процеси життєвого циклу програмних засобів.
DOD-STD 2167 A:1988. Розробка програмних засобів для систем військового призначення.
ISO 09646 - 1-6: 1991. ІТ. ВОС. Методологія й основи атестаційного тестування ВОС.
ANSI/IEEE 829 - 1983. Документація при тестуванні програм.
ANSI/IEEE 1008 - 1986. Тестування програмних модулів і компонент ПЗ.
ANSI/IEEE 1012 - 1986. Планування перевірки (оцінки) (verification) та підтвердження вірогідності (validation) програмних засобів
Розробка і супровід складних ПЗ і БД на базі CASE-технологій дозволяє усувати найбільше небезпечні системні й алгоритмічні помилки на ранніх стадіях проектування, а також використовувати неодноразово перевірені в інших проектах програмні й інформаційні компоненти високої якості.
Кроме того, по статистике не менее 75% всех компьютерных преступлений инициируется изнутри корпоративной сети, своими сотрудниками. А как уже было сказано выше, "классические" средства защиты, в том числе и межсетевые экраны, не позволяют защитить корпоративную сеть в случае наличия плохого умысла со стороны пользователя, имеющего в нее законный доступ.
Hо "хакеpы" и иже с ними пpедставляют, если можно так выpазиться, "внешнюю" угpозу компьютеpным системам. Hаpяду с "внешней" угpозой существует еще и "внутpенняя" угpоза, исходящая со стоpоны лиц, pаботающих в самой фиpме. Если говоpить более доступно, эта угpоза состоит в использовании служебной инфоpмации - или возможности ее получения - в личных целях.
Вопpосы, касающиеся безопасности компьютеpных систем, можно условно pазделить на следующие гpуппы: 1. Вопpосы обеспечения физической безопасности компонентов компьютеpной системы. Сюда относятся вопpосы защиты компьютеpных систем от пожаpа, затопления, дpугих стихийных бедствий, сбоев питания, кpажи, повpеждения, задымления и т.д. 2. Вопpосы обеспечения логической безопасности компонентов компьютеpных систем. Сюда относятся вопpосы эащиты компьютеpных систем от неавтоpизованного доступа, от умышленных и неумышленных ошибок в действиях людей и пpогpамм, котоpые могут пpивести к ущеpбу и т.д. 3. Вопpосы обеспечения социальной безопасности компонентов компьютеpных систем. Сюда относятся вопpосы pазpаботки законодательства, pегулиpующего пpименение компьютеpов и опpеделяющего поpядок pасследования и наказания наpушений безопасности компьютеpных систем; пpинципы и пpавила такой оpганизации обслуживания пользователей в компьютеpных системах, котоpая уменьшала бы pиск наpушения безопасности компьютеpных систем и т.д. 4. Вопpосы обеспечения этической безопасности компонентов компьютеpных систем.
Опять же, с точки зpения теоpии, безопасность любого компонента компьютеpной системы складывается из обеспечения тpех его хаpактеpистик: секpетности, целостности и доступности. Секpетность состоит в том, что компонент системы доступен только автоpизованным субьектам системы (пользователям, пpогpаммам и т.д.) Для остальных - неавтоpизованных - субьектов этот компонент как бы не существует (лучше сказать, он им "невидим"). Целостность компонента пpедполагает, что компонент может быть модифициpован только автоpизованным для этого субъектом (подpазумевается, что этот субьект осуществляет все модификации коppектно и не ставит целью осложнение собственной жизни путем искажения собственных данных или поломки собственного устpойства). Иными словами целостность - гаpантия пpавильности(pаботоспособности) компонента в любой момент вpемени. Отметим, что под модификацией подpазумеваются опеpации записи, обновления, изменения состояния, удаления и создания. Доступность пpедполагает действительную доступность компонента автоpизованному субъекту, т.е. автоpизованный субъект может в любой момент без особых пpоблем получить доступ к необходимому компоненту.

6. Засоби моделювання автоматизованих інформаційних системДо відповіді на це питання слід додати ще оглядовий матеріал по CASE–технологіям із 1 питання.
Важное место в моделировании информационных систем занимает методология и системы, использующие UML - унифицированный язык моделирования (Unified Modeling Language).
UML - язык для спецификации, визуализации, конструирования и документирования сложных информационно-насыщенных объектных систем. В настоящее время зарегистрирован как международный стандартISO/IEC 19501:2005 "Information technology - Open Distributed Processing - Unified Modeling Language (UML)".
UML-модель может включать в себя следующие аспекты;
Структурный аспект: Use-Case-диаграммы, идентифицирующие бизнес-процессы и бизнес-транзакции, их взаимосвязь, соподчиненность и взаимодействие; Package-диаграммы, описывающие структуру предметной области и иерархическую структуру организации.
Динамический аспект: Behavior-диаграммы (Activity, Statechart, Collaboration, Sequence), описывающие поведение (жизненный цикл) бизнес-процесcов в их взаимодействии во времени и в пространстве с привязкой к используемым ресурсам и получаемым результатам.
Статический аспект: Class-диаграммы, отражающие совокупность взаимосвязанных объектов, т.е. рассматривающие логическую структуру предметной области, ее внутренние концепции, иерархию объектов и статические связи между ними, структуры данных и объектов; Deployment-диаграммы, отражающие технологические ресурсы организации.
Словарь языка UML включает три вида строительных блоков:
сущности;
отношения;
диаграммы.
Сущности в UML - это абстракции, являющиеся основными элементами модели. Отношения связывают различные сущности; диаграммы группируют представляющие интерес совокупности сущностей.
В UML имеется четыре типа сущностей:
структурные;
поведенческие;
группирующие;
аннотационные.
Структурные сущности - это имена существительные в моделях на языке UML. Как правило, они представляют собой статические части модели, соответствующие концептуальным или физическим элементам системы. Существует семь разновидностей структурных сущностей: Класс, Интерфейс, Кооперация, Прецедент, Активный класс, Компонент, Узел.
Поведенческие сущности являются динамическими составляющими модели UML. Это глаголы языка: они описывают поведение модели во времени и пространстве. Существует всего два основных типа поведенческих сущностей: Взаимодействие и Автомат.
Группирующие сущности являются организующими частями модели UML. Это блоки, на которые можно разложить модель. Есть только одна первичная группирующая сущность, а именно - пакет.
Аннотационные сущности - пояснительные части модели UML. Это комментарии для дополнительного описания, разъяснения или замечания к любому элементу модели. Имеется только один базовый тип аннотационных элементов - примечание.
Все разновидности сущностей UML в диаграммах имеют свой способ графического изображения.
В языке UML определены четыре типа отношений:
зависимость;
ассоциация;
обобщение;
реализация.
Диаграмма в UML - это графическое представление набора элементов, изображаемое чаще всего в виде связанного графа с вершинами (сущностями) и ребрами (отношениями). Диаграммы рисуют для визуализации системы с разных точек зрения. Теоретически диаграммы могут содержать любые комбинации сущностей и отношений. На практике, однако, применяется сравнительно небольшое количество типовых комбинаций, соответствующих пяти наиболее употребительным видам, которые составляют архитектуру ИС. Таким образом, в UML выделяют девять типов диаграмм:
диаграммы классов (Class Diagrams);
диаграммы объектов (Objects Diagrams);
диаграммы прецедентов (Use Cases Diagrams);
диаграммы последовательностей (Sequence Diagrams);
диаграммы кооперации (Collaboration Diagrams);
диаграммы состояний (State Diagrams);
диаграммы действий (Activity Diagrams);
диаграммы компонентов (Component Diagrams);
диаграммы развертывания (Deployment Diagram).
Инструментальные средства, поддерживающие методологию UML - Rational Rose (Rational Software), Paradigm Plus (CA/Platinum), ARIS (IDS Sheer AG), Together Designer (Borland) и др.
Система Rational Rose позволяет строить восемь типов диаграмм UML: диаграммы прецедентов, диаграммы классов, диаграммы последовательностей, диаграммы кооперации, диаграммы состояний, диаграммы действий, компонентные диаграммы, диаграммы развертывания. Основным типом диаграмм, своеобразным ядром моделирования в UML являются диаграммы классов. Кроме UML, предусмотрено использование и других методов (Booch, OMT).
Система Paradigm Plus ориентирована на методологию OOCL (Object Oriented Change and Learning) и компонентную технологию проектирования и разработки. Она поддерживает диаграммы различных методов (UML, CLIPP, TeamFusion, OMT, Booch, OOCL, Martin/Odell, Shlaer/Mellor, Coad/Yourdon).
Система ARIS обеспечивает четыре различных "взгляда" на моделирование и анализ: Процессы, Функции (с Целями), Данные, Организация. Для каждого "взгляда" поддерживаются три уровня анализа (требования, спецификации, внедрение). Каждый из уровней анализа состоит из своего комплекта моделей различных типов, в том числе диаграмм UML, диаграмм SAP/R3 и др. Каждый объект моделей ARIS имеет множество атрибутов, которые позволяют контролировать процесс разработки моделей, определять условия для выполнения функционально-стоимостного анализа, имитационного моделирования, взаимодействия с workflow-системами и т.д.
Система Together Designer Community Edition - средство создания диаграмм UML 2.0. Позволяет строить диаграммы прецедентов (диаграммы сценариев взаимодействия пользователя с продуктом с точки зрения пользователя); диаграммы последовательностей, описывающие порядок передачи сообщений от одних объектов к другим; диаграммы кооперации, описывающие взаимодействие объектов друг с другом, диаграммы деятельности, описывающие потоки работ и изменение состояний объектов, диаграммы развертывания. При необходимости может создаваться логическая модель данных, содержащаядиаграммы "сущность-связь", на ее основе генерируется физическая модель данных для конкретной СУБД, выбранной для реализации проекта.
На этапе создания клиентского и серверного кода все современные средства UML-моделирования могут осуществлять генерацию кода на различных языках программирования.

7. Моделі життєвого циклу програмних засобів.Waterfall («водоспад», каскадна модель)
Модель не передбачає зворотні зв'язки (кожен етап повністю закінчений до переходу на наступний етап). При розв’язанні складних задач це неможливо. Модель застосовна коли: 1) вирішується дуже просте завдання, 2) розробляється чергова версія ПП
Прототипування
Спочатку розробляється не сам програмний продукт, а його прототип, що містить вирішення головних проблем, що стоять перед розробниками. Після успішного завершення розробки прототипу за тими самими принципами розробляється й справжній програмний продукт. Прототип дозволяє краще розуміти вимоги до розроблювальної програми. Використовуючи прототип, замовник також може точніше сформулювати свої вимоги. Розроблювач має можливість за допомогою прототипу пред'явити замовникові попередні результати своєї роботи.
Ітераційна модель
Задача розділяється на підзадачі й визначається черговість їх реалізації таким чином, щоб кожна наступна підзадача розширювала можливості ПП. Успіх суттєво залежить від того як вдало задачі розділені на підзадачі і як обрана черговість. Переваги: 1) можливість активної участі замовника в розробці, він має можливість уточнити свої вимоги в ході розробки; 2) можливість тестування наново розроблюваних частин разом з раніше розробленими, що зменшить витрати на комплексне налагодження; 3) під час розробки можна починати часткове впровадження.
Життєвий цикл «спіраль»
Кожний цикл у моделі починається з визначення мети цього циклу, аналізу різних шляхів її досягнення й можливих обмежень; оцінюється ступінь невизначеності й ризику. Вибирається стратегія проектування, що дозволяє їх зменшити. Далі розробляється перший прототип, виконується аналіз, уточнення вимог і т.д. Коло за колом, програмний продукт наближається до остаточного виду. Ця модель застосовується для проектів з великою невизначеністю й ризиком.

8. ER–модель.ER–модель - Інформаційна модель концептуального рівня (ІМКР) призначена для формального опису предметної області з урахуванням різноманітних точок зору на дані, які мають різні користувачі або задачі. Важливо зауважити, що ІМКР не залежить від конкретної СУБД, чи апаратної платформи, на якій реалізована база даних. Однією з найбільш часто вживаних модельних мов для опису ІМКР є ЕR-модель (Entity-Relationship model), яка була запропонована Ченом (P.Chen) у 1976 році, та її модифікації.
Розглянемо базові засоби ЕR-моделі, основу концепції якої складають такі поняття як тип об’єкту, тип зв’язку, атрибут та ключ.
Об’єктом називають сутність, яка для даної предметної області має незалежне від інших існування. Ця сутність може бути реальним (чи віртуальним) об’єктом, або поняттям. Всю сукупність однотипних об’єктів називають типом об’єкта, а окремий об’єкт інколи отримує назву примірника об’єкта. Тип об’єкта має ім’я та список іменованих властивостей, які називаються атрибутами. В класичній ER-моделі кожен примірник об’єкта по кожному атрибуту міг мати тільки одне значення, яке належало домену, або області значень відповідного атрибута. У деяких же модифікаціях ER-моделі розрізняють також атомарні чи складені атрибути та однозначні чи багатозначні. Відзначимо, що класична ER-модель орієнтується тільки на назви доменів (цим вони відрізняються один від одного), не приділяючи уваги способам їх реалізації.
Ключем об’єкта називається атрибут (або кілька атрибутів), значення якого однозначно специфікує примірник об’єкта за умови мінімальності. Умова мінімальності означає, що зі складу ключа не можна вилучити жодного атрибута без втрати властивості однозначної специфікації примірника об’єкта. Якщо ключ об’єкта складається з одного атрибута, то умова мінімальності виконується автоматично.
Зв’язок асоціює один чи кілька примірників одного типу об’єкта з одним чи кількома примірниками інших типів об’єктів. Зв’язок має ім’я (бажано з семантичним навантаженням) і характеризується арністю та типом відображення. Бінарними називаються зв’язки, які асоціюють примірники двох типів об’єктів, відповідно тернарними називаються зв’язки, що підтримують три типи об’єктів і т.д.
Згідно з типом відображення зв’язки поділяються на три групи. Зв’язки з типом відображення 1:1 (один до одного) одному примірнику одного типу об’єкта ставлять у відповідність точно один примірник іншого типу об’єкта. Прикладом такого зв’язку є зв’язок між об’єктами завідувач відділу та відділ. У графічному представленні такий зв’язок має вигляд, показаний на мал. 1.5.1:
Завідувач
відділу
Відділ
очолює

Зв’язки з типом відображення 1: N (один до багатьох) одному примірнику одного типу об’єкта ставлять у відповідність кілька (зокрема 0) примірників іншого типу об’єкта. Прикладом такого зв’язку є зв’язок між об’єктами співробітник та відділ. У графічному представленні такий зв’язок має вигляд, показаний на мал. 1.5.2:
Співробник
Відділ
працює
N
1

Зв’язки з типом відображення M : N (багато до багатьох) багатьом примірникам одного типу об’єкта ставлять у відповідність кілька примірників іншого типу об’єкта. Прикладом такого зв’язку є зв’язок між об’єктами співробітник та тема, у виконанні якої він бере участь. У графічному представленні такий зв’язок має вигляд, показаний на мал. 1.5.3:
Співробник
Тема
виконує
M
N

Відзначимо певні семантичні аспекти використання наведених зв’язків:
Зв’язок “очолює”(1:1) означає, що кожен відділ очолює один (і тільки один) завідувач і що кожен завідувач очолює тільки один відділ. Немає завідувачів без очолюваних відділів, і немає відділів без завідувачів.
Зв’язок “працює” (1:N) означає, що кілька співробітників можуть працювати у одному відділі, але кожен співробітник працює не більш ніж у одному відділі. Взагалі кажучи, можуть бути співробітники, які не відносяться до жодного відділу. У деяких модифікаціях моделі такі ситуації необхідно відзначати специфікацією об’єкту по певному зв’язку як обов’язковий (mandatory), або необов’язковий (optional), але по класиці береться останній, більш загальний варіант.
Зв’язок “виконує” означає, що кілька співробітників беруть участь у виконанні теми, і один і той же співробітник може брати участь у виконанні кількох тем. Можлива ситуація (як і у попередньому пункті), що деякий співробітник не виконує жодної теми, або є теми, що ніким не виконуються.
Відзначимо, що попередні визначення і приклади наводилися для випадку бінарних зв’язків; для зв’язків більших арностей – визначення аналогічні.
Зв’язки можуть мати власні атрибути, що не відносяться до жодного з об’єктів, що входять в зв’язок, але характеризують зв’язок загалом. Наприклад, зв’язок “виконує” може мати кілька атрибутів типу дата, задають термін, протягом якого певний співробітник бере участь у виконанні певної теми.
Для графічного зображення атрибутів часто використовують овальні контури, які з’єднуються з відповідними прямокутниками-об’єктами. На жаль такий спосіб може бути зручним тільки при відносно невеликій кількості атрибутів у об’єктах. На практиці ж частіше інформацію про атрибути подають окремо у вигляді одноіменної з об’єктом чи зв’язком таблиці. Наприклад, для об’єкта тема можна запропонувати наступну табличку.
ТЕМА
№ Назва атрибуту Домен Примітки
1. Номер теми Код1 2. Назва теми рядок літер 3. Дата початку дата 4. Дата завершення дата 5. Кошторис число 6. Категорія Код2 Ключовий атрибут відмічений у таблиці підкресленням номеру відповідного атрибуту; іноді відмітку про належность атрибуту до ключа роблять у вигляді зірочки у назві атрибуту.

9. Класифікація запитівЗа складністю запити поділяються на найпростіші, прості та складні. Зауважимо, що множина складних запитів може бути класифікована більш детально. Для класифікації найпростіших запитів введемо основну форму:
А ( O ) = V,
де А - ім'я атрибута або властивості, відносно якої формується запит, O - специфікація об'єкта запиту, V - значення, яке може набути атрибут об'єкта; замість знака "=" може бути використаний будь-який із знаків бінарних предикатів, що визначені для значень даної властивості об'єкта, наприклад: {<, >, =>, ...}.
Прості запити можна отримати з найпростіших (а також і простих) за допомогою логічних зв'язок ("або", "і", "ні"). Для побудови складних типів запитів необхідне використання кванторів існування та узагальнення.
Спочатку зробимо класифікацію найпростіших запитів. Для цього використаємо основну форму A(E) Q V, деQ = {}, A – атрибут, V –значення, Q – бінарний предикат, E – сам об’єкт, ключ.
Для прикладів використаємо таку модель: нехай є кілька кіосків, і в кожному місяці вони мають певний прибуток.
A – номер місяця.
E – номер кіоску.
V – значення прибутку кіоску за певний місяць (на перетині № кіоску і № місяця).
Прямий запит
A(E) = ? – відомий атрибут, відомий ключ. “Який прибуток був у кіоску №7 у березні?”. Результат – одне значення.
Інвертований запит
A(?) = V – відомий атрибут і відоме значення. “Знайти номери кіосків, у яких у березні був прибуток 8 тисяч”. Результат – множина.
?(E) = V. “У якому місяці кіоск №17 мав прибуток 8 тисяч?”. Результат – множина.
?(E) = ? (річний звіт). “Видати інформацію за рік по кіоску №17”.
A(?) = ?. “Видати інформацію по всім кіоскам за березень”.
?(?) = V. “Видати інформацію про кіоски і місяці з прибутком 8 тисяч”.
?(?) = ?. Повна інформація про все.
З найпростіших запитів формуються прості та складні запити. Прості запити – це найпростіші, що з’єднанні логічними зв’язками {}. Складні запити – це найпростіші, що з’єднанні зв’язками {}.
Більш формально:
Найпростіші запити часто включають селекцію і проекцію над єдиним відношенням, тобто специфікується деяка умова, якій повинні відповідати кортежі.
При простих запитах необхідно отримати природне з’єднання, з’єднання загального вигляду або декартів добуток декількох відношень, здійснити селекцію кортежів з побудованого відношення.
При складних запитах використовується деякий еквівалент квантору “для всіх”, який використовується для узагальнення простих запитів.

10. Реляційна модель Кодда. Реляційна алгебра12 правил Кодда. Ці правила є напів-офіційним визначенням поняття реляційна база даних:
правило 0: Основное правило (Foundation Rule): Реляционная СУБД должна быть способна полностью управлять базой данных, используя связи между данными.:
правило 1: Явное представление данных. Информация должна быть представлена в виде данных, хранящихся в ячейках. Данные, хранящиеся в ячейках, должны быть атомарны. Порядок строк в реляционной таблице не должен влиять на смысл данных.
правило 2: Гарантированный доступ к данным. Доступ к данным должен быть свободен от двусмысленности. К каждому элементу данных должен быть гарантирован доступ с помощью комбинации имени таблицы, первичного ключа строки и имени столбца.
правило 3: Полная обработка неизвестных значений: Неизвестные значения NULL, отличные от любого известного значения, должны поддерживаться для всех типов данных при выполнении любых операций.
правило 4: Доступ к словарю данных в терминах реляционной модели. Словарь данных должен сохраняться в форме реляционных таблиц, и СУБД должна поддерживать доступ к нему при помощи стандартных языковых средств.
правило 5: Полнота подмножества языка: Система управления реляционными базами данных должна поддерживать хотя бы один реляционный язык, который
(а) имеет линейный синтаксис,
(б) может использоваться как интерактивно, так и в прикладных программах,
(в) поддерживает операции определения данных, определения представлений, манипулирования данными (интерактивные и программные), ограничители целостности, управления доступом и операции управления транзакциями (begin, commit и rollback).
правило 6: Возможность модификации представлений: Каждое представление должно поддерживать операции манипулирования данными: операции выборки, вставки, модификации и удаления данных.
правило 7: Наличие высокоуровневых операций управления данными. Операции вставки, модификации и удаления данных должны поддерживаться не только по отношению к одной строке реляционной таблицы, но по отношению к любому множеству строк.
правило 8: Физическая независимость данных: Приложения не должны зависеть от способов хранения данных, аппаратного обеспечения компьютеров, на которых находится реляционная база данных.
правило 9: Логическая независимость данных: Представление данных в приложении не должно зависеть от структуры реляционных таблиц.
правило 10: Независимость контроля целостности: Вся информация, необходимая для поддержания целостности, должна находиться в словаре данных. Язык для работы с данными должен выполнять проверку входных данных и автоматически поддерживать целостность данных.
правило 11: Дистрибутивная независимость: База данных может быть распределённой, может находиться на нескольких компьютерах, и это не должно оказывать влияние на приложения..
правило 12: Согласование языковых уровней: Если используется низкоуровневый язык доступа к данным, он не должен игнорировать правила безопасности и правила целостности, которые поддерживаются языком более высокого уровня.
Теоретичні основи реляційної моделі баз даних були закладені Е.Коддом на початку 70-х років Введемо поняття реляції.
Нехай V – основний алфавіт, тобто деяка скінченна множина. - деякий виділений елемент; V.
Позначимо через D1, D2, … Dn V* ; де V* - множина всіх слів в алфавіті V.
Домени визначаються як Di = Di {};
Множину імен атрибутів позначимо . І введемо однозначне, але не обов’язково ін’єктивне відображення N: {D1, D2, … Dn}, яке іменує домени. Кожен домен може мати кілька імен, позначимо і = N-1(Dі) – множину всіх імен домена Dі. Очевидно, що ці множини мають такі властивості:і j = ; (i=1 n) і = ;
Атрибутом називається (А,Dі) – де А і ,
Нехай (Аі1,D1)(Аі2,D2)…(Аік,Dк) – відношення над декартовим добутком атрибутів. Введемо над множиною так визначених відношень розбиття на класи еквівалентності: до одного класу віднесемо ті відношення, які відрізняються тільки порядком компонент у декартовому добутку. Представник такого класу називається реляцією R((Аі1,D1),(Аі2,D2),…,(Аік,Dк)).
Схемою реляції R(А1,А2,…,Ак) називають відповідну реляційну таблицю без даних. ЧерезR будемо позначати множину імен атрибутів реляції R.
Реляційна алгебра – алгебра в строгому розумінні. Елементи основної множини – реляції.
Сигнатура складається з 8-ми операцій.
Теоретико-множинні операції ,,\ – частково визначені (визначені тільки для сумісних реляцій з однаковою структурою).
Реляції R1(A1, … , An) і R2(B1, … , Bk) називаються сумісними, якщо у них однакова кількість атрибутів; та кожному атрибуту першої реляції можна поставити у взаємно однозначну відповідність атрибут другої реляції.
Об’єднання.R1R2: в результуючу реляцію попадають всі кортежі першої і другої реляції без дублів.
Перетин.R1R2: в результуючу реляцію попадають кортежі, присутні і в першій, і в другій реляції.
Різниця.R1\R2: в результуючу реляцію попадають кортежі з R1, яких немає в R2.
Декартів добуток.R1R2 – визначається для будь-яких реляцій.
R1R2 = {(r1, … , rk, rk+1, … , rk+n) | (r1, … , rk) R1, (rk+1, … , rk+n) R2}.
Ця операція може різко збільшити об’єм результату.
Проекція.Реляція S(B1, … , Bn) узгоджена з R(A1, … , Ak), якщо f : S R, N(f(Bi)) = N(Ai), i = 1 n.
Відображення f однозначне, але, взагалі кажучи, не взаємно однозначне.
Проекцією реляції R на схему S відносно узгодження f будемо називати реляцію
T = R[S] таку, що: T = {(r[Ai1], r[Ai2], … , r[Ain])} та T = R[Ai1, Ai2, … , Ain,]
Операція  - з’єднання ( - join).
Введемо поняття  - порівнюваності для кортежів.
На двох реляціях R(A1, … , Ak) і S(B1, … , Bn) візьмемо відповідно два підкортежі:
r1 = (d1, d2, … , dm), r2 = (d1|, d2|, … , dm|);
Нехай  = {=, , <, , >, , …}; Два кортежі r1 і r2  - порівнювані:
r1r2  di  di|, i = 1,m; (m  k, m  n);
Нехай в реляції R виділений список атрибутів M1 = {A1, … , Am}, а в реляції S список атрибутів M2 = {B1, … , Bm}, причому відповідні атрибути співпадають по доменам, тобтоN(Ai) = N(Bi), i = 1,m;
Операція  - з’єднання реляції R з реляцією S по спискам M1 і M2 :R[M1  M2]S = {t  R  S | t[M1]  t[M2]}.
Операція  - обмеження.
Нехай задана реляція R(R), де R - множина імен атрибутів;
M1 = {A1, … , Am} R; і
M2 = {B1, … , Bm} R - списки атрибутів з властивістюN(Ai) = N(Bi); i = 1,m;
 - обмеження реляції R по спискам M1 і M2 :R[M1  M2] = {r | (r R) &(r[M1]  r[M2])}.
Операція ділення.
Нехай задана реляція R(A1, … , Ak) і два взаємнодоповнюючі списки атрибутів
M1 = {A1, … , An}; M2 = {An+1, … , Ak}
Нехай є С1 = D1…Dn; С2 = Dn+1…Dk; де Di = N(Ai), i = 1,k;
Якщо візьмемо деякий елемент x  С1, то образом x по реляції R буде називатись множина підкортежів :
imRx = {y  С2 | (x, y)  R}
Розглянемо реляції R(R), S(S) і списки атрибутів {A1, … , An}R ; {B1, … , Bn}S;
Необхідно, щоб реляції R[A1, … , An] і S[B1, … , Bn] були сумісними, тоді операція R[A B]S називається діленням R на S по спискам {A1, … , An} і {B1, … , Bn}
Результатом є множина підкортежів по атрибутам, що доповнюють список {A1, … , An}.
R[A B]S = {r[An+1, … , Ak] | (r R) & (S[B1, … , Bn]  imR(r[An+1, … , Ak]))}
Приклад використання операції ділення.
Нехай задана таблиця R з двома атрибутами (мова програмування і прізвище програміста, який цією мовою володіє)
Знайти прізвища програмістів, які знають мови А і Ф одночасно. Для виконання такого запиту утворимо допоміжну реляцію S з одним атрибутом і двома кортежами з відповідними значеннями кодів мов програмування {А,Ф}.
R[мова мв]S
R Мова Прізв S мв
  А І   А
А П   Ф
ПЛ С Ф Ф Ф І Ф С ПЛ П П Ф П І Образом І буде {А, Ф, П}, що є надмножиною відносно{А, Ф}, тому І проходить у результуючу таблицю; а П, С, Ф – не проходять у результуючу таблицю, бо їх образи не накривають {А, Ф}. Це означає, що програміст І знає мови {А,Ф} (можливо ще щось), а інші не знають цих мов одночасно.

11. Функціонально повна залежність. 2-нормальна форма (2НФ).Функціональна залежність:RD1D2, d1D1, imRd1 –1 елемент.
Якщо реляція бінарна, то функціональна залежність має таке визначення: довільне значення першого атрибуту (його образ) складається з одного елементу.
Узагальнене поняття ФЗ на випадок n-арної реляції:
Нехай RD1...Dn, n2, R(AR), M1, M2 AR, тоді r1R[M1], r2R[M2] r1Rr2rR1, r1 = r[M1] r2=r[M2].
R.M1R.M2 – означає, що атрибути списку М1 функціонально визначають список М2
R.M1R.M2 - взаємооднозначність.
Тепер реляції можна розглядати у вигляді (AR , f R), де AR - булеан всіх імен атрибутів, f R – структура функціональних залежностей.
Означення: Список атрибутів М2 функціонально залежить від М1, якщо:
R.M1R.M2
AM1 BM2: R.AR.B
Означення: Квазіключем або кандидатом в ключ називається така підмножина імен атрибутів КАR, що задовольняє двом умовам:
МАR, R.KR.M
K’К МАR: не виконується R.K’R.M
Означення: Атрибут називається первинним, якщо він входить до складу хоча б одного квазіключа.
Означення: Атрибут називається вторинним, якщо він не входить до складу жодного квазіключа.
Перша нормальна форма. Кажуть, що реляція знаходиться в першій нормальній формі, якщо всі її атрибути атомарні, неподільні, неструктуровані.
Друга нормальна форма. 2НФ=1НФ+функціонально повна залежність будь-якого непервинного атрибуту від кожного квазіключа.
Теорема Хиса: якщо в реляції R маємо R.M1R.M2, тоді R=R[M1M2] R[AR\(M1\M2)].
Умови, за яких реляція обов’язково знаходиться в 2НФ:
всі атрибути первинні (нема функціональної залежності);
кожен квазіключ має тільки один атрибут(тобто ключ не можна розщепити).
Друга нормальна форма посилена. Все те, що і для 2НФ, лише зняти слово “непервинний”.

12. Мінімальна структура функціональних залежностейФункціональна залежність:RD1D2, d1D1, imRd1 –1 елемент.
Якщо реляція бінарна, то функціональна залежність має таке визначення: довільне значення першого атрибуту (його образ) складається з одного елементу.
Узагальнене поняття ФЗ на випадок n-арної реляції:
Нехай RD1...Dn, n2, R(AR), M1, M2 AR, тоді r1R[M1], r2R[M2] r1Rr2rR1, r1 = r[M1] r2=r[M2].
R.M1R.M2 – означає, що атрибути списку М1 функціонально визначають список М2
R.M1R.M2 - взаємооднозначність.
Тепер реляції можна розглядати у вигляді (AR , f R), де AR - булеан всіх імен атрибутів, f R – структура функціональних залежностей.
Структура функціональних залежностей F називається мінімальною, якщо:
Кожна права частина залежності в структурі F має один атрибут.
Антинадлишковість: ніяку функціональну залежність не можна викинути і в результаті отримати еквівалентну. (xA) F, F\{xA} не еквівалентна F.
Антинадлишковість лівої частини: ні для якої функціональної залежності не виконується (xA) F & rX (X – множина атрибутів), F\{xA} {rA} еквівалентна F.
Теорема: для кожної структури функціональних залежностей F еквівалентна їй мінімальна структура.
- проективність
- транзитивність
- монотонність

13. Аксіоми АрмстронгаФункціональна залежність:RD1D2, d1D1, imRd1 –1 елемент.
Якщо реляція бінарна, то функціональна залежність має таке визначення: довільне значення першого атрибуту (його образ) складається з одного елементу.
Узагальнене поняття ФЗ на випадок n-арної реляції:
Нехай RD1...Dn, n2, R(AR), M1, M2 AR, тоді r1R[M1], r2R[M2] r1Rr2rR1, r1 = r[M1] r2=r[M2].
R.M1R.M2 – означає, що атрибути списку М1 функціонально визначають список М2
R.M1R.M2 - взаємооднозначність.
Тепер реляції можна розглядати у вигляді (AR , f R), де AR - булеан всіх імен атрибутів, f R – структура функціональних залежностей.
Нехай R – система властивостей функціональних залежностей реляції.
Перша система аксіом (випливає з визначення ФЗ).
R1.”Проективність”. М1, М2 – множини атрибутів деяких реляцій.М1 М2=> М1М2
R2. Транзитивність.М1М2 & М2М3 => М1М3
R3. Монотонність.М1М2 => (М1М3)(М2М3)
Будемо казати, що пара множин М1, М2 більша або рівна парі множин М3, М4, якщо
(М1, М2) (М3, М4) <=> M1M3 & M2M4 MR.
Аксіоми Армстронга.
Р1. Рефлексивність. М1М2
Р2. Транзитивність (Р2 R3). М1М2 & М2М3 => М1М3
Р3. М1М2 & (М1,М2) (М3,М4) => М3М4
Р4. Щось на зразок монотонності (псевдомонотонність). М1М2 & М3М4 => М1М2М2М4
Теорема: Р еквівалентна R.

14. Третя нормальна форма та третя нормальна форма Бойса-КоддаРеляційне числення Кодда є одним із найважливіших наріжних каменів теорії реляційних моделей баз даних.
Алфавіт.V1 = {a; r; P; }; V2 = {; ; ; ; }; V3 = {=; ; ; ; ; }; V4 = {[; ]; (; ); ,; :}; V = V1 V2 V3 V4;
Індекси – це слова виду ... (m - штук), m = 0,1,2,...
Константи – слова виду а... (m - штук), m = 0,1,2,...; позначення - am; a=a0;
Змінні – слова виду r... (m - штук), m = 0,1,2,...; позначення - rm;
Предикати (унарні) – слова виду P... (m - штук), m = 0,1,2,...; позначення - Pm;
Зрізи – слова виду r...[...] (i та m - штук), і,m = 0,1,2,...; позначення – ri[m];
Терми значень – слова виду Pi rj;
Терми з’єднань – слова виду , або , де , -- зрізи, - константа, - бінарний предикат (порівняння).
Всі терми значень і терми з’єднань є ППФ (Правильно побудовані формули). Всі їх змінні – вільні. Якщо F – ППФ, то F – ППФ. Якщо F1 і F2 – ППФ і їх спільні змінні вільні у кожній з формул, то F1 F2, F1 F2 – ППФ. Змінні вільні у F1 F2, F1 F2, якщо вони вільні принаймні у одній формулі.Якщо F – ППФ і r – вільна у ній змінна, то r(F), r(F) – ППФ; r – зв’язана змінна. Інших ППФ немає.
Реляція знаходиться в 3 НФП, якщо вона в 2 НФП і не має транзитивної залежності атрибутів відносно кожного квазіключа.
Приклад:
А5 А4 А3
А1 – шифр міністерства,
А2 – шифр головного управління,
А3 – шифр області,
А6 А2 А4 – шифр району,
А6 – шифр підприємства,
А7 – шифр галузі.
А1
{ А5А6А1}
{ А5А2А1}А5 є ключем ієрархічної структури.
{ А5А4А3}
Є транзитивна залежність А5А3.
Розглянемо варіант { А5А6А2}, який є транзитивно залежним.
А5А2
А5А6
А в { А5,А6,А2} нема транзитивної залежності, оскільки А6А2. Такі структури в логічному проектуванні називаються трикутником (кілька взаємозвязаних вершин).
В даному випадку існують 2 транзитивної залежності ця реляція не знаходиться в 3 НФ.
Нормальна форма Бойса — Кодда (або НФБК, або БКННФ, або 3.5НФ) — нормальна форма використовна в нормалізації баз даних. Це трошки сильніша версія третьої нормальної форми (3НФ). Таблиця знаходиться в НФБК тоді і тільки тоді, коли для кожної її нетривіальної функціональної залежності X → Y, X це суперключ — тобто, X або потенційний ключ, або його надмножина.

15. Багатозначні залежності. 4-нормальна формаРозглянемо схему відношення PR (Предмети), наведену нижче:
PR (Предмети)
PN
PNAME
PZAN

Відношення Предмети містить номери (коди) предметів, для кожного предмету – перелік курсів, що включені в цей предмет, і перелік завдань, що передбачені курсом. При цьому по курсу їх може бути декілька, а різні курси можуть включати однакові завдання.
Кожний кортеж відношення пов’язує деякий предмет з курсом і завданням, які мають бути виконані в рамках даного курсу. З наведених вище умов, єдиним можливим ключем відношення є складений атрибут {PN, PNAME, PZAN} і немає ніяких інших детермінантів. Звідси, відношення предмети знаходиться у НФБК, але при цьому воно володіє недоліками, наприклад, деяке завдання додається до курсу, необхідно вставити у відношення Предмети стільки кортежів, скільки завдань у ньому передбачено.
У відношенні R {A,B,C} існує багатозначна залежність між А і В (АB) в тому випадку, якщо множина значень В, що відповідає парі значень (А і С) залежить лише від А і не залежить від С.
У відношенні Предмети існують дві багатозначні залежності: PPNAME i PN PZAN
Таким чином, відношення знаходиться в 4НФ в тому випадку, якщо у випадку існування багатозначної залежності AB всі решта атрибутів функціонально залежать від А.
В нашому прикладі можна провести декомпозицію відношення Предмети на два відношення Предмети-Курси та Предмети-Завдання. Обидва отримані відношення знаходяться в 4НФ і вільні від описаних проблем.
Формально. Нехай Х,У αR: imR(X,Y)={y | zR & z[X]=x & z[Y]=y}.
Нехай . (αR – множина імен атрибутів )
Означення. (Х багатозначно залежить від Х – списка атрибутів), якщо (x,z) XZ, imR(XZ, Y) = imR(X, Y).
Функціональна залежність багатозначна залежність.
Багатозначна залежність тривіальна, якщо вона дублюється функціональною.
Реляція знаходиться в 4 НФ, якщо вона знаходиться в 3 НФ і не має нетривіальної багатозначної залежності, або 4 НФ: R AB A αR +3 НФ (А - ключ)
(про реляційну алгебру Кодда див. 1.14)

16. Стратегії розподілу даних в розподілених базах даних1. Централізація.
На одному вузлі сконцентровані всі дані, а всі звертаються до нього.
Особливість полягає в тому, що об’єм даних мережі обмежуються даними серверу.
Надійність мережі – здатність зберігати дані при виході з ладу одного з вузлів. В даному випадку надійність залежить від серверу. При інтенсивному зверненні до серверу мережа перевантажується.
Простота програмного забезпечення => надійність з точки зору збоїв програмного забезпечення.
2. Розчленування.
Стратегія розчленування – всі дані розбиваються на частини і розподіляються по вузлам мережі. Об’єм даних, що функціонують в мережі обмежений сумарною пам’яттю всіх вузлів мережі.
Надійність залежить від характеру роботи мережі (розподіленої РБД), якщо більшість запитів стосуються даних свого вузла, то вихід з ладу одного чи декількох вузлів мережі знижує працездатність, але в незначній мірі => навантаження на мережу відносно невелике.
Внесення змін: якщо зміни вносяться локально, то проблем особливих нема, якщо глобально, у всю РБД, то виникає проблема одночасного оновлення всіх вузлів мережі.
Найбільша проблема – пошук даних. Спочатку потрібно з’ясувати де знаходяться довідники даних, потім визначити де саме знаходяться дані. Для цього потрібно розробити ефективну стратегію довідників даних.
3. Дублювання.
Копії всіх даних знаходяться на кожному вузлі мережі. Об’єм даних в мережі обмежується найменшим об’ємом пам’яті вузла, надійність мережі найвища. Інтенсивність роботи в мережі при запиті читання низька, але дуже висока при оновленні та синхронізації.
В цьому випадку також зростає надійність програмного забезпечення (на всіх вузлах одне і теж).
4. Змішана.
Різноманітні варіанти об’єднання трьох вище вказаних стратегій.

2. Системне програмування1. Поняття мовного процесора. Типи мовних процесорів. Основні фази мовного процесора.Мовний процессор – це програмний комплекс, що реалізує мову програмування. При розробці мовних процесорів беруться до уваги три аспекти: прагматичний, семантичний, синт`аксичний.
Прагматичний аспект в мовному процесорі визначає область адекватного використання системи: транслятори та інтерпретатори. Транслятор - на вхід якого подається текст (програма) на вхідний мові, а на виході подається текст на вихідній мові. Інтерпретатор - на вхід якого подається програма, на виході отримуємо результат роботи програми по вхідним даним.
В залежності від того, яка вхідна мова використовується при трансляції, існує дві спеціалізації трансляторів: компілятори і асемблери. Якщо вихідною мовою є об’єктний код, то такі транслятори - компілятори. Якщо вхідна мова транслятора - асемблер, а вихідна - машинний код, то такі транслятори - асемблери.
Архітектура ЕОМ в певній мірі впливає на структуру мовного процесора. В залежності від структури ЕОМ мовні процесори поділяють на: 1) однопрохідні мовні процесори (він отримує результат за один перегляд вхідної програми, як приклад Pascal); 2) багатопрохідні мовні процесори (він отримує результат за багато переглядів вхідної програми, як приклад Assembler). Кількість переглядів мовним процесором вхідної програми залежить від структури мови програмування.
результат
Вхідна програма
Синтаксичний аналізатор
Семантичний аналізатор
Оптимізація семантичного терму
Генератор вихідного тексту (об’єктний код)
Лексичний аналізатор
Мовні таблиці
транслятора
Структура мовного процесора типу ТРАНСЛЯТОР
Структура мовного процесора типу ІНТЕРПРЕТАТОР
результат
Вхідна програма
Синтаксичний аналізатор
Семантичний аналізатор
Інтерпретація семантичного терму
Вхідні дані
Лексичний аналізатор
Мовні таблиці
транслятора


2. Скінченні автомати. Методика побудови лексичного аналізатора на основі скінченного автомата.Недетмінований ск. автомат – це п‘ятірка M=(Q, , , q0, F), де Q – ск. множ. станів, - ск. множ. дозволених вх. симв., : Q x -> B(Q) - функція переходів, q0Q– початковий стан, F Q – множ. заключних станів.
Роботою скін. авт. є деяка послід. кроків, або тактів. Такт задається поточним станом автомату та вхідним символом, який він бачить на зараз на вхідній ленті. Сам такт складається із зміни стану та здвигу вхідної головки на одну ячейку праворуч.
Пара (q, w) Qx* - є конфігурація автомату. (q0, w) – початкова конфігурація, (q, e), qF – заключна конфігурація (або допустима). Такт автомату є бінарне відн. M заданих на конфігураціях: якщо (q, a) q’, то (q, aw) M (q’, w) для w* .
Мова, яку задає (розпізнає) автомат M: L(M) = {w | w* та (q0, w) * (q,e) для деякого qF}
Засоби завдання ск. автоматів:
табличний – задаємо таблицею фю ,
графічний – малюємо стані авт.та напрямлені стрілки між станами з поміткою символом з по якому здійснюється перехід,
матричний – будуємо вектори 1:n [вхідні компоненти 1:k + вихідні компоненти k:n], цим задаємо зв‘язок вхідних даних з вихідними.
Методика побудови лексичного аналізатора: Нехай є ск. автомат M=(Q, , , q0, F, Err), де Err Q – мн. помилкових станів. При своїй роботі авт. (зпочатку знах. в поч. стані q0) читає з вхідної стрічки символи поки не потрапить в деякий стан q (порожні символи пропускаються, тобто існує перехід по порожньму символу зі стану q0 в стан q0): якщо q F, то розпізнана деяка лексема (яка саме – залежить від стану, який відповідає лексемі), передаємо її синтаксичному аналізатору та переводимо автомат в стан q0; якщо q Err, то розпізнувана лексема є помилковою -> кінець роботи. Спрощена (!) схема:


3. Регулярні множини та регулярні вирази, їх звязок із скінченними автоматами.Основні тотожності в алгебрі регулярних виразів.Регулярна множина в алф. (ск. алфавіт) задається рекурсивно:
- рег. множ.;
{e} - рег. мн. в алф. ;
{a} - рег. мн. a ;
якщо P та Q - рег. мн., то P Q, PQ, P* - рег. мн.
Регулярний вираз в алф. та відповідні рег. множ, які вони позначають, задається рекурсивно:
- рег. вираз, що позначає рег. множ. ;
e - рег. вираз, що позначає рег. множ. {e};
a - рег. вираз a , що позначає рег. множ. {a};
якщо p та q - рег. вираз, що позначає відп. рег. мн. P та Q , то (p+q) - рег. вираз, що позн. P Q, (pq) - рег. вираз, що позн. PQ, (p)* - рег. вираз, що позн. P*.
Алгебра регулярних виразів: ER=<B(*),{,,*}>. Нехай ,, - рег. вирази, тоді
+=+,
+(+)=(+)+,
(+)=+,
ae=ea=a,
a*=a+a*,
a+a=a,
*=e,
()=(),
(+)=+,
a=a=,
(a*)*=a*, 12) a+=a
Теорема. Деяка мова задається скінченим автоматом коли мова є регулярною множиною.

4. Вивід у граматиці. Дерево виводу. Лівостороння та правостороння стратегії виводу.Нехай G-граматика. Будемо казати, що послідовність v безпосередньо породжує послідовність w: v w, якщо v=xUy, w=xuy, та існує правило U ::= u
Будемо казати, що послідовність v породжує w: v+ w, якщо існує посліовність v=u0 u1 … un =w
Лівостороння стратегія виводу w в G - це така стратегія безпосереднього виводу де на кожному кроці береться перший з ліва направо нетермінал. Правостороння протилежна лівосторонній.
Синтаксичні дерева.


S
Синтаксичне дерево - дерево, корінь якого є аксіома, проміжні вершини позначені елементами з N, на кроні знаходяться елементи з множини E.
Контекстно-вільні граматики: Породжуюча граматика (за Хомським): G=<N,E,P,S>, де N - допоміжний алфавіт (алфавіт нетерміналів); E - основний алфавіт (алфавіт терміналів); N та E - скінченні множини; P - скінчена множина правил типу , де: , ( множина всіх слів у термінальному алфавіті), - аксіома (виділений нетермінал).
Впорядковане дерево D називається деревом виводу (або деревом розбору) в КВ-граматиці G(S)=(N,E,P,S), яцщо виконуютсья наступні умови:
корінь дерева D позначений S;
кожен лист позначений або , або e;
кожна внутрішня вершина помічена нетерміналом;
якщо N - нетермінал, яким позначена внутрішня вершина і X1,...,Xn - мітки її прямих нащадків в у вказаному порядку, то N->X1...Xk - правило з множини P.

5. LL(k)-граматики. Перевірка LL(1)-умови для довільної КВ- граматикиГраматика називається -граматикою, якщо існують два виводи:
,
,
та:
, то , де





S


{множина термінальних слів, довжина яких не більше , які можна вивести з }
, якщо
LL(1)-умова для довільної КС-граматиці:
,
,
Якщо з виводиться не -слово, то вже не впливає на результат.
Умови:
, , ,
в граматиці не може бути , ,
Якщо існує таке , то при
,
Функція:
,

,
в інших випадках не визначено.

6. Побудова LL(1)-таблиці для управління LL(1)-синтаксичним аналізаторомТаблиця , де ,

Алгоритм роботи -синтаксичного аналізатора (продемонстровано на магазинному автоматі):
0: В стек занесли аксіому, прочитавши поточну лексему b;
1: Якщо на вершині стеку нетермінал , то визначає номер правила, яке заміщає на вершині магазина;
2: Якщо на вершині магазину - поточна лексема, то з вершини стеку зняти , прочитавши нову лексему;
3: Якщо стек порожній, то прочитати всю програму, то "допустити" інакше - "синтаксична помилка";
4: В інших випадках - "синтаксична помилка";
Побудований синтаксичний аналізатор аналізує програму за час пропорційний O(n), використовує лише одну поточну лексему.

7. Атрибутний метод визначення семантики програм. Синтезовані та успадковані атрибути.Порядок та правила обчислення атрибутів.Синтаксично кероване визначення — узагальнення контекстно-вільної граматики, в якій кожен граматичний символ має зв`язану множину атрибутів, розділену на дві підмножини, – синтезовані і успадковані атрибути цього граматичного символа.
Атрибут може бути чим завгодно, – строкою, числом, типом, адресою пам`яті і т.д. Значення атрибуту у вузлі дерева розбору визначається семантичними правилами, зв`язаними з використованою в даному вузлі продукцією. Значення синтезованого атрибута у вузлі обчислюється по значеннях атрибутів в нащадках даного вузла; значення успадкованих атрибутів визначається значеннями атрибутів сусдніх ( тобто вузлів, що є нащадками по відношенню до батьківського вузла даного ) і батьківського вузлів.
Атрибутний метод визначення семантики програм був запропонований Кнутом.
Ідея: з довільною граматикою пов`язана певна множина атрибутів. Значення одного атрибута обчислюється через значення інших атрибутів. Є правила, в котрих для певних атрибутів вводяться константи або певні значення з таблиць.
Для розрахунку атрибутів фіксується процедура ( на синт. дереві ), наприклад лівосторонній обхід дерева. Якщо атрибутна схема вимагає декілька переглядів дерева, то неефективно.
Проблема: Коректність атрибутної схеми — чи можна для довільного правила побудувати синтаксичне дерево обчислення довільних атрибутів?
Відповідь: Для довільного КВ-граматики не існує алгоритму перевірки коректності атрибутної схеми. Як вихід із положення, Кнут запропонував конкретизацію атрибутів, а саме поділення атрибутів на
успадковані ( int i,j,k – типи “j” та “k” такі ж, як і у “i” ),
синтезовані ( напр. a+b, синтезовані з “а” та “b” за допомогою “+” ).
Обмеження до конкретизації: Доведення атрибуту для даного правила може розраховуватись лише через атрибут, що пов`язаний з цим правилом, а також через атрибути нащадків для правої частини правила.
Висновок :
Атрибутну схему з конкретизацією легко перевірити на коректність
Атрибутну схему можна розрахувати за 1 перегляд.

8. Машинно-орієнтовані мови програмування. Асемблери.Структура асемблера, перегляди тексту програми та відповідні бази даних.Асемблер: машинно-орієнтована мова. Основною одиницею в асемблер-програмі є машинна команда (директива асемблера). На її основі будується машинний код.
Директиви асемблера – це команди, що управляють процесом компіляції. На основі директиви асемблера об’єктний код не будується. Кожна машинна команда чи директива записується в один рядок (або в декілька шляхом продовження).
Між кодами операцій і операціями повинен бути щонайменше один " ". Операнди записуються через кому, без проміжків.
ОП1,ОП2 коментар(коментар може починатись або з "*" або з ";")
Помітка – іменує як команди, так дані (символьне ім’я). В асемблері значення символьного імені є адреса. Repeat – символьне ім’я.
0
Repeat
дані
MAX
Сегмент команд
Сегмент даних
Стек
Сегмент
Кожне символьне ім’я кодується парою: (база, зміщення), де база - ім’я сегменту програми, в якому це символьне ім’я визначено.
Оскільки ми не можемо знати наперед абсолютну адресу пам’яті ЕОМ, куди завантажується програма, то асемблер виконує початкове присвоєння абсолютної адреси кожного сегменту значення . Реальна адреса формується під час виконання програми шляхом сумування значення регістру та зміщення, а початкові значення регістрів сегментів приписується операційною системою під час завантаження програми.
Генерація машиного коду
Вхідна програма
Синтаксичний аналізатор
Семантичний аналізатор
Лексичний аналізатор
Мовні таблиці
ассемблеру
Асемблер під час обробки програми з кожним сегментом пов’язує лічильник сегменту. Обчислюється як попереднє значення плюс довжина команди. Початкове значення кожного лічильника або встановлюється директивою асемблера.

Оскільки відсутня дисципліна вживання символьних імен, компілятор асемблеру щонайменше двопрохідний:
Попередній перегляд тексту: визначення значень символьних імен, їх адреси (сегмент + зміщення).
Другий перегляд тексту: Дає можливість перевірити код команди, та вказує адреси операндів.
Але в асемблері існують такі імена та значення, які не можна визначити під час компіляції (абсолютна адреса, ім’я зовнішньої функції). Тому в об’єктному коді резервується місце для операнда, а в результуючий файл, в таблиці модуля вказується зміщення в об’єктному коді, котре треба модифікувати.

3. Архітектура ЕОМ, комп’ютерні та інформаційні мережі1. Розподіл оперативної пам’яті, поняття сегменту та зсуву. Сторінкова організація пам’яті.Логічна структура пам’яті PC зумовлена особливостями системи адресації процесорів 8086:
адресний простір 1 Мбайт (20 біт шини адреси),
реальна (лінійна) адреса обчислюється за формулою Addr=Seg*16+Offset, де Seg та Offset – вміст сегментного та адресного 16-бітних регістрів. Addr=00000h–FFFFFh.
Розподіл основної пам’яті PC:
00000h-9FFFFh – Conventional (Base) Memory – базова пам’ять, доступна DOS та програмам реального режиму; з них:
00000h-003FFh – Interrupt Vectors – вектори переривань (256 подвійних слів),
00400h-004FFh – BIOS Data Area – область змінних BIOS,
00500h-00xxxh – DOS Area – область DOS,
00xxxh-9FFFFh – User RAM – пам’ять, що надається користувачу;
A0000h-FFFFFh – Upper Memory Area – верхня пам’ять, зарезервована для системних потреб;
A0000h-BFFFFh – Video RAM, 128 Кбайт – відеопам’ять,
C0000h-DFFFFh – Adapter ROM/RAM – резерв для адаптерів, що використовують власні модулі ROM BIOS,
E0000h-EFFFFh – вільна пам’ять, іноді зайнята під System BIOS,
F0000h-FFFFFh – System BIOS – ROM на системній платі,
FD000h-FDFFFh – Extended Static Configuration Data – область енергонезалежної пам’яті що використовується для конфігурування пристроїв Plug and Play;
вище 100000h – Extended Memory – додаткова (розширена, відображувана) пам’ять, безпосередньо доступна лише в захищеному режимі 286+ процесорів.
Для АТ з 24-бітною шиною адреси FDFFFFh – верхня межа Extended Memory; FE0000h-FFFFFFh – ROM BIOS Area (звернення еквівалентно зверненню до ROM BIOS 0E0000h-0FFFFFh). Для 386+ процесорів і 32-розрядної шини адреси теоретично верхня межа – 4 Гбайт, образ BIOS додатково проектується в адреси FFFE0000h-FFFFFFFFh.
В захищеному режимі пам’ять адресується парами (селектор, зсув). Перетворення логічних (віртуальних) адрес у фізичні здійснюється за допомогою таблиць дескрипторів - локальної чи глобальної - LDT або GDT.

2. Канали та порти вводу-виводуКанал вводу-виводу – спеціалізований процесор, в якому реалізовані засоби пересилки даних і схеми управління операціями вводу-виводу (ВВ). Як правило, забезпечує форматування і буферизацію та має всі необхідні засоби управління для забезпечення синхронної роботи з пристроєм ВВ. Якщо інтерфейс має декілька паралельних каналів ВВ, то кожен з них звичайно використовується для пересилання тільки одного виду інформації, наприклад, даних. До одного каналу можуть бути під’єднані декілька пристроїв ВВ, при цьому для ВВ потоків даних на той чи інший пристрій використовуються спеціальні схеми управління, що передбачені у складі каналу. Якщо пристрої ВВ мають відносно низьку швидкодію, для з’єднання їх з процесором використовується мультиплексний канал. Операції ВВ по такому каналу на окремі пристрої мультиплексовані, тобто чергуються знак за знаком так, що одночасно можуть працювати декілька пристроїв. Якщо необхідно підключити декілька пристроїв з високою швидкодією, то використовується селекторний канал. В цьому випадку за одну операцію вводиться або виводиться цілий запис (або декілька), а потім виконується перемикання на наступний пристрій. Поки селекторний канал обслуговує один пристрій, інші пристрої не можуть пересилати інформацію. Однак в цей час вони можуть працювати. В якості каналів ВВ часто використовуються процесори з “зашитою” програмою. В міру ускладнення каналів, для їх реалізації використовують ЕОМ (процесори ВВ).
Порти ВВ (I/O port) – апаратура спряження, що вміщує ланцюги управління та дозволяє підключати пристрої ВВ до внутрішньої шини мікропроцесора. Звичайно один і той самий порт може переключатися на ввід або вивід, що, як правило, здійснюється інтерфейсним адаптером периферійних пристроїв. Цей адаптер з одного боку має роз’єми, сумісні з портом ВВ, а з іншого – один чи більше інтерфейсів, що підходять до різноманітних периферійних пристроїв. Порт також дозволяє застосовувати з’єднуючі кабелі збільшеної довжини. У вільному вживанні означає внутрішнє під’єднання до мережі зв’язку або через електричну схему, або через інтерфейс термінала.
Під портами в PC розуміють набір каналів для обміну інформацією з системними та зовнішніми пристроями (в ХТ їх 1024, в АТ – 65536), їх також часто називають регістрами – на низькому рівні; або стандартні порти паралельного чи послідовного інтерфейсів (LPT - Line PrinTer, COM - COMmunication port, інфрачервоний порт, …) – на більш високому рівні.

3. Поняття про переривання та їх класифікаціяВ обчислювальній техніці під перериванням розуміють подію, при якій міняється нормальна послідовність виконання команд, що визначена програмою. Переривання, є механізмом, що дозволяє координувати паралельне функціонування окремих пристроїв комп’ютерної системи та реагувати на особливі стани, що виникають при роботі процесора. Тобто, переривання, це примусова передача керування від програми, що виконується, до ОС, а через неї до відповідної програми обробки переривань. Ця передача відбувається при виникненні певної події.
Механізм переривань реалізується апаратно програмним забезпеченням. Структура систем переривань може бути різноманітною (в залежності від архітектури апаратного забезпечення), але всі вони реалізують одну ідею – переривається звичайний порядок виконання команд процесором.

Перехід від перерваної програми до обробника переривань повинен виконуватися якомога швидше. Одним з методів, що реалізуються цей механізм переходу, є організація таблиць, що містять всі допустимі в системі переривання та адреси їх обробників.
Для коректного повернення з переривання до перерваної програми перед передачею керування обробнику система запам’ятовує вміст регістрів процесора або у пам’яті з прямим доступом, або у системному стеку.
Таким чином, якщо відбулося переривання:
Керування передається ОС;
 ОС запам’ятовує стан перерваного процесу, як правило, ця інформація запам’ятовується в його блоці керування процесом (PCB);
ОС аналізує тип переривання та передає керування відповідному обробнику.
Переривання, що виникають при роботі обчислювальної системи, можна поділити на такі основні групи:
Зовнішні (або асинхронні). Викликаються асинхронними подіями, які відбуваються поза процесом, що виконується і відповідно переривається:
переривання від таймера;
переривання від зовнішніх пристроїв;
переривання при збоях у живлення;
переривання з пульта оператора обчислювальної системи;
переривання від іншого процесора або обчислювальної системи.
Внутрішні. Викликаються подіями, що пов’язані з роботою процесу, що виконується і є синхронними з його операціями. Такі переривання виникають:
при неправильній адресації (в адресній частині команди вказано заборонену або неіснуючу адресу, звертання до відсутнього сегменту або сторінки віртуальної пам’яті);
при наявності в полі коду операції, неіснуючої команди;
при діленні на нуль;
при переповненні, або пропаданні порядку в числах з плаваючою крапкою;
при виявленні порушення паритету парності, а також помилок в роботі різних пристроїв апаратури комп’ютера засобами контролю;
переривання за звертаннями до супервізора. У деяких комп’ютерах існують привілейовані команди, які може виконувати тільки ОС, а не програми користувачів. Відповідно в апаратурі передбачено різні режими роботи. При спробі виконати таку команду заборонену в даному режимі, відбувається внутрішнє переривання і керування передається супервізору ОС.
Програмні переривання. Викликаються відповідними командами переривання. За такими командами процесор виконує практично такі самі дії, що й при внутрішній перериваннях.
За рінями пріоритету переривання розподіляються наступним чином:

Оскільки переривання виникають у довільні моменти часу та при їх виникненні вже можуть існувати декілька сигналів переривань, що повинні оброблятися тільки послідовно, то щоби обробити їх в деякому логічному порядку перериванням присвоюють пріоритети. Переривання з більш високим пріоритетом обробляється позачергово, обробка інших переривань відкладається. Отже переривання з високим пріоритетом може перевати обробку переривання з нижчим пріоритетом.
Перемикання контексту. Для обробки кожного з видів переривань в складі ОС передбачені програми, що називаються обробниками переривань (IH – Interrupt Handler). Коли відбувається переривання, ОС запам’ятовує стан перерваних процесів та передає керування відповідним обробникам переривань. Ця процедура називається перемиканням контексту. При її реалізації використовуються слова стану програми (Program Status Word, PSW), які керують напрямком виконання команд і містять різну інформацію про відносно стану процесу.
Існує три типи PSW: поточне(біжуче), нове та старе.

Адреса наступної команди, що має виконуватися, міститься в поточному PSW, у ньому вказані також типи переривань, що дозволені заборонені на даний час.
CPU реагує на дозволені переривання. Обробка заборонених переривань або відкладається, або ігнорується. Процесору не можна заборонити реагувати на переривання супервізора, з рестарту та на деякі види програмних переривань.
В однопроцесорній машині є тільки одне поточне PSW, але N нових та N старих (по одному на кожен тип переривань).
Нове PSW для переривання поточного типу містить постійну адресу, за якою резидентно міститься обробник переривань цього типу. Коли відбувається переривання і якщо процесору не заборонено обробляти переривання цього типу, відбувається автоматичне (виконується апаратурою) перемикання PSW за схемою:
Поточне PSW стає старим PSW для переривань цього типу;
Нове PSW для переривань цього типу стає поточним PSW.
Коли обробку переривання завершено, ЦП починає обслуговувати або той процес, який виконувався в момент переривання, або готовий процес з найвищим пріоритетом. Це залежить від того, чи дозволяє перерваний процес перехоплення ЦП, чи ні. Якщо ні, то перерваний процес знову отримує у своє розпорядження ЦП. Якщо дозволяє, то він отримає доступ до ЦП тільки у випадку, якщо нема інших процесів готових до виконання.

4. Поняття про відеосистему. Режими роботи відеосистемиВідеосистема включає такі компоненти:
монітор (дисплей);
графічний адаптер (відеоадаптер);
драйвери відеосистеми.
Монітор (дисплей) комп'ютера призначений для виведення на екран текстової та графічної інформації. Монітори можуть бути кольоровими і монохромними. Вони можуть працювати в одному з двох режимів: текстовому або графічному.
Адаптер керує дисплеєм з плати в одному з роз'ємів розширення (в деяких комп'ютерах адаптер знаходиться на системній платі).
Графічний адаптер розміщується на системній платі або встановлюється в слот системної шини. З системного боку адаптер містить відеопам’ять, регістри вводу-виводу, модуль розширення BIOS. До монітору адаптер посилає сигнали управління яскравістю променів RGB (Red, Green, Blue – базисні кольори) та синхросигнали строкової та кадрової розгорток. PnP-монітори при наявності відповідної підтримки адаптером здатні повідомляти системі свої параметри (модель, параметри синхронізації). Архітектура PC допускає установку до двох адаптерів з роздільними моніторами.
Текстовий режим. У текстовому режимі екран монітора умовно розбивається на окремі ділянки-знакомісця, частіше всього на 25 рядків по 80 символів (знакомісць). У кожне знакомісць може бути виведений один з 256 заздалегідь заданих символів. До цих символів входять великі і малі латинські букви, цифри, а також псевдографічний символи, що використовуються для виведення на екран таблиць і діаграм, побудови рамок навколо ділянок екрана і т. д. Також це можуть бути символи кирилиці (літери російського алфавіту). На кольорових моніторах кожному знакомісць може відповідати свій колір символу і свій колір фону.
Графічний режим. Графічний режим монітора призначений для виведення на екран графіків, малюнків і т. д. Зрозуміло, що у цьому режимі можна також виводити і текстову інформацію. У графічному режимі екран монітора складається з точок, кожна з яких може бути темної чи світлої на монохромних моніторах або одного з декількох кольорів на кольоровому.
Загальні параметри відеосистеми:
роздільна здатність (resolution) Hor x Vert – кількість точок в рядку по горизонталі та кількість рядків;
режим (mode Type) – адресація елементів зображення:
ТХТ – текстовий;
Gr, APA (Graphics, All Points Addressable) – графічний, всі точки адресуються.
кількість кольорів або градацій сірого – розуміється і як максимальна кількість одночасно присутніх кольорів на екрані, і як кольорова гама – кількість можливих кольорів. Відповідність кольорів з гами комбінаціям біт визначається палітрою (palette), що переключається програмно (CGA, EGA) або програмується матрицею RAMDAC (VGA, SVGA);
текстовий формат (Character Format) Col x Lin – кількість колонок та рядків символів на екрані;
формат знакомісця (Character Box) Hor x Vert – кількість точок в знакомісці (текстовий формат);
частота сканування (Scan Frequency) – кадрова (вертикальна) та построкова (горизонтальна) частоти розгортки;
режим розгортки (Scan Mode): NI (Non-Interlaced) – построковий, I (Interlaced) – черезстроковий;
продуктивність
DOS performance – швидкість виводу символів або пікселів;
GUI performance – швидкість при виводі примітивів Windows GUI;
Video Display performance – продуктивність виводу “живого” відео, підвищується застосуванням апаратних кодеків (MPEG та ін.); підвищення продуктивності виражається в підвищенні якості декодування, зменшенні кількості пропущених кадрів та зниженні завантаженості процесору).
підтримка Display Power-Management Signal монітором та адаптером забезпечують можливість управління енерговживанням монітора по командам системи.
підтримка Display Data Channel – інтерфейсу обміну даними з монітором для PnP-моніторів.
Відеорежими (BIOS Video Modes) визначають формат відображення:
режими 0-13h – стандартні для адаптерів MDA, CGA, EGA, VGA; встановлюються параметром функції 0 BIOS INT 10h (AH=0, AL=Mode). Серед стандартних режимів – текстові 80х25 та 40х25 символів, графічні 320х200 (4, 16, 256 кольорів) та 640х350, 640х400 / 640х480 (2, 4, 16 кольорів);
режими 14h-7Fh – нестандартні VGA- або SVGA- розширення BIOS, специфічні для конкретних моделей;
режими вище 100h стандартизовані VESA, встановлюються параметром функції 4F02h BIOS INT 10h (AX=4F02h, BX=Vmode). Це режими SVGA моніторів 640x480, 800x600, 1024x768, … з 8, 15, 16, 24, 32-бітним кольором, а також текстові режими 132x25, 132x43, 80x60 символів.
Взаємодія між програмним забезпеченням та відеосистемою може відбуватися на трьох рівнях:
на рівні операційної системи: за допомогою програмного системного переривання, вбудованого в ОС; продуктивність при цьому найнижча, але найвища переносимість програми;
за допомогою BIOS: керування дисплеєм здійснюється через перервання INT 10h, функції якого утворюють драйвер дисплея; хороша продуктивність, переносимість на комп’ютери з однотимними відеоадаптерами;
пряме керування: через програмно доступні регістри (порти введення-виведення); найвища продуктивність, проте найгірша переносимість.

5. Структура таблиці розміщення файлів на магнітних дисках.Фізичний та логічний формати магнітних дисків. Коренева директорія.Таблиця розміщення файлів (FAT – File Allocation Table) містить інформацію про розміщення файлів на диску. Оскільки область даних диску розбито на кластери, то FAT містить інформацію про послідовність кластерів, які необхідно прочитати, щоб зібрати цілий файл з частин-кластерів.
Розглянемо FAT-16. Число 16 вказує на розмір елементів FAT – 16 біт. Для дискет FAT є 12-бітним. Також є FAT-32. Спеціальні помітки кластерів в FAT: 0000 – вільний кластер, nnnn – номер наступного кластера для файлу, FFF7 – невикористовуваний кластер (збійна доріжка), FFFF – останній кластер файлу.
Нехай деякий файл розміщено на кластерах з номерами 2, 3 та 5. Тоді елемент каталогу для цього файлу буде містити (серед інших параметрів) 0002 – номер першого кластеру файлу, а FAT буде виглядати наступним чином:
Відносний кластер 0 1 2 3 4 5 6
Елемент FAT **** **** 0003 0005 **** FFFF ****
На фізичному рівні магнітні диски складаються з секторів, що складають доріжки на диску (для дискет, як правило, 9, або 15, або 18 на доріжку), певна кількість яких складає поверхню (для дискет, як правило, їх кількість дорівнює 40 або 80). Поверхонь може бути 1 чи 2 (для дискет) або більше (для вінчестерів). Тобто на фізичному рівні найменшою одиницею адресації диску є сектор, а сама адресація – тривимірна за рахунок тривимірної геометрії дисків (голівка/поверхня - доріжка - сектор на доріжці). Іноді всі сектори диску вишиковують у лінійний порядок.
Фізично жорсткий диск може містити до 4 розділів (Partition). Інформація про структуру диску зберігається в Master Boot Record (MBR) – сектор 1, циліндр 0, голівка 0, – який завантажується за адресою 0:7С00h та виконується при спробі початкового завантаження з вінчестеру. Первинний розділ DOS (Primary DOS Partition) містить 1 логічний диск. Розширений розділ DOS (Extended DOS Partition) може бути розбито на довільну кількість логічних дисків, їх завантажники ніколи не виконуються. Конфігурування диску – розбиття на розділи, вибір активного (тільки на першому фізичному диску) розділу та створення логічних дисків в розширеному DOS-розділі виконується програмою FDISK після Low-Level Format. Далі йде форматування верхнього рівня (логічне).
На логічному рівні структура диску DOS є наступною: перший сектор диску – Boot Record – містить опис структури диску та програму завантаження системи. Структура наступних секторів залежить від типу ОС. DOS-диски містять: декілька копій FAT (File Allocation Table) – таблиць розміщення файлів, кореневий каталог (Root) та безпосередньо область даних. Ця остання частина диску ділиться на кластери (певна кількість секторів), і адресація даних здійснюється не до секторів, а до кластерів, які вишикувані у лінійний порядок і нумеруються, починаючи з 0. Отже, форматування логічного рівня для DOS – це створення Boot, FAT, Root та помітка в FAT дефектних кластерів (тих, що не пройшли верифікацію) – виконується командою FORMAT.
Коренева директорія диску містить інформацію про файли та каталоги, що знаходяться на верхньому рівні деревовидної ієрархії каталогів диску. Кожен запис Root складається з: імені та розширення файлу і його параметрів (довжина в байтах, дата та час створення, номер першого кластеру розміщення вмісту цього файлу на диску, атрибути – архівний, тільки для читання, системний, схований, ознака каталогу, ознака мітки тому). При видаленні файлу перший символ його імені замінюється на символ E5h. Завдяки цьому можливою стає процедура типу UNDELETE. Якщо деякий запис є каталогом (а не файлом), то його вміст повторює структуру кореневого каталогу, додаються тільки два записи - з іменами “.” та “..” – поточний каталог та вихід на попередній рівень структури каталогів.

6. Системи телеобробки даних. Функціональне середовище для взаємодії систем телеобробки. Етапи у взаємодії систем телеобробки.Система телеобробки – сукупність технічних і програмних засобів, призначена для обробки на ЕОМ даних, переданих по каналах зв'язку. Абоненти системи (користувачі, технічні об'єкти) підключаються до ЕОМ за допомогою каналів зв'язку. Канал зв'язку складається з лінії зв'язку, по якій передаються сигнали, і апаратури передачі даних, що перетворить даних в сигнали, відповідні до типу лінії зв'язку (каналу). Архітектура системи визначає основні її елементи та характер і топологію взаємодії цих елементів.
До систем телеобробки інформації відносять системи, які дозволяють користувачам використовувати віддалені (remote) обчислювальні ресурси. Під такими ресурсами розуміють данні та програми, що перебувають за межами процесу конкретної задачі користувача.
Доступ фізично здійснюється за допомогою мереж. Мережа (Network) – технічні апаратні засоби (фізичне середовище передачі), що звязують різні системи та забезпечують обмін данних між ними. Мережі можна розділити на:
аналогові та цифрові;
однонаправлені та двонаправлні (ці в свою чергу поділяються на синронизовані та асинхронні);
броадкастові та пойнт-ту-пойнт.
Телеобработка (Teleprocessing) – автоматизированная обработка данных, при которой устройства вв/выв находятся на удаленном расстоянии от централ. процессора. Телеобработка данных – это организация инф.-выч. процесса, при которой ресурсы одной или нескольких ЭВМ одновременно используются многими пользователями через различные виды средств связи.
Системы телеобработки обеспечивают организацию двух основных методов обработки данных – пакетного и диалогового. В зависимости от архитектурных принципов телеобработка делится на системную и сетевую.
Системная телеобработка – совокупность техн. и прогр. средств, обеспечивающая коллективное использование ресурсов одной ЭВМ большим количеством пользователей, подключенных к ЭВМ через средства связи.
Сетевая телеобработка – совокупность унифицированных логич. и физ. средств, протоколов, интерфейсов, обеспечивающая возможность распределения управляющих и обрабатывающих ресурсов Такая телеобработка обеспечивает коллективное использование ресурсов одной или нескольких территориально рассредоточенных ЭВМ большим количеством пользователей, подключенных к ЭВМ через средства связи и передачи данных. Средства сетевой телеобработки обеспечивают объединение различных вычислительных средств в сеть и доступ локальных и удаленных пользователей к распределенным в сети информационно-вычислительным ресурсам и базам данных.
В практике объединение компьютеров в сеть позволяет совместным пользователям использовать:
Аппаратные средства (жесткие диски);
Программные средства;
Многопользовательские системы (электронную почту, информационные системы на основе базы данных).

7. Модель відкритої системи, стек протоколів. Концепція еталонної моделі OSI.Під відкритою ситемою розуміють таку, що за допомогою свого стандарту надає можлівість обміну інформацією між різними операційними середовищами. Відкрита ситема підтримує послідовність рівнів, кожен з яких відповідає за певну організацію передачі данних.
Еталонна модель OSI:
Рівень 7, Прикладний (Application) – найвищий рівень моделі OSI. Він являє собою засіб для доступу прикладних процесів до мережевих послуг. Цей рівень забезпечує послуги підтримки прикладних програм користувача, наприклад, програмного забезпечення для передачі файлів, доступу до баз даних, електронної пошта.
Рівень 6, Рівень представлення (Presentation), визначає формат, використовуваний для обміну даними між комп'ютерами мережі. На комп'ютері-відправнику дані, що надійшли від Прикладного рівня на цьому рівні перекладаються в загальнозрозумілий проміжний формат. На комп'ютері-одержувачі на цьому рівні відбувається переклад із проміжного формату в той, що використовується Прикладним рівнем даного комп'ютера. Представительський рівень відповідає за перетворення протоколів, трансляцію даних, їхнє шифрування, зміну або перетворення застосовуваного набору символів (кодової таблиці). Представительський рівень, крім того, управляє стиском даних для зменшення переданих бітів.
Рівень 5, Сеансовий (Session), дозволяє двом програмам на різних комп'ютерах встановлювати, використовувати і завершувати мережеве з'єднання, зване сеансом. На цьому рівні виконуються такі функції, як розпізнавання імен і захист, необхідні для зв'язку двох програм у мережі.
Сеансовий рівень забезпечує синхронізацію між задачами користувача за допомогою розставляння в потоку даних контрольних точок (chekpoints). Таким чином, у випадку мережевої помилки, буде потрібно наново передати тільки дані, що йдуть за останньою контрольною точкою. На цьому рівні виконується керування діалогом між взаємодіючими процесами, тобто регулюється, яка зі сторін здійснює передачу, коли, як довго і т.д.
Рівень 4, Транспортний (Transport), забезпечує додатковий рівень з'єднання - нижче Сеансового рівня. Транспортний рівень гарантує доставку пакетів без помилок, у тієї ж послідовності, без втрат і дублювання. Транспортний рівень управляє потоком, перевіряє помилки і бере участь у рішенні проблем, пов'язаних із відправленням і одержанням пакетів.
Рівень 3, Мережевий (Network), відповідає за адресацію повідомлень і переклад логічних адрес і імен у фізичні адреси. Одним словом, виходячи з конкретних мережних умов, пріоритету послуги й інших чинників тут визначається маршрут від комп'ютера-відправника до комп'ютера-одержувача. На цьому рівні вирішуються також такі задачі і проблеми, пов'язані з мережним трафиком, як комутація пакетів, маршрутизація і перевантаження.
Рівень 2, Канальний, здійснює передачу кадрів (frames) даних від Мережного рівня до Фізичного. Кадри - це логічно організована структура, у якій можна поміщати дані. Канальний рівень комп'ютера-одержувача упаковує «сирий» потік бітів, що надходять від Фізичного рівня, у кадри даних. Канальний рівень забезпечує точність передачі кадрів між комп'ютерами через Фізичний рівень. Це дозволяє Мережевому рівню вважати передачу даних по мережевому з'єднанню фактично безпомилковою.
Рівень 1, Фізичний, – найнижчий у моделі OSI. Цей рівень здійснює передачу неструктурованого, «сирого» потоку бітів по фізичному середовищу (наприклад, по мережевому кабелю). Тут реалізуються електричний, оптичний, механічний і функціональний інтерфейси з кабелем. Фізичний рівень також формує сигнали, що переносять дані, що надійшли від усіх рівнів, що лежать вище.
На цьому рівні визначається засіб з'єднання мережевого кабеля з платою мережного адаптера, зокрема, кількість контактів і їхній функції. Крім того, тут визначається засіб передачі даних по мережевому кабелю.
8. Стек протоколів TCP/IP: топологічні особливості, функції рівнів.TCP/IP – загальна назва для набору (стеку) мережевих протоколів різних рівнів, що використовуються в мережі Інтернет. Особливості TCP/IP:
відкриті стандарти протоколів, що розроблялися незалежно від апаратного та програмного забеспечення;
незалежність від фізичної середи передачі даних;
система унікальної адресації;
стандартизовані протоколи високого рівня для популярних сервісів.
Модель протоколу TCP/IP поділена на чотирі рівні:
рівень мережевого інтерфейсу керує обміном данних між пристроєм та мережею, а також маршрутизує данні між пристроямі однеї мережи. Функціонально еквівалентний фізичному та канальному рівням моделі OSI;
міжмережевий рівень керує обміном данними між пристроями, що знаходяться в різних мережах. Відповідає за функції сітьової адресації та відповідно сітьовому рівню в моделі OSI.
транспортний рівень організовує зв'язок між джерелом та приймачем данних. Відповідає транспортному рівню моделі OSI.
прикладний рівень забезпечує функції, що необхідні програмам користувача та включає в себе функції вищих рівней моделі OSI.
Транспортный протокол ТСР в стеке протоколов TCP/IP. Эти протоколы берут свое начало от одной из первых территориальных сетей ARPANET. Они получили широкое распространение благодаря реализации в ОС Unix и в сети Internet и в настоящее время оформлены в виде стандартов RFC (Requests For Comments) организацией IETF (Internet Engineering Task Force). TCP - дуплексный транспортный протокол с установлением соединения. Его функции: упаковка и распаковка пакетов на концах транспортного соединения; установление виртуального канала путем обмена запросом и согласием на соединение; управление потоком; помещение срочных данных между специальными указателями, т.е. возможность управлять скоростью передачи.
Сетевой протокол IP в стеке протоколов TCP/IP. IP - дейтаграммный сетевой протокол без установления соединения. Его функции: фрагментация и сборка пакетов при прохождении через промежуточные сети, имеющие другие протоколы; маршрутизация; проверка контрольной суммы заголовка пакета (правильность передачи всего пакета проверяется на транспортном уровне, т.е. с помощью TCP, в оконечном узле); управление потоком - сброс дейтаграмм при превышении заданного времени жизни.
В состав протокола IP входит ряд частных протоколов. Среди них протоколы ARP, IGP, EGP, относящиеся к маршрутизации на разных иерархических уровнях в архитектуре сети. На одном уровне с IP находится протокол управления ICMP (Internet Control Message Protocol).
Протокол ARP (Address Resolution Protocol) относится к связям "хост-хост" или "хост-шлюз" в конкретной подсети. Он использует локальные таблицы маршрутизации - ARP-таблицы, устанавливающие соответствие IP-адресов с NPA (Network Point of Attachment) адресами серверов доступа в соответствующих подсетях. В подсетях не нужно рассчитывать кратчайший путь и определять маршрут в разветвленной сети, что, естественно, ускоряет доставку. ARP-таблицы имеются в каждом узле. Если в таблице отправителя нет строки для IP-адреса получателя, то отправитель сначала посылает широковещательный запрос. Если некоторый узел имеет этот IP-адрес, он откликается своим NPA, и отправитель пополняет свою таблицу и отсылает пакет. Иначе отправка пакета произойдет на внешний порт сети.
Протокол IGP (Interior Dateway Pr.) предназначен для управления маршрутизацией в некотором домене (автономной сети - AS), т.е. он определяет маршруты между внутренними сетями домена. Другими словами, в AS имеется (или может быть получена) информация о путях ко всем сетям домена, и протокол IGP доставляет дейтаграмму в нужную подсеть в соответствии с алгоритмом маршрутизации RIP или OSPF. (В основе – алг. Дейкстры).
Протокол EGP (Exterior Gateway Pr.) относится к корневой сети и предназначен для управления маршрутизацией между внешними шлюзами и пограничными маршрутизаторами доменов. В TCP/IP входит также протокол UDP (User Datagram Protocol) - транспортный протокол без установления соединения, он значительно проще TCP, но используется чаще всего для сообщений, умещающихся в один пакет. После оформления UDP-пакета он передается с помощью средств IP к адресату, который по заголовку IP-пакета определяет тип протокола и передает пакет не агенту ТСР, а агенту UDP. Агент определяет номер порта и ставит пакет в очередь к этому порту. В UDP служебная часть дейтаграммы короче, чем в ТСР, не требуется предварительного установления соединения или подтверждения правильности передачи, как это делается в TCP, что и обеспечивает большую скорость за счет снижения надежности доставки
Среди протоколов управления различают протоколы, реализующие управляющие функции сетевого уровня, и протоколы мониторинга за состоянием сети, относящиеся к более высоким уровням. Основные функции протоколов мониторинга заключаются в сборе информации о состоянии сети, в предоставлении этой информации нужным лицам путем посылки ее на соответствующие узлы, в возможном автоматическом принятии необходимых управляющих мер. В сетях ТСР/IP роль первых из них выполняет протокол ICMP, роль вторых - протокол SNMP (Simple Network Management Protocol).
Основные функции ICMP:
оповещение отправителя с чрезмерным трафиком о необходимости уменьшить интенсивность посылки пакетов;
передача откликов (квитанций) на успешно переданные пакеты;
контроль времени жизни Т дейтаграмм и их ликвидация при превышении Т или по причине искажения данных в заголовке;
оповещение отправителя о недостижимости адресата;
формирование и посылка временных меток (измерение задержки) для контроля времени доставки пакетов.
ICMP-пакеты вкладываются в IP-дейтаграммы при доставке.
Протокол SNMP относится к прикладному уровню в стеке протоколов TCP/IP. Менеджер (серверная программа SNMP) посылает запросы агентам, агенты (т.е. программы SNMP объектов управления) устанавливаются в контролируемых узлах, они собирают информацию (например, о загрузке, очередях, временах совершения событий), и передают ее серверу для принятия нужных мер.
Для посылки команд SNMP используется транспортный протокол UDP. Одной из проблем управления по SNMP является защита агентов и менеджеров от ложных команд и ответов, которые могут дезорганизовать работу сети. Используется шифрование сообщений, но это снижает скорость реакции сети на происходящие события. Расширением SNMP являются протоколы RMON (Remote Monitoring) для сетей Ethernet и Token Ring и RMON2 для сетевого уровня.

9. Архітектура мережевої телеобробки: однорангова, клієнт/сервер, трирівневаСистема телеобробки - сукупність технічних і програмних засобів, призначена для обробки на ЕОМ даних, переданих по каналах зв'язку. Абоненти системи (користувачі, технічні об'єкти) підключаються до ЕОМ за допомогою каналів зв'язку. Канал зв'язку складається з лінії зв'язку, по якій передаються сигнали, і апаратури передачі даних, що перетворить даних в сигнали, відповідні до типу лінії зв'язку (каналу). Архітектура системи визначає основні її елементи та характер і топологію взаємодії цих елементів;
Архітектура представляє собою логічну, функціональну й фізичну організацію технічних і програмних засобів мережі. У сучасній архітектурі виділяється чотири групи об'єктів: клієнти, сервери, дані й мережеві служби. Клієнти розташовуються в системах користувачів, що перебувають на робочих місцях. Дані зберігаються в основному в серверах. Мережеві служби є спільно використовуваними прикладними програмами, які взаємодіють із клієнтами, серверами й даними. Крім цього, служби управляють процедурами розподіленої обробки даних, інформують користувачів про зміни, що відбуваються в мережі. Розглянемо такі основні види архітектур: однорангову, клієнт-сервер і трирівневу.
Однора́нгові, децентрализо́вані або пірінгові (від англ. peer-to-peer, P2P - рівний до рівного) мережі - це комп'ютерні мережі, засновані на рівноправності учасників. У таких мережах відсутні виділені сервери, а кожний вузол (peer) є як клієнтом, так і сервером. На відміну від архітектури клієнт- сервера, така організація дозволяє зберігати працездатність мережі при будь-якій кількості й будь-якій комбінації доступних вузлів. Адміністрування однорангової мережі може бути складніше за рахунок більшого числа серверів і більш розвинених можливостей кожного сервера. Невиділені сервери повільніше спеціалізованих.
Одна з областей застосування технології однорангових мереж – це обмін файлами. Користувачі файлообмінної мережі викладають які-небудь файли в т.зв. "розшарену" (англ. share - ділитися) директорію, зміст якої є доступним для скачування іншими користувачами. Процес проходить таким чином: який-небудь користувач мережі надсилає запит на пошук якого-небудь файлу, програма шукає серед клієнтів мережі файли, відповідні до запиту, і показує результат. Після цього користувач може скачати файли з знайдених джерел. У сучасних файлообмінних мережах інформація завантажується відразу з декількох джерел. Її цілісність перевіряється по контрольних сумах. Зазвичай в таких мережах обмінюються фільмами й музикою, що є споконвічним головним болем відеовидавничих і звукозаписних компаній. Проблемою стає те, що припинити поширення файлу в децентралізованої пірінговій мережі технічно неможливо - для цього буде потрібно фізично відключити від мережі всі машини, на яких лежить цей файл, а таких машин може бути дуже й дуже багато.
Крім виключно P2 P-Мереж, існують так звані гібридні мережі, у яких існують сервери, що використовуються для координації роботи, пошуку або надання інформації про існуючі машини у мережі та їх статуси (on-line, off-line і т.д. ). Гібридні мережі поєднують швидкість централізованих мереж і надійність децентралізованих завдяки гібридним схемам з незалежними індексованими серверами, що синхронізують інформацію між собою. При виході з ладу одного або декількох серверів мережа продовжує функціонувати. До частково децентралізованих мереж відносяться Edonkey, Bittorrent.
Архітектура клієнт-сервер:
Тут клієнти виконують прості операції обробки даних, відпрацьовують інтерфейс взаємодії із сервером, звертаються до нього із запитами. Більшу ж частину завдань обробки виконує сервер. Для цих цілей він має базу даних. Високі вимоги до виділеного сервера забезпечення високої продуктивності вимагає установки на сервері великої кількості оперативної пам'яті, диска великого розміру й використання в сервері продуктивного процесора. При порушенні роботи сервера мережа стає практично непрацездатною.
Архітектура клієнт- сервер поступово перетворюється в архітектуру клієнт-мережа, у якій використовується не один, а безліч серверів. Наприклад, у мережі Internet їх сотні тисяч. Прагнення дати можливість роботи в мережі клієнтам, створеним різними виробниками, привело до виникнення архітектури будь-який клієнт – сервер.
Трирівнева архітектура:
У комп'ютерних технологіях трирівнева архітектура (з англ. three-tier або Multitier architecture) припускає наявність наступних компонентів додатка: клієнтський додаток (звичайно говорять "тонкий клієнт" або термінал), підключений до сервера додатків, який у свою чергу підключений до сервера бази даних.
Термінал – це інтерфейсний (звичайно графічний) компонент, який представляє перший рівень- додаток для кінцевого користувача. Перший рівень не повинен мати прямих зв'язків з базою даних (по вимогах безпеки), бути навантаженим основною бізнес- логікою (по вимогах масштабованості) і зберігати стан додатка (по вимогах надійності). На перший рівень може бути винесена і звичайно виноситься найпростіша бізнес- логіка: інтерфейс авторизації, алгоритми шифрування, перевірка значень, що вводяться, на допустимість і відповідність формату, нескладні операції (сортування, угруповання, підрахунок значень) з даними, уже завантаженими на термінал.
Сервер додатків розташовується на другому рівні. На другому рівні зосереджена більша частина бізнес-логіки. Поза ним залишаються фрагменти, експортовані на термінали, а також занурені в третій рівень збережені процедури й тригери.
Сервер бази даних забезпечує зберігання даних і виноситься на третій рівень. Звичайно це стандартна реляційна або об'єктно-орієнтована СУБД. Якщо третій рівень являє собою базу даних разом зі збереженими процедурами, тригерами й схемою, що описує додаток у термінах реляційної моделі, то другий рівень будується як програмний інтерфейс, що зв'язує клієнтські компоненти із прикладною логікою бази даних.
У найпростішій конфігурації фізично сервер додатків може бути сполучений із сервером бази даних на одному комп'ютері, до якого по мережі підключається один або кілька терміналів. В "правильній" (з погляду безпеки, надійності, масштабування) конфігурації сервер бази даних перебуває на виділеному комп'ютері (або кластері), до якого по мережі підключено один або кілька серверів додатків, до яких, у свою чергу, по мережі підключаються термінали.
Прикладом трирівневої архітектури є взаємодія MySQL-серверу, технологій ADO.NET, ASP.NET та web-серверу IIS.

10. Надійність систем телеобробки та комп’ютерних мереж. Класи безпеки. Міжмережеві екрани. Proxy-сервери, брандмауери.Брандмауер – це автоматизована система або комплекс систем, що дозволяють розділити мережу на дві або більше частин і забезпечує захисні механізми від НСД на рівні пакетів обміну інформацією мережевого, транспортного та прикладного рівнів мережевих протоколів Семирівнева моделі OSI.
Деякі міжмережеві екрани дозволяють організовувати віртуальні корпоративні мережі (Virtual Private Network). При цьому декілька локальних мереж, підключених до глобальної мережі, об'єднуються в одну віртуальну корпоративну мережу. Передача даних між цими локальними мережами здійснюється прозоро для користувачів локальних мереж. При цьому забезпечується конфіденційність та цілісність інформації, що передається за допомогою різних засобів: шифрування, використання цифрових підписів і т.п.
Підтримуваний рівень мережевої моделі OSI є основною характеристикою при класифікації міжмережевих екранів. Розрізняють такі типи міжмережевих екранів:
керовані комутатори (канальний рівень);
мережеві фільтри (мережевий рівень);
шлюзи сеансового рівня (circuit-level proxy);
посередники прикладного рівня;
інспектори стану (stateful inspection), що представляють собою міжмережеві екрани сеансового рівня з розширеними можливостями.
Крім виконання своїх основних функцій, міжмережеві екрани експертного класу мають добре продуману систему протоколювання подій та оповіщення адміністраторів.
Посередники прикладного рівня (application-level proxy), часто звані proxy-серверами, контролюють і фільтрують інформацію на прикладному рівні ієрархії OSI. Посередники розрізняють за підтримуваних протоколів прикладного рівня. Найбільш часто підтримуються служби Web (HTTP), FTP, SMTP, POP3/IMAP, NNTP, Gopher, Telnet, DNS. Коли клієнт внутрішньої мережі звертається, наприклад, до сервера Web, то його запит потрапляє до посередника Web (або перехоплюється їм). Останній встановлює зв'язок з сервером від імені клієнта, а отриману інформацію передає клієнту. Для зовнішнього сервера посередник виступає в якості клієнта, а для внутрішнього клієнта - як сервер Web. Аналогічно посередник може працювати і у випадку зовнішнього клієнта і внутрішнього сервера.
Посередники прикладного рівня поділяються на прозорі (transparent) і непрозорі.
Прозорі посередники невидимі для клієнтів і серверів: клієнт звертається до сервера самим звичайним способом, а посередник перехоплює запит і діє від імені клієнта. Особливою популярністю користуються прозорі посередники для сервісу Web, їх нерідко встановлюють провайдери Internet з метою підвищення продуктивності праці та зниження навантаження на глобальні канали зв'язку за рахунок кешування інформації.
У випадку непрозорих посередників клієнтську систему потрібно явно налаштувати на роботу з посередником. Непрозорі посередники гарні там, де потрібна сувора аутентифікація при вході у внутрішню мережу або на виході з неї.

11. Мультиплексування цифрових каналів з розділенням у часі (TDM).Плезіохронні та синхронні цифрові ієрархії. Широкосмугові канали зв’язку.Цифровой канал представляет собой соединение при котором данные передаются как в обычной LAN в виде цифровых сигналов уровня 0 и 1, и операция модуляция/демодуляция не производится . За счет этого можно непосредственно работать по стандартам протокола TCP/IP и повішается скорость и пропускная способность канала.
Под каналом связи понимают логическое (виртуальное) соединение между источником и получателем, по которому проходят данные. Узкополосный канал - это канал в области передачи данных, полоса пропускания (макс. скорость передачи данных) которого не превышает 2400 bps. Соответственно широкополосная связь обеспечиваеться полосой пропускания:
до 56Кbps по обычной телефонной линии;
до 128Kbps по ISDN- каналу;
до 1.54 Мbps по линии Т1;
до 40 Мbps по сети КТВ.
Коммутация каналов на основе разделения времени. Аппаратура TDM-сетей - мультиплексоры, коммутаторы, демультиплексоры - работает в режиме разделения времени, поочередно обслуживая в течение цикла своей работы все абонентские каналы. Цикл работы оборудования TDM равен 125 мкс, что соответствует периоду следования замеров голоса в цифровом абонентском канале. Это значит, что мультиплексор или коммутатор успевает вовремя обслужить любой абонентский канал и передать его очередной замер далее по сети.
Мультиплексор принимает информацию по N входным каналам от конечных абонентов, каждый из которых передает данные по абонентскому каналу со скоростью 64 Кбит/с - 1 байт каждые 125 мкс. В каждом цикле мультиплексор выполняет следующие действия:
прием от каждого канала очередного байта данных;
составление из принятых байтов уплотненного кадра, называемого также обоймой;
передача уплотненного кадра на выходной канал с битовой скоростью, равной N*64 Кбит/с.
Порядок байт в обойме соответствует номеру входного канала, от которого этот байт получен. Количество обслуживаемых мультиплексором абонентских каналов зависит от его быстродействия.
Демультиплексор выполняет обратную задачу - он разбирает байты уплотненного кадра и распределяет их по своим нескольким выходным каналам, при этом он считает, что порядковый номер байта в обойме соответствует номеру выходного канала. Коммутатор принимает уплотненный кадр по скоростному каналу от мультиплексора и записывает каждый байт из него в отдельную ячейку своей буферной памяти, причем в том порядке, в котором эти байты были упакованы в уплотненный кадр.
Соединение в сети TDM всегда обладает известной и фиксированной пропускной способностью, кратной 64 Кбит/с. Сети, использующие технику TDM, требуют синхронной работы всего оборудования, что и определило второе название этой техники – синхронный режим передач (STM).

12. Повторювачі, мости, маршрутизатори, шлюзи та їх місце в профілі OSIРепітери
Електричний сигнал при передачі по кабелю спотворюється, оскільки зменшується його амплітуда. У результаті, якщо кабель має достатню довжину, загасання може спотворити сигнал до невпізнанності. Проте завдяки репітерам (repeater) сигнали спроможні поширюватися на великі відстані. Репітер працює на Фізичному рівні моделі OSI. Репітер приймає загасаючий сигнал з одного сегмента, відновлює його і передає в інший сегмент. Щоб дані через репітер надходили з одного сегмента в інший, кожний сегмент повинен використовувати однакові пакети та протоколи. Проте репітери можуть передавати пакети з одного типу фізичного носія в інший.
Розширення локальних мереж. Мости.
Міст (bridge), як і репитер, може з'єднувати сегменти або локальні мережі робочих груп. Проте, на відміну від репітера, міст також служить для розбивки мережі, що допомагає ізолювати трафик. Мости працюють на Канальном рівні моделі OSI. Мости звичайно вирішують такі задачі:
збільшують максимальну кількість комп'ютерів у мережі, та усувають вузькі місця, що з'являються в результаті підключення надлишкового числа комп'ютерів;
з'єднують різнорідні фізичні носії, такі, як витая пару і коаксиальний кабель;
з'єднують різнорідні сегменти мережі, наприклад Ethernet і Token Ring;
Робота моста заснована на принципі, відповідно до якого кожний вузел мережі має власну адресу - міст передає пакети, виходячи з адреси вузла призначення.
Розширення локальних мереж. Маршрутизатори.
У середовищі, що об'єднує декілька мережевих сегментів із різноманітними протоколами й архітектурами, мости не завжди гарантують швидкий зв'язок між усіма сегментами. Для такої складної мережі необхідний пристрій, що не тільки знає адресу кожного сегмента, але й визначає найкращий маршрут для передачі даних та фільтрує широкомовні повідомлення. Такий пристрій називається маршрутизатором.
Маршрутизатори (routers) працюють на Мережевому рівні моделі OSI. Це означає, що вони можуть переадресовувати пакети через множину мереж. За допомогою маршрутизаторів можна узгоджувати не лише канальні протоколи, як це має місце при застосуванні мостів, але й мережеві протоколи. Маршрутизатори можуть виконувати деякі функції мостів: фільтрувати й ізолювати трафик та з'єднувати сегменти мережі. Проте маршрутизаторам доступно більше інформації, чим мостам, і вони використовують її для оптимізації доставки пакетів.
Маршрутизатори підрозділяються на два основних типи: статичні (static) потребують, щоб адміністратор вручну створив і сконфигурировал таблицю маршрутизації, а також зазначив кожний маршрут. Динамічні (dynamic) автоматично визначають маршрути і тому потребують мінімального конфігурования.
Шлюзи
Шлюзи (gateways) забезпечують зв'язок між різноманітними архітектурами і середовищами. Зокрема, шлюз переупаковує інформацію відповідно до вимог системи призначення; змінює формат повідомлення, щоб прикладна програма на стороні, що приймає, могла розпізнати дані. Шлюз зв'язує дві системи, що використовують різні: комунікаційні протоколи; структури і формати даних; мови; архітектури.
Шлюзи створюються для виконання конкретного типу задач, тобто для конкретного типу перетворення даних. Деякі шлюзи використовують усі сім рівнів моделі OSI, проте звичайно шлюзи виконують перетворення протоколів на Прикладному рівні. Це цілком залежить від типу шлюзу.
13. Поняття мереж комутації: пакетів, каналів, повідомлень.Контроль перевантажень в мережах комутації пакетів.Любые сети связи поддерживают некоторый способ коммутации своих абонентов между собой. Абоненты соединяются с коммутаторами индивидуальными линиями связи, каждая из которых используется в любой момент времени только одним, закрепленным за этой линией абонентом. Между коммутаторами линии связи разделяются несколькими абонентами, то есть используются совместно.
Существуют три принципиально различные схемы коммутации абонентов в сетях: коммутация каналов (circuit switching), коммутация пакетов (packet switching) и коммутация сообщений (message switching). Сети с коммутацией каналов ведут свое происхождение от первых телефонных сетей. Сети с коммутацией пакетов появились в конце 60-х годов как результат экспериментов с первыми глобальными компьютерными сетями. Сети с коммутацией сообщений послужили прототипом современных сетей с коммутацией пакетов и сегодня они в чистом виде практически не существуют.
Мережі, що передають пакети від множини різноманітних користувачів по багаьох доступних маршрутах, називаються мережами з комутацією пакетів (відповідно до методу упаковування і пересилки даних).
Вихідний блок даних розбивається на пакети, і кожний пакет постачається адресою одержувача й іншої службової інформації. При комутації пакетів кожний пакет передається проміжними станціями по оптимальному на сучасному момент маршруту між джерелом і одержувачем. Хоча кожний пакет просувається власним шляхом, а пакети, що складають повідомлення, можуть досягати адресата в різний час або зі зміненою черговістю, комп'ютер, що приймає, точно відновить вихідне повідомлення.
Пакети мають невеличкий розмір. Якщо при передачі виникає помилка, то передати ще разом маленький пакет простіше, чим великий. Крім того, маленькі пакети займають комутатори протягом дуже короткого проміжку часу.
Как сети с коммутацией пакетов, так и сети с коммутацией каналов можно разделить на два класса по другому признаку - на сети с динамической коммутацией и сети с постоянной коммутацией.
В первом случае сеть разрешает устанавливать соединение по инициативе пользователя сети. Коммутация выполняется на время сеанса связи, а затем (опять же по инициативе одного из взаимодействующих пользователей) связь разрывается. В общем случае любой пользователь сети может соединиться с любым другим пользователем сети.
Во втором случае сеть не предоставляет пользователю возможность выполнить динамическую коммутацию с другим произвольным пользователем сети. Вместо этого сеть разрешает паре пользователей заказать соединение на длительный период времени.
Примерами сетей, поддерживающих режим динамической коммутации, являются телефонные сети общего пользования, локальные сети, сети TCP/IP.
В настоящее время для мультиплексирования абонентских каналов используются две техники:
техника частотного мультиплексирования (Frequency Division Multiplexing, FDM);
техника мультиплексирования с разделением времени (Time Division Multiplexing, TDM).

14. Інформаційна глобальна мережа INTERNETПід Інтернетом розуміють вільно доступну надмережу що складається із взаємозв’язаних комп’ютерних мереж, які передають дані за допомогою механізму комутації пакетів sвикористовуючи стандартний Міжмережевий Протокол (IP). Інтернет утворює глобальний інформаційний простір, є фізичною основою для Всесвітньої павутини і цілої низки схем (протоколів) передачі даних. Інтернет складається з багатьох тисяч копоративних, наукових, урядових та домашніх мереж.Об’єднання мереж різної архітектури та топології стало можливим завдяки IP і принципу комутації пакетів даних. Тобто будь-яка система (мережа) передачі цифрових даних, дротова і бездротова, може передавати в тому числі і трафік Інтернету. На стиках мереж спеціальні маршрутизатори (програмні чи апаратні) займаються сортуванням і перенаправленням пакетів даних, виходячи із IP-адрес адресатів ціх пакетів. Пртокол IP утворює єдиний адресний простір у масштабах всього світу, але в кожній окремій мережі може існувати і окремий адресний простір, яке обирається виходячи із класу мережі.
Така організація IP-адрес дозволяє маршрутизаторам однозначно визначати подальший напрямок для кожного найменьшого пакету даних.
В результаті між різними мережами Internet не виникає конфліктів, і дані точно і без перешкод передаються з мережі в мережу по всій планеті.
Інтернет використовує цілу низку протоколів.
Протокол в даному випадку – це «мова», що використовується ЕОМ для обміну даними при роботі в мережі. Щоб різні ЕОМ в мережі могли взаємодіяти, вони мають «розмовляти» однією мовою, тобто використовувати один і той самий протокол. Більшість протоколів Інтернету стандартизовано організацією IETF.
Інтернет пропонує велику кількість різноманітних послуг. До найпопулярніших відносяться Всесвітня павутина, Електронна пошта, групи новин, файлообмінні мережі, електронні платіжні системи, IP-телефонія.

15. Система доменних імен глобальної мережі INTERNETDNS (Domain Name System) – це система, що дозволяє перетворювати символьні імена доменів на IP-адреси (і навпаки) в мережах TCP/IP.
Домен – певна зона у ситемі доменних імен (DNS) Інтернету, що виділяється певній країні, організації чи особі для тих чи інших цілей.
DNS важлива для роботи Інтернету, бо для встановлення з’єднання з вузлом необхідна інформація про його IP-адресу, а для користувачів простіше запам’ятовувати імена з літер (як правило семантично багатіші), ніж послідовність цифр IP-адреси. Спершу перетворення між доменними іменами і IP-адресами виконувалося з використанням спеціального текстового файлу DHOSTS.TXT, який складався централізовано і обновлявся на кожному з вузлів мережі вручну. З ростом Мережі виникла потреба в автоматизованому механізмі, яким і став DNS.
DNS була розроблена Полом Мокапетрисом у 1983 році.
Доменне ім’я складається, як мінімум з двох частин (що зазвичай називаются мітками), розділених крапкою. Сама права міткає доменом верхнього рівня, кожна наступна справа наліво є піддоменом.
Система DNS містить в собі ієрархію серверів DNS.
Кожний домен чи піддомен підтримуєтся як мінімум одним авторизованим сервером DNS, на якому розташована інформація про домен. Ієрархія серверів DNS співпадає з ієрархією доменів.
Процес перетворення домнного імені в IP-адресу є різновидом ітеративного пошуку, коли DNS-клієнт по черзі опитує DNS-сервери, доки не доходить до авторизованого серверу шуканого домену.
Між іеменем хоста і IP-адресою немає тотожньої відповідності. Хост із одною IP-адресою може мати одразу декілька імен, що дозволяє розташовувати на одному комп’ютері низку web-сайтів. Обернене твердження теж вірне – одному імені може бути співставлено декілька хостів. Це використовується для балансування навантаження.
Для пришвидшення роботи DNS запитів використовується DNS cache.
DNS може виконувати і протилежну функцію до перетворення доменних імен у IP-адреси. Для цього використовуються вже існуючі засоби DNS. Справа в тому, що у DNS можуть бути співставлені різноманітні дані, в тому числі і символьні імена.
Існує спеціальний домен in-addr.arpa, записи в якому використовуються для перетворення IP-адрес у символьні імена.

16. Система електронної пошти глобальної системи INTERNETЕлектронна пошта (e-mail) – метод «постійної комунікації», що полягає у написанні, передачі, збріганні та отриманню повідомлень через електронні системи зв’язку. Термін «електронна пошта» відносится як до поштової системи мережі Інтернет, що базується на використанні протоколу SMTP, так і до поштових систем в локальних мережах, що дозволяють користувачам в межах однієї організації обмінюватися електронними повідомленнями. Система електронної поши була попередником Інтернету. Саме існуючи на той момент поштові системи були одном із основним засобів створення Інтернету.
Для написання повідомлень електронної пошти використовються поштові посередники користувачів (mail user agent, MUA). MUA форматує повідомлення у формі поштових повідомлень Інтернету (Interenet e-mail format) і використовує Simple Mail Transfer Protocol (SMTP) для передачі повідомлення на локальний поштовий трансферний агент (mail transfer agent. MTA). MTA аналізує адресу отримувача, знаходить IP-адресу його MTA використовуючи систему DNS, та надсилає повідомлення до відповідного MTA використовуючи знову таки протокол SMTP. MUA адресата отримує повідомлення з свого поштового сервера використовуючи протокол POP3 (Post Office Protocol).
Основна особливість електронної пошти полягає у тому, що інформація адресату відправляється не напряму, а через проміжну ланку – електронну поштову скриньку, який являє собою дисковий простір на сервері, де повідомленнязберігється до запиту адресата. У більшості випадків для доступу до поштового серверу вимагається наявність паролю. Доступ до поштового серверу може надаватися як через MUA, так і через web-інтерфейс. Користувачі отриують повідомлення зі своїх поштових серверів використовуючи протоколи POP та IMAP, або, що характерно для великих організацій, використовуючи власні протоколи систем IBM Lotus Notes та Microsoft Exchange.
Отримане повідомлення може зберігатися на клієнті, на сервері або на обох одночасно. Якщо повідомлення не може бути доставлено, MTA, що отримав дане повідомлення, має надіслати відправнику сповіщення про статус передачі, що містить в собі опис помилки.

17. Поняття універсального вказівника ресурсу. Основні типи ресурсівUniform Resource Identifier — единообразный идентификатор ресурса. URI — это короткая строка, позволяющая идентифицировать какой-либо ресурс: документ, изображение, файл, службу, ящик электронной почты и т. д.
Структура URI <схема>:<идентификатор-в-зависимости-от-схемы>
схема — схема обращения к ресурсу, например http, ftp, mailto, urn.
идентификатор-в-зависимости-от-схемы — непосредственный идентификатор ресурса, вид которого зависит от выбранной схемы обращения к ресурсу.
Примеры URI — это URL, URN.
Uniform Resource Locator (URL)— это стандартизированный способ записи адреса ресурса в сети Интернет. Для доступа к объектам используются различные схемы (протоколы).
Структура URL<схема>://<логин>:<пароль>@<хост>:<порт>/<URL-путь>
В этой записи:
схема — схема обращения к ресурсу, в большинстве случаев имеется в виду сетевой протокол;
хост — полностью прописанное доменное имя хоста в системе DNS или IP-адрес хоста в форме четырёх десятичных чисел, разделённых точками;
URL-путь — уточняющая информация о месте нахождения ресурса (зависит от протокола) Общепринятые схемы (протоколы).
URL включают:
ftp — Протокол передачи файлов FTP;
http — Протокол передачи гипертекста http;
mailto — Адрес электронной почты news — Новости Usenet;
telnet — Ссылка на интерактивную сессию Telnet file — Имя локального файла;
data — Непосредственные данные (Data: URL);
mailserver — Доступ к данным с почтовых серверов;
skype — Адрес Skype.
Uniform Resource Name (URN) — единообразное имя ресурса. URN — это постоянная последовательность символов, идентифицирующая абстрактный или физический ресурс. Имена URN призваны в будущем заменить локаторы URL.
Но имена URN, в отличие от URL, не включают в себя указания на место нахождения и способ обращения к ресурсу. Стандарт URN специально разработан так, чтобы он мог включать в себя другие пространства имён.
Структура URN<URN> ::= "urn:" <NID> ":" <NSS>
<NID> — идентификатор пространства имён (Namespace Identifier), представляет собой синтактическую интерпретацию NSS; не чувствителен к регистру.
<NSS> — строка из определённого пространства имён (Namespace Specific String); если в этой строке содержатся символы не из набора ASCII, то они должны быть закодированы в Юникоде и предварены (каждый из них) знаком процента «%».
Пример:URN книги, идентифицируемой номером ISBN:urn:isbn:5170224575

18. Поняття раутінгу в мережах TCP/IPМаршрутизация (Routing) — процесс определения маршрута следования информации в сетях связи. Задача маршрутизации решается на основе анализа таблиц маршрутизации, размещенных во всех маршрутизаторах и конечных узлах сети.
Одношаговые алгоритмы в зависимости от способа формирования таблиц маршрутизации делятся на три класса:
алгоритмы статической маршрутизации (статические таблицы маршрутизации);
алгоритмы простой маршрутизации;
алгоритмы адаптивной (или динамической) маршрутизации.
Для алгоритмов статической маршрутизации различают одномаршрутные таблицы, в которых для каждого адресата задан один путь, и многомаршрутные таблицы, определяющие несколько альтернативных путей для каждого адресата. В многомаршрутных таблицах должно быть задано правило выбора одного из маршрутов.
В алгоритмах простой маршрутизации таблица маршрутизации либо вовсе не используется, либо строится без участия протоколов маршрутизации.
Выделяют три типа простой маршрутизации:
случайная маршрутизация, когда прибывший пакет посылается в первом попавшем случайном направлении, кроме исходного;
лавинная маршрутизация, когда пакет широковещательно посылается по всем возможным направлениям, кроме исходного;
маршрутизация по предыдущему опыту, когда выбор маршрута осуществляется по таблице, но таблица строится по принципу моста путем анализа адресных полей пакетов, появляющихся на входных портах.
Самыми распространенными являются алгоритмы динамической маршрутизации. Эти алгоритмы обеспечивают автоматическое обновление таблиц маршрутизации после изменения конфигурации сети. В таблицах маршрутизации при адаптивной маршрутизации обычно имеется информация об интервале времени, в течение которого данный маршрут будет оставаться действительным. Это время называют временем жизни маршрута (Time To Live, TTL).
Адаптивные алгоритмы маршрутизации должны обеспечивать рациональность маршрута. Во-вторых, алгоритмы должны быть достаточно простыми, чтобы при их реализации не тратилось слишком много сетевых ресурсов, должны всегда приводить к однозначному результату за приемлемое время.
Адаптивные протоколы обмена маршрутной информацией:
дистанционно-векторные алгоритмы (Distance Vector Algorithms, DVA);
алгоритмы состояния связей (Link State Algorithms, LSA).
В алгоритмах дистанционно-векторного типа каждый маршрутизатор периодически и широковещательно рассылает по сети вектор, компонентами которого являются расстояния от данного маршрутизатора до всех известных ему сетей. Под расстоянием обычно понимается число промежуточных маршрутов. При получении вектора от соседа маршрутизатор наращивает расстояния до указанных в векторе сетей на расстояние до данного соседа. Получив вектор от соседнего маршрутизатора, каждый маршрутизатор добавляет к нему информацию об известных ему других сетях, о которых он узнал непосредственно или из аналогичных объявлений других маршрутизаторов, а затем снова рассылает новое значение вектора по сети. В конце концов, каждый маршрутизатор узнает информацию обо всех имеющихся в интерсети сетях и о расстоянии до них через соседние маршрутизаторы.
Дистанционно-векторные алгоритмы хорошо работают только в небольших сетях. В больших сетях они засоряют линии связи интенсивным широковещательным трафиком.
Наиболее распространенным протоколом, основанным на дистанционно-векторном алгоритме, является протокол RIP IP.
Алгоритмы состояния связей обеспечивают каждый маршрутизатор информацией, достаточной для построения точного графа связей сети.
Вершинами графа являются как маршрутизаторы, так и объединяемые ими сети.
Чтобы понять, в каком состоянии находятся линии связи, подключенные к его портам, маршрутизатор периодически обменивается короткими пакетами HELLO со своими ближайшими соседями. Этот служебный трафик также засоряет сеть, но не в такой степени как, например, RIP-пакеты, так как пакеты HELLO имеют намного меньший объем.

19. Технології, що забезпечують відмовостійкість мереж TCP/IPЗазвичай для забезпечення надлишкової маршрутизації IP використовуються дублюючі маршрутизатори та додаткові з'єднання. Надлишкова маршрутизація забезпечується розробленими IETF (Internet Engineering Task Force, група технічного розвитку Internet) протоколами FIRP (Fault Isolation and Recovery Protocol, протокол виявлення несправностей і відновлення), IRDP (Internet Router Discovery Protocol, протокол виявлення маршрутизаторів Internet), VRRP (Virtual Router Redundancy Protocol, протокол надлишкових віртуальних маршрутизаторів) і BGP (Border Gateway Protocol, протокол прикордонного міжмережевого шлюзу). Протоколи FIRP, IRDP і VRRP дозволяють будувати схеми з надлишковими локальними, а BGP - з надлишковими міжмережевим маршрутизаторами.
А если более детально...
Множинні шлюзи
Для забезпечення відмовостійкості необхідно включити в кожну підмережу ще один або декілька дублюючих шлюзів за замовчуванням (іншими словами, комп'ютери в підмережі повинні мати можливість виявити шлюз за замовчуванням). При відмові основного маршрутизатора комп'ютер повинен переключатися на резервний. Механізм виявлення непрацюючого шлюзу і переключитися на інший шлюз визначено в документі RFC 816.
Множинні шлюзи дозволяють рівномірно розподілити навантаження на маршрутизатори. Так, якщо в підмережі є два маршрутизатора Router Router 1 і 2, то для половини комп'ютерів в підмережі можна вказати перші Router 1, а для іншої половини - Router 2.
Виявлення маршрутизаторів
У разі налаштування кількох шлюзів за замовчуванням необхідно використовувати на обслуговуваних комп'ютерах узгоджені установки для шлюзів за умовчанням або діапазонів DHCP. Можна дотримуватися іншого підходу, із застосуванням протоколу IRDP, який дозволяє маршрутизатора повідомляти про те, що він доступний. Комп'ютер може динамічно виявити найбільш відповідний шлюз з доступних в підмережі та автоматично перейти на нього при відмові поточного. Опис протоколу IRDP можна знайти в RFC 1256.
Підтримуючий IRDP маршрутизатор із заданою періодичністю інформує комп'ютери своєї підмережі про послуги. Темники, повідомлення, яке містить адресу інтерфейсу маршрутизатора, рівень вподобання і час життя (скільки можна буде використовувати даний маршрутизатор в якості шлюзу за замовчуванням). Підтримуючий IRDP комп'ютер самостійно вибирає шлюзом за замовчуванням маршрутизатор з найменшим значенням номера переваги (менші значення цього параметра відповідають більш високому рівню переваги).
Віртуальні маршрутизатори
Протокол VRRP, запропонований в RFC 2338, забезпечує більш ефективний спосіб організації надлишкових шлюзів за замовчуванням, не вимагаючи при цьому індивідуального переналаштування всіх комп'ютерів підмережі.
Як випливає з назви протоколу VRRP, надмірність досягається шляхом організації віртуального маршрутизатора. Такий маршрутизатор має віртуальний код VRID (virtual router ID) і віртуальну адресу VRIP (virtual routerIP). Фізично віртуальний маршрутизатор складається з двох або більше маршрутизаторів: головного або активного (master) і декількох резервних (backup). Головний маршрутизатор забезпечує основні функції маршрутизації для вказаної адреси VRIP. Резервні маршрутизатори відстежують стан головного маршрутизатора і починають працювати в разі його відмови. Головний маршрутизатор періодично розсилає резервним повідомлення про те, що він доступний.
BGP
Часто протоколи маршрутизації використовуються для обміну інформацією про маршрути і динамічного оновлення таблиць маршрутизації при змінах топології мережі. Мережа, що належить одному адміністративному домену, наприклад intranet, називається автономною системою (AS, autonomous system). Діючий AS протокол маршрутизації називається внутрішнім протоколом маршрутизації. Широко застосовуються такі протоколи як Routing Information Protocol (RIP) і Open Shortest Path First (OSPF). Різні AS зазвичай використовують також зовнішній протокол (званий інакше междоменним протоколом маршрутизації) для обміну інформацією про маршрути. У Internet у якості зовнішнього протоколу маршрутизації прийнятий BGP, опис якого можна знайти в RFC 1771. Для роботи в Internet за протоколом BGP кожна автономна система повинна мати унікальний ідентифікатор (розподіляється InterNIC)
Після того, як два прикордонних маршрутизатора встановили з'єднання TCP, вони починають використовувати BGP-повідомлення про оновлення для обміну та поширення інформації про маршрутизації. Маршрутизатори BGP надсилають інформацію про маршрутизації BGP в автономні системи, доступні їм і сусідніх маршрутизаторів. Ця інформація містить відомості про Internet-маршрутах, які маршрутизатори отримали від зовнішніх маршрутизаторів, і Intranet маршрутах, отриманих з протоколів внутрішньої маршрутизації або з параметрів статичної маршрутизації.
Багатодімність
Найпростішим варіантом підключення до Internet є підключення локальної мережі до одного провайдера. Для організації надмірності необхідно створити багатодімну конфігурацію - налаштувати кілька з'єднань через одного або декількох провайдерів. Розрізняють варіанти підключення через одного провайдера і через різних провайдерів.
При підключенні через одного провайдера знову ж таки є два варіанти: підключення єдиного маршрутизатора до двох і більше маршрутизаторам провайдера в різних POP (Point of Presence, точка присутності). Інший варіант підключення двох і більше маршрутизаторів до різних POP. Хоча перший варіант і забезпечує надмірність підключення, єдиний маршрутизатор є потенційним слабкою ланкою.

20. Класифікація комп’ютерних мереж.По размеру, охваченной территории:
Локальные сети (LAN, Local Area Network)
Городская сеть (MAN, Metropolitan Area Network) охватывает несколько зданий в пределах одного города либо город целиком.
Глобальные вычислительные сети (WAN, Wide Area Network) представляет собой компьютерную сеть, охватывающую большие территории и включающую в себя десятки и сотни тысяч компьютеров.
Персональная сеть (PAN, Personal Area Network) это сеть, построенная «вокруг» человека. Данные сети призваны объединять все персональные электронные устройства пользователя (телефоны, карманные персональные компьютеры, смартфоны, ноутбуки, гарнитуры и.т.п.).
По типу функционального взаимодействия:
Клиент-сервер — сетевая архитектура, в которой устройства являются либо клиентами, либо серверами. Сеть с выделенным сервером — это локальная вычислительная сеть (LAN), в которой сетевые устройства централизованы и управляются одним или несколькими серверами. Индивидуальные рабочие станции или клиенты (такие, как ПК) должны обращаться к ресурсам сети через сервер(ы).
Точка-точка, P2P — простейший вид компьютерной сети, при котором два компьютера соединяются между собой напрямую через коммуникационное оборудование. Достоинством такого вида соединения является простота и дешевизна, недостатком — соединить таким образом можно только 2 компьютера и не больше.
Одноранговая — это компьютерные сети, основанные на равноправии участников. В таких сетях отсутствуют выделенные серверы, а каждый узел является как клиентом, так и сервером. В отличие от архитектуры клиент-сервер, такая организация позволяет сохранять работоспособность сети при любом количестве и любом сочетании доступных узлов. Любой член токой сети не гарантирует никому своего присутствия на постоянной основе. Он может появляться и исчезать в любой момент времени. Но при достижении определённого критического размера сети наступает такой момент, что в сети одновременно существует множество серверов с одинаковыми функциями.
По типу сетевой топологии: Шина, Звезда, Кольцо, Смешанная топология, Полносвязная топология.
По функциональному назначению:
Сети хранения данных — сеть, предназначенная для подсоединения устройств хранения информации (например, массивов жёстких дисков или библиотек магнитных лент) к серверам. Сеть хранения данных состоит из: коммуникационной инфраструктуры, которая обеспечивает физическую связь между элементами сети хранения данных; системы управления сети хранения данных; устройств хранения информации; серверов.
Сети SOHO (Small Office, Home Office) — локальная компьютерная сеть. Сеть обычно представленна одним кабинетом или комнатой. В сети используется сетевые коммутаторы Ethernet или повторители и кабель 5-той категории, или беспроводная сеть Wi-Fi. Такая сеть позволяет использовать ресурсы всех компьютеров для передачи/хранения данных, а так же получать доступ в сеть Интернет через один из компьютеров или сетевой шлюз. В сети SOHO можно использовать сервер для контроля доступа к сети, общего хранилища данных, а так же разделять права пользователей.

4. Теорія програмування та обчислень1. Основні аспекти програмІнтуїтивне поняття програми хоча і нестроге, але настільки ясне, що практично не було випадків, коли спеціалісти розійшлися б у поглядах відносно того, чи є програмою те чи інше конкретне завдання процесу. За визначенням Даля програма – це нарис, інтрукція певного процесу. Як кожне фундаментальне поняття програма може розглядатия з різних точок зору, перш за все
Синтакичний аcпект
Семантичний аcпект
Прагматичний аcпект
Серйозно просунуті дослідження двох з них: семантики та синтаксису.
Принцип підпорядкованоті : Прагматика > Семантика>Синтаксис.
Дійсно, програми ми повинні розглядати в першу чергу з прагматичної точки зору, це як правило і відбувається в дійності (оскільки перед тим як почати створювати програму ми визначаємо нащо вона потрібна). Наступний крок - семантика, по ній будується синтаксис і в цілому інтегрована семантико-синтаксична структура. Зрозуміло, що цей підхід, безперечно, більш перспективний порівнюючи з синтаксико-семантичним підходом. Тому сучасне програмування, тим більше майбутнє програмування повинно базуватись на цьому підході . Але зараз панує синтаксисо-семантичний підхід (Сучасні заоби програмування дозволяють нам використовувати синтаксичні контрукції, а не оперувати семантикою, перевірити заздалегідь можна синтаксис, але не існує верифікаторів семантики програм).

2. Основні поняття програмуванняНайважливішим чинником (частиною всезагального) є поняття користувача (його елементи суть конкретні користувачі). Користувачі мають проблеми, для розв’язку яких використовують програми. Виникає головна тріада програмування:
користувач (теза) – проблема (антитеза) – програма (синтез).
Ці поняття пов’язані наступними відношеннями:
актуальність – адекватність – прагматичність.
Головна тріада занадто загальна. Треба ввести додатково специфічні (якісні) характеристики. словники тлумачать програму як запис дій (які виконуються). Звідси випливає, що можемо зробити ще один оберт, ввівши процес виконання (обчислення) програми. Отримуємо нову тріаду:
користувач – програма – процес виконання (обчислення).
Ця тріада вводить нові відношення: обчислюваність (програм) та інтерфейс (між користувачем та процесом обчислення).
Нарешті, слід ввести ще одну тріаду – тріаду процесу програмування:
проблема – програма – процес програмування
Нові відношення в цій тріаді наступні: проблемна орієнтованість (процесу програмування на проблему) та генетичність (програми) і експлікативність (процесу).

3. Методи подання синтаксису мов програмуванняПрименяют форму Наура-Бэкуса (ФНБ), которая предполагает использование в качестве нетерминальных символов комбинаций слов естественного языка, заключенных в угловые скобки, а в качестве разделителя знак, состоящего из двух двоеточий и равенства.
Чтобы сократить описание схемы грамматики, в ФБН разрешается объединять правила c одинаковой левой частью в одно правило, правая часть должна включать правые части объединяемых правил, разделенные вертикальной чертой. <список>::=<элемент списка><список>|<элемент списка>.
Для получения более компактных описаний синтаксиса применяют итерационную форму описания. Такая форма предполагает введение специальной операции. Итерация вида {a}*. Например, описание множества цепочек, каждая из которых должна начинаться знаком # и может состоять из произвольного числа букв x и y, может быть представлено <I> ® #{x | y}* .



4. Класифікація породжувальних граматикПусть дана грамматика G = (N, T, P, S). Тогда если правила грамматики не удовлетворяют никаким ограничениям, то ее называют грамматикой типа 0, или грамматикой без ограничений.
Если каждое правило грамматики, кроме S e, имеет вид , где ||||, и в том случае, когда S e P, символ S не встречается в правых частях правил,то грамматику называют грамматикой типа 1, или неукорачивающей.
Если каждое правило грамматики имеет вид A , где A N, (N T)*, то ее называют грамматикой типа 2, или контекстно-свободной (КС-грамматикой).
Если каждое правило грамматики имеет вид либо A xB, либо A x, где A, B N, x T* то ее называют грамматикой типа 3, или праволинейной.
Язык типа 1 - контекстно-зависимым (КЗ), язык типа 2 - контекстно-свободным (КС), язык типа 3 - праволинейным.
K3 K2 K1 K0.
Грамматика G называется неоднозначной, если существует цепочка w, для которой имеется два или более различных деревьев вывода в G.
Грамматика G называется леворекурсивной, если в ней имеется нетерминал A такой, что существует вывод A→Aw для некоторой цепочки w.
Атрибутной грамматикой называется четверка AG = (G, AS, AI, R), где
G = (N, T, P, S) - приведенная КС-грамматика;
AS - конечное множество синтезируемых атрибутов;
AI - конечное множество наследуемых атрибутов, AS AI = ;
R - конечное множество семантических правил.
Атрибутная грамматика AG сопоставляет каждому символу X из N  T множество AS(X) синтезируемых атрибутов и множество AI(X) наследуемых атрибутов.

5. Автоматна характеристика основних класів мовПочнемо з більш простого класу мов – мов регулярних.
Під автоматом розуміється п’ятірка <K,X,,q,F>, де
K - множина станів,
X - множина вхідних станів,
- функція переходів,
qK - початковий стан,
F – множина заключних станів.
Основним поняттям, на основі якого дається характеристика класів мов, є зображення мови L в автоматі A. Для того, щоб строго ввести це поняття, продовжимо функцію на множину KF(X), де F(X) – напівгрупа, що породжена X з одиницею . Продовження задається індуктивно.При цій домов-леності визначається так:
(k, )=k,kK (тобто кожний стан переводиться пустим словом сам в себе)
(k,px),pF(X),xX =>(k,px)=((k,p),x) (тобто продовження ф-ції досить природнє.)
Будемо говорити, що мова L зображається в автоматі А <=> L={p|(q,p)F}. Автоматну характеристику класу регулярних мов дає наступна теорема:
Теорема. Мова L є регулярною <=> вона зображається в скінченому автоматі.
По аналогії з aвт. хар-кою регулярних мов, базується АХ трьох інших класів мов. Зокрема, для КВ-мов роль автоматів виконують автомати з магазинною пам’яттю, для БС-мов – лінійно-обмежені автомати, і нарешті, рекурсивно-злічені мови (як вже відомо) – машинами Тюрінга.


6. Метод нерухомої точкиВідомо, що функція f:A->A має нерухому точку aA, якщо f(a)=A. Проблема мати чи не мати нерухому точку, звичайно, суттєво залежить від класу функцій, з яких вибирається f. Як правило, в основу цих властивостей вкладаються властивості, що базуються на неперервності.
Але ці властивоссті безпосередньо не можуть бути перенесені на клас програмних функцій. Спряжено це в першу чергу з тим, що топології, що використовуються у традиційних галузях є неадекватними в класі програмних функцій. Точніше кажучи, границі, що зберігаються класичними функціями, що робить їх неперервними, не відповідають навіть основним властивостям поняття програми, на приклад, не узгоджується з властивістю дискретністі програм. В зв’язку з цим виникає важлива проблема: чи можна адекватно ввести топологію, зокрема поняття границі, стосовно яких програмні функції зберігали границю.Відповідь так. Це дає підстави для наступної теореми:
Теорема. Програмні функції мають нерухому точку. В доведенні теореми нерухома точка будується конструктивно.



Застосування теорії нерухомої точки:





7. Методи формальної семантикиВ реальних МП, в кращому випадку лише синтаксис задається строго формально, а семантика задається лише інтуїтивно, Тому з кожною мовою реального програмування спражена важлива проблема – формалізація її семантики. Задання семантики в кожному випадку спряжене з подоланням серйозних труднощів. Як бачили, навіть для такої “ювелірної” мови як λ-нотація було спряжене з подоланням принципової проблематики. Дійсно, так операція Ap,задана на впорядкованій парі (a,f), де a та f мають різний тип, семантика зпряжена з розв’язком проблеми самопримінення – примінення функції f до самої себе. В реальних МП ця проблема суттєво ускладнюється. Навіть в λ-численні ця проблема стояла відкритою більше 50-ти років. Теорія Скотта створила фундамент для розв’язку проблеми формалізації λ-нотації. В основі цієї формалізації лежить інтегрована структура програмування. Дійсно, задати формально семантику λ-нотації = задати семантику терму Ap(a,f) та терму x.t(x). Що стосується терму Ap(a,f), то він інтерпритується в семантичних структурах. Конкретніше, він інтерпритується як функція (а це поняття семантичне), що задана на парі (a,f), один з компонентів якої є знову функція (семантичне поняття) та об’єкт a (яке знову ж є теоретико-множинним елементом, а не символом – а це семантика). Звідси випливає, що інтерпритація a задається в термінах лише семантичних понять.
Розглянемо тепер другий терм - x.t(x).. Перш за все, відзначимо, що використовуючи співвідношення Шенфінкеля, що зіставляє кожній функції f(x,y) нову функцію (y)=fx(y), що параметризована x-ом, ми зводимо інтерпритацію подібних термів до інтерпритації унарних функцій. Але ж, як бачимо, на відміну від семантики Ap(a,f), ми приречені поряд з суто семантичними поняттями використовувати синтаксичні поняття (типові вирази t(x) з вільно змінною x). В зв’язку з цим семантика вказаних виразів (тобто функція, що йому відповідає) задається шляхом стандартної інтерпритації терму t(x) на елементах з області значень змінної x, яка пробігає її. Таким чином, на відміну від аплікації, λ-абстракція інтерпретується шляхом від синтаксису до семантики. Таким чином, формалізація семантики λ-нотації є дійсно змішаною.

8. Формальні методи програмуванняФормальні методі (англ. Formal methods) — в комп'ютерних науках, основані на математиці методи написання специфікацій, розробки та верифікації (перевірки) програмного забезпечення (ПЗ) та комп'ютерного обладнання. Цей підхід особливо важливий для вбудованих систем, для яких важливими є надійність або безпека, для захисту від появи помилок в процесі розробки. Застосування формальних методів особливо ефективно на ранніх етапах написання вимог та специфікацій, але, також, можуть використовуватись для повністю формальної розробки реалізації (наприклад, програми). Існують стандарти на критерії безпечності та захищенності программ. Частіше за все для реалізації валідації ПЗ використовуються теорія скінчених автоматів.
Формальні методи можуть бути застосовані на декількох рівнях:
Рівень 0
Написання формальної специфікації та неформалізована розробка, на її основі, ПЗ. Такий підхід, також, має назву спрощені формальні методи. Він може бути найоптимальнішим, з точки зору витрат, підходом у багатьох випадках.
Рівень 1
Формальний підхід до розробки програмного забезпечення та перевірки може використовуватись для формальнішої реалізації програми. Наприклад, може виконуватись доведення властивостей або уточнення (англ. refinement) із формальної специфікації в програмі. Такий підхід найоптимальніший у вбудованих системах, які повинні мати високий рівень безпеки або надійності.
Рівень 2
Можливе застосування систем автоматичного доведення теорем для проведення повністю автоматизованої перевірки доведення теорем. Це може бути занадто дорого, і, на практиці, застосовується у випадках, коли ціна помилок може бути зависокою (наприклад, в критично важливих частинах схеми мікропроцесорів).
Відомі формальні методи: Event-B, Z-notation, ASM, RAISE, SLAM, Мережі Петрі та ін.

9. Функції складності (сигналізуючі) за часом та за пам’яттю. Теорема про прискорення.В теорії складності обчислень розглядаються обчислювальні задачі чи задачі розпізнавання (аналізу) і досліджуються питання складності розв’язку цих задач на відповідних обчислювальних пристроях. Основний інтерес представляє отримання оцінок складності задач по часу і по пам’яті. Відповідно при розгляді обчислень на машинах Тьюрінга вводяться поняття часової сигналізуючої і сигналізуючої по пам’яті.
Нехай A=(K ,Σ, A`, H, q0, q*)- машина Тьюрінга, що розпізнає мову L(A) , де L(A) Σ*. Вважається, що при довільному вхідному слові w є Σ* машина Тьюрінга A , розпочавши роботу в конфігурації q0w , зупиниться через скінченну кількість кроків (через tA(w) кроків) і при цьому вона використає lA(w) комірок робочої стрічки.
При цьому якщо вона зупиниться в кінцевому стані q* , то маємо, що w є Σ* , а в іншому випадку, маємо, що Σ ∉ w . Тепер визначимо для машини Тьюрінга A часову сигналізуючу TA(x) і сигналізуючи по пам’яті LA(x) .
Покладемо, що
TA(x)=max{tA(w)|wє Σ* , |w|<=x}
LA(x)=max{tA(w)|wє Σ* , |w|<=x}
Будемо говорити, що задача розпізнавання w є Σ* має верхню (часову) оцінку (в.о.) T(x) , якщо існує машина Тьюрінга A , що розпізнає мову L і TA(x) <= T(x)для всіх натуральних чисел x .
Будемо говорити, що задача розпізнавання w є Σ*має нижню (часову) оцінку (н.о.) T(x) , якщо доведено, що для довільної машини Тьюрінга A , що розпізнає мову L виконується співвідношення T (x) <= TA (x) для всіх натуральних чисел x .
Будемо говорити, що задача розпізнавання w є Σ* має оптимальну (часову) оцінку (о.о.) T(x) , якщо функція T(x) є одночасно н.о. і в.о. для цієї задачі.
Теорема про прискорення. Нехай деяка задача розв’язується на МТ A з часовою сигналізуючою TA (x), де TA (x) ≥ x2 . Нехай c - довільне натуральне число і c ≥ 2 . Тоді існує МТ B , яка розв’язує ту ж задачу з часовою сигналізуючою TB(x), де TB(x) <= 1/c TA(x) для майже всіх x .
Доведення. Ідея доведення полягає в укрупненні комірок.
Нижня квадратична оцінка тут важлива, бо на перебудову слова в алфавіті Σ потрібний квадратичний час, якщо Σ≥|2|.
Якщо ж вхідні і вихідні слова представлені в однобуквеному алфавіті, то в формулюванні теореми замість нижньої оцінки x2 можна взяти оцінку xlog x.

10. Функції, елементарні за КальмаромФункція f(х,у) отримується з функції g(х,у) за допомогою операції сумування, якщо для всіх х, у є N маємо .
Функція f(х,у) отримується з функції g(х,у) за допомогою операції мультиплікації, якщо для всіх х, у є N маємо .
Функція f(x1, ..., xn) елементарнa (елементарнa за Кальмаром), якщо вона може бути отримана з функцій s, I, + та ∸ за допомогою скінченної кількості застосувань операцій суперпозиції, сумування і мультиплікації.
Наступні співвідношення встановлюють елементарність відомих функцій:
1) о(x) = х∸х;
2) ;
3) (х) = s(о(х));
4) x∸1 = x∸1(x)
5) sg(x) = x∸ (х∸1);
6) nsg(x) = 1(х) ∸х;
8) mod(х, у) = х ∸ (у ∸ х / у])
9)C(x, y)=[((x+y)2 + 3*x+y)/2];
10) x! =x∏i=1 i
11) xy=y∏ i=1 I21(x,i).
Нехай f(х) отримана за допомогою операції кускового завдання з функцій g1(x), ..., gn(x) та допоміжних функцій α1(x), ..., αn(x): f(х) = g1(x)nsg(α1(x))+...+gn(x)nsg(αn(x)).
Тоді f(х) – елементарна функція, якщо функції gi(x), αi(x), де 1 i n, елементарні.
Нехай f(х) = μyα(x)(g(х, у)=0) отримана за допомогою операції обмеженої мінімізації. Тоді функцію f(х) можна задати у вигляді f(х)=h(х,α(x)), де .
Звідси f(х) елементарна функція, якщо функції g(х,у) та α(x) елементарні.
Кажуть, що функція f(х,у) отримується за допомогою операції обмеженої рекурсії з функцій g(х), h(х, у, z) та φ(х, у), якщо:
функція f(х, у) задається схемою примітивної рекурсії f(х, 0) = g(х),f(х, у) = h(х, у ∸ 1), f(х, у ∸1)),
для всіх х, уєN маємо f(х, у)φ (х, у).
Теорема. Нехай функція f(х, у) отримана за допомогою операції обмеженої рекурсії з функцій g(х), h(х, у, z) та φ(х, у), причому функції g(х), h(х,у,z) та φ(х,у) – елементарні. Тоді f(х, у) також елементарна.
Визначимо операцію обмеженої рекурсії в загальному випадку. Нагадаємо, що є скороченим позначенням послідовності x1, ..., xn
Скажемо, що функція f(, у) отримана за допомогою операції обмеженої рекурсії з функцій g(), h(, у, z) та φ(, у), якщо вона задана схемою примітивної рекурсії
f(, 0) = g(),f(, у) = h(,у ∸1), f(,у ∸1)),
причому для всіх єNn та уєN маємо f(, у) φ(, у).
Має місце природне узагальнення теореми 9.1.1.
Теорема. Нехай функція f(, у) отримана за допомогою операції обмеженої рекурсії з елементарних функцій g(), h(, у, z) та φ(, у). Тоді функція f(, у) також елементарна.

11. Співвідношення між класами примітивно рекурсивних та елементарних функційНехай , де носій El – клас елементарних функцій; – це операції.
Алфавіт:
Визначення операторного терму:
Усі символи базових функцій є операторними термами.
Якщо є операторними термами для завдання m-арних функцій, а є термом для задання n-арної функції, то терм є термом для позначення m-арної функції.
Якщо є операторним термом для бінарної функції, то терми є операторними термами для бінарних функцій.
Інших оператор них термів не існує.
Зрозуміло, що кожна елементарна функція є ПРФ. Доведемо зворотне твердження – що це включення строге.
Для цього розглянемо допоміжну функцію :
Функцію назвемо k-східчастою, якщо має місце умова: .
Теорема: Довільна елементарна функція є k-східчастою для певного відповідного значення k.
Доведення:
Базові функції:

так само для ;
.
Нехай є операторним термом для бінарної функції . Утворимо функції та (обидві вони бінарні). Нехай є -східчастою функцією. Тоді є -східчастими функціями.
Це випливає з двох нерівностей:


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

12. Техніка слідів. Лема про заміщення1859280379095Рассмотрим вычислит. процесс, обозначаемый M[P], который выполняет МТ М, запущенная в начальной конфигурации с исходным словом р. Пронумеруем границы между соседними ячейками так:
С каждой фиксированной границей j можно ассоциировать послед-сть внутренних состояний МТ след. образом: если в процессе М[P] головка ни разу не пересекает границу j, то эта последовательность пуста (не содержит никаких элементов). Пусть головка пересекает границу j ровно s раз: первый раз в состоянии q(1), 2-ой – в состоянии q(2) и т.д. Тогда последовательность q(1), q(2),…, q(s), являющаяся словом в алфавите Q внутренних состояний, называется следом процесса M[P] в точке j и обозначается следM(P, j). Это обозначение содержит указание на рассматриваемую машину М и на исходное слово Р. Однако в тех случаях, когда из контекста ясно, какая имеется в виду машина или слово, будем применять упрощенніе обозначения типа след(Р, j) или след(j). Если первое прохождение головки было слева направо, то второе будет справа налево и далее направление будет также чередоваться. Ясно, что при j>0 первое прохождение будет только слева направо, а при j0 – в противоположном направлении. Если процесс M[P] бесконечен, то может случиться, что в некоторых границах j след также будет бесконечен. Однако поскольку мы далее будем рассматривать только конечные процессы, заканчивающиеся выдачей результирующего слова R (зависящего от исходного слова P), то и следы будут конечными. Пусть |след(j)| обозначает длину следа в т. j, т. е. число пересечений границы j. Очевидно, что каждое пересечение головкой какой-либо границы связано с затратой 1 такта работы МТ. Поэтому справедливо нер-во: tM(P)|след(P, j)| (1), где суммирование берется по любому мн-ву границ. Строгое нер-во может возникнуть за счет того, что рассматривается лишь часть границ, пересекаемых головкой, а также по той причине, что на некоторых тактах головка не сдвигается с обозреваемой ячейки, а следовательно не совершается никаких пересечений. Иногда анализ процесса M[P] позволяет обнаружить, что в некоторых точках возникают достаточно длинные следы. В таких случаях нер-во (1) может послужить для установления нижней оценки сигнализирующей tM(P).
Лемма о замещениях.
Пусть есть МТ А=<K, Г, , Н, q0, q*> и разметки ленты 1 и 2. Пусть на разметке i возникает полное поведение qi, i=1,2 MT A.
Пусть теперь для некоторых i и j (i<j) верно S(i, q1)=S(j, q2). След S(i, qi) конечен, и если q1=(1, q1, i1), q2=(2, q2, i2), то (i1<i) & (i2<j) или (i1i) & (i2j). Тогда на разметке :
Возникает полное поведение q3 МТ А такое, что k
Доказательство будем вести индукцией по n – длине следа S=S(i, q1), n=|S|.
При n=0 в случае (i1<i) & (i2<j) имеем, что начиная с разметки 1 МТ не заходит правее (i-1)-ой ячейки, а тогда k i |S(k, q1)|=0. Аналогично, k j |S(k, q2)|=0, а тогда утверждение леммы тривиально. Случай (i1i) & (i2j) разбирается аналогично. Пусть мы доказали лемму для некоторого n. Докажем ее справедливость для n+1. Пусть (i1<i) & (i2<j). Поведение q1 и q2 можно представить в виде

Остаточные поведения и являются полными, и их следы на i- и j- разрезах соответственно совпадают и меют длину n, к тому же (i=i) & (j=j). Мы попадаем в условия леммы, а тогда на разметке возникает полное поведение МТ А такое, что k
Заметим, что .
Поведение q3 на разметке 3 можно представить в виде
получено из заменой разметки на такую
Имеем :
Что и требовалось доказать.
Случай (i1i) & (i2j) разбирается аналогично. По принципу мат. индукции лемма доказана.

13. Функції, обчислювані за реальний часНехай маємо строго зростаючу функцію - обчислювана за реальний час (RTF) якщо існує машина Тьюрінга А, що має скінчену кількість робочих стрічок, вихідну стрічку та за реальний час генерує (множина всіх значень функції f)
Той факт, що машина А генерує нескінченну послідовність αf за реальний час означає, що: в початковий момент часу МТ А має порожні робочі стрічки і порожню вихідну стрічку. Потім, на кожному такті роботи МТ А здійснює дії відносно робочих стрічок (зміна символу, що розглядається; зсуви робочих стрічок відносно керуючої голівки; зміна стану керуючої голівки) і друкує лише 1-ин символ на вихідну стрічку.
Функція називається обчислюваною за реальний час (за допомогою МТ А, що має n вхідних стрічок, скінченну кількість робочих і вих.), якщо для довільних натуральних чисел xi вона обчислює значення за кількість
Відносно класу RTF можна довести, що він замкнутий відносно операцій додавання, множення, віднімання (при певних обмеженнях), суперпозиції, піднесення до степеня і т.д.
Доведемо твердження про замкненість відносно операції сумування.
Теорема. Клас функцій, обчислюваних за реальний час, замкнутий відносно операції сумування. Тобто, якщо , то.
Доведення.
Нехай є машина Af , яка обчислює за реальний час функцію f . Побудуємо Aϕ , яка обчислює за реальний час функцію ϕ .
Етап 0. ϕ(0) = 0
Етап x . .
Машина Aϕ має 1-у додаткову робочу стрічку.
Там вже знаходиться блок довжиною f(x-1). Вказівник рухається по цьому блоку і робить f(x-1) кроків. Потім включається машина Af. Вона робить f(x)-f(x-1) кроків і паралельно добудовує блок довжиною f(x)-f(x-1).
Здійснюється всього f(x) кроків. На кожному кроці на виході машина Aϕ друкує “0”, і кінці “1”. Тоді в кінці етапу x в пам’яті буде знаходитись блок довжиною f(x).

5. Системи штучного інтелекту1. Знання. Класифікація знаньНа інтуїтивному рівні знання можна визначити як інформацію, на основі якої можна отримувати нову інформацію, тобто нові знання.
Визначення. Знаннями інтелектуальної системи називається трійка <F, R, P>, де F - сукупність фактів, що зберігаються в пам’яті системи в явному вигляді, R - сукупність правил, які дозволяють на основі існуючих фактів отримувати нові, P - сукупність процедур, які визначають, яким чином слід застосовувати правила.
Знання, доступні системі, складають базу знань цієї системи.
Розрізняють екстенсіональні та інтенсіональні представлення. Під екстенсіональним представленням мається на увазі просто набір фактів, або кортежів, що входять до бази даних. Інтенсіональне представлення - це задання правила, якому підпорядковуються записи у базі даних. Інтенсіональне відношення можна формально визначити як відношення R(A1, …, An ). Вважається, що до бази даних, що описується відношенням R , належать ті і тільки ті факти, які задовольняють йому. Якщо в чисто екстенсіональній базі даних всі факти необхідно зберігати в явному вигляді, то при наявності інтенсіональних представлень це не обов’язково. Нові факти можуть бути породжені відношенням R ,за його ж допомогою може бути перевірена істинність того чи іншого твердження.
Згідно з класифікацією Попова Е.З. , знання класифікуються за областями і за типами знань. Можна виділити такі області знань: проблемна область, область мови, область системи, область користувача, область діалогу. Чим більше в нас областей знань, тим більша можливість інтерпретації вхідних висловлень.
Типи знань бувають такі:
Базові елементи, об’єкти реального світу. Не потребують обговорення і додаються в нашу систему фактів в тому вигляді, в якому вони отримані.
Визначення та твердження. Вони ґрунтуються на базових елементах і очікуються бути достовірними.
Концепції. Являють собою перегрупування та узагальнення базових фактів.
Відношення. Можуть бути як властивостями базових елементів, так і відношення між концепціями. Прикладом відношень можуть бути скрипти.
Теореми та правила перезапису. Це частковий випадок породжуючих правил R з визначеними властивостями. Для використання теорем потрібні експертні правила їх використання. Наявність теорем визначає відмінність експертних систем та реляційних СУБД.
Алгоритми розв’язку. Вони потрібні для виконання певних задач. Визначають чітку послідовність обробки інформації на відміну від інших типів знань, в яких елементи інформації можуть використовуватися довільним чином.
Стратегії або евристика. Має зворотній до послідовності отримання порядок осмислення інформації. Наприклад, це можуть бути роздуми типу «Я хочу отримати такий результат, а тому мені треба зробити такі дії». Поява експертних систем пов’язана якраз з цією властивістю осмислення інформації людським мозком.
Метазнання. Являє собою сукупніть скоефіцієнтів довіри до існуючих знань.
Спосіб задання знань включає два аспекти: спосіб організації знань і модель задання. Вони різняться рівнями задання і рівнем детальності. За рівнями задання виділяють знання нулевого рівня (конкретні і абстрактні знання) і знання більш високих рівнів (метазнання). Перший рівень складають знання про задання знань нульового рівня. Число рівнів може бути продовжено.
Організація знань за рівнями детальності дозволяє розглядати знання з різним ступенем деталізації. Кількість рівнів деталізації залежить від специфіки задач вирішення, обсягу знань і способу їх задання. Традиційно виділяють три рівні: відображення загальної організації знань, логічна і фізична організація окремих структур знань.

2. Фреймова модель задання знаньТеорія фреймів (1975 р. М.Мінський). "фрейм" – англ. Frame ("рамка", "каркас"). Мінський: знання групуються в модулі, і назвав фреймами ці модулі. Інтуїтивно фрейм - каркас, на якому тримаються знання ( або рамка, на основі якої описуються різноманітні об’єкти та ситуації). Мінський: коли людина потрапляє в нову ситуацію, вона співставляє цю ситуацію з тими фреймами, які зберігаються у неї в пам’яті.
Фрейм - структура даних, що призначена для опису типових ситуацій або типових понять. М. Мінський визначав фрейм як мінімальний опис деякої сутності, такий, що подальше скорочення цього опису призводить до втрати цієї сутності.
E.g. Фрейм "Студента". Прізвище, ім’я та по-батькові, факультет, курс => представляються слотами. Опис = заповнення слотів конкретними значеннями. Екземпляри понять утворюються в результаті конкретизації фреймів понять.
Ієрархія понять. Фрейм "Студент" наслідує слоти від фрейму "Людина". Заповнені слоти можуть успадковуватися фреймами-нащадками.
Один і той самий предмет може описуватися різними фреймами, які відповідають різним умовам спостерігання цього предмета. Риси, спільні для цих різних фреймів, описуються базовим фреймом.
Фрейм може мати таку структуру:
1)Ім`я фрейму. Цей ідентифікатор є єдиним в даній фреймовій системі.
Кожний фрейм складається з довільного числа слотів (декілька з них системні, решта - користувача). Слоти: а) IS - A, що вказує на фрейм-предок даного фрейму; b) слот - вказівник фреймів нащадків, який є списком вказівників цих фреймів; с) слот для введення імені користувача, дати визначення, дати зміни, тексту коментаря; d) інші слоти.
Кожний слот в свою чергу задається фіксованою структурою даних.
2) Ім`я слоту - ідентифікатор, унікальний в фреймі. Деякі імена слотів мають смислове навантаження: а) IS - A(визначає тип відношення); b) DESENDANTS (вказівник прямого дочірнього фрейму); c) DEFINED BY (користувач, який визначає фрейм); d) DEFINEDON (дата визначення фрейму); e)MODIFIEDON (дата модіфікації фрейму); f)COMMENT - коментар; g)HAS_PART, RELATIONS - системні і використовуються при редагуванні бази знань і керуванні виведенням.
3)Вказівники наслідування використовуються тільки в фреймових системах ієрархічного типу, що грунтуються на відношеннях "IS - А". Вони вказують, яку інформацію про атрибути слотів фрейму вищого рівня наслідують слоти з таким же ім`ям в фреймі нижчого рівня.
4) Визначення типу даних - вказується, що слот має числове значення, або виступає вказівником іншого фрейму.
5)Значення слоту. Поле для введення значення слоту. Значення слоту повинно співпадати з вказанним типом даних цього слоту, і, крім того, повинна виконуватись умова наслідування.
6)Демон. Тут дається визначення демонів типу if-needed, if-аdded, if-removed. Демоном називається процедура, яка автоматично запускається при виконанні деякої умови. Демони запускаються при зверненні до відповідного слоту. Наприклад, демон if-needed запускається, якщо в момет звернення до слоту його значення не було встановленно, if-added - при підстановці значення в слот, if-removed - при стиранні значення слоту.
Спеціалізовані мови для представлення знань фреймами: KRL та ін. Часто фреймові моделі ще називаються об'єктними. Загальна форма об’єктного представлення визначається як: Об’єкт, (атрибут_j, значення_ j)( j = 1, … m). Об’єктна модель лягла в основу об'єктно-орієнтованих мов програмування, таких, як Smalltalk, C++, Delphi.
Зв’язок між семантичними мережами та фреймами: на сучасному етапі фреймові моделі та семантичні мережі розглядають, як правило, у спільному контексті: -> вузли семантичної мережі - як фрейми з власною внутрішньою структурою; <- можна вводити різноманітні зв’язки між слотами фреймів. Тоді фрейм набуває рис семантичної мережі.
3. Семантичні мережіМережні моделі базуються на семантичних мережах. Мережна модель:<I,C1 ,C2, ...,Cn ,Г>. I-множина інформаційних одиниць,C1,C2,...,Cn-типи зв’язків між інформаційними одиницями, Г-відображення, що задає зв’язки між інформаційними одиницями. Мережні моделі тісно пов’язані з моделями "сутність-зв’язок". Сутність - об’єкт довільної природи. П-сутність: об’єкт, що існує в реальному світі. Його представлення в базі знань -> М-сутність. У базі знань відображаються також зв’язки між сутностями.
Виділяють класифікуючі мережі, функціональні мережі та сценарії. Класифікуючі мережі дозволяють задавати відношення ієрархії між інформаційними одиницями. Функціональні мережі характеризуються наявністю функціональних відношень, які дозволяють описувати процедури обчислень одних інформаційних одиниць через інші. У сценаріях використовуються відношення типу "причина-наслідок", "дія", "засіб дії" та ін.
Семантична мережа - мережа, в якій поєднані зв’язки різних типів. Семантичну мережу можна неформально уявляти собі у вигляді графа, вершини якої, як правило, позначають об’єкти предметної області, а дуги відповідають зв’язкам між ними.
Базовим є поняття концептуального об’єкту (графічно зображається концептуальним графом). П-сутність описується концептуальним об’єктом, (до опису включаються клас, до якого належить П-сутність, властивості сутності та його прототип (або приклад)). Приклад - концептуальний граф для чайника:
Клас Об`ємна місткість
Чайник Властивість Металевий, фарфоровий,
з носиком
Приклад Металевий
У вигляді концептуального графа можна представляти будь-яку логічну формулу або словесне висловлювання. (Тоді концептуальний граф – проста семантична мережа, що відповідає одному твердженню). E.g. "Жак надсилає книгу Марі" => предикат ПОСИЛКА(ЖАК_2, МАРІ_4, КНИГА_22), а концептуальний граф матиме вигляд:
Цифри потрібні для того, щоб дати кожній сутності своє індивідуальне ім’я. Прямокутники концептуального графа - для представлення аргументів предикатів, а кола - для представлення самих предикатів. Круг і прямокутник з'єднуються дугою, якщо вони є відповідно ім'ям та аргументом того самого предиката. Часто буває корисним представити предикат, що відповідає деякій складній фразі природної мови, у вигляді кон'юнкції бінарних предикатів. Предикат ПОСИЛКА (ЖАК_2, МАРІ_4, КНИГА_22) можна переписати у вигляді: Відправник (Посилка_8, Жак_2); Отримувач (Посилка_8, Марі_4); Що (Посилка_8, Книга_22); IS_A (Посилка_8, Посилки). Предикат IS_A відіграє винятково важливу роль та означає належність деякої сутності до певного типу. Бінарне представлення називають представленням "об'єкт-атрибут-значення". "Об'єкт" є ім'ям бінарного предикату (або назвою сутності, що описується). "Атрибут" є назвою деякої ознаки, або властивості цього об'єкта. "Значення" відповідає конкретному значенню цієї властивості
Семантична мережа - це композиція концептуальних графів, об’єднаних за тими чи іншими правилами. Багато методів логічного виведення на семантичних мережах грунтуються на зв’язку IS_A та понятті наслідування, що тісно з ним пов’язане. Сутність наслідує атрибути типу, до якого вона належить. Якщо для типу визначені конкретні значення атрибутів, сутність, що належить до цього типу, наслідує їх за замовченням
Зв’язок PART-OF показує відношення "ціле - частина". Цей зв’язок показує відношення між екземплярами класу.
ластівка is-a птах
E.g. речення "всі ластівки - птахи". Cемантична мережа:
Ластівка - ім`я "Дана", тоді мережу можна розширити наступним чином:
дана is-a ластівка is-a птах
Тоді з семантичної мережі можна вивести речення: Дана - птах. Механізм наслідування НЕ завжди гарантує правильність висновку.
Приклад семантичної мережі:



4. Продукційна модель задання знаньУ продукційних моделях знання задаються за допомогою правил "якщо-то" (явище-реакція). Вони широко використовуться, бо для них характерні простота модифікації баз знань. З одного боку, їх правила виведення близькі до логічних моделей, з іншого - вони відображають знання у порівнянні з класичними логічними моделями, більш наочно.
Визначення. Продукційною моделлю називається представлення знань у вигляді сукупності продукцій. Продукція визначається в як вираз такого вигляду: (i) Q; P; A B; NТут (i) - ім'я продукції, за допомогою якого вона виділяється серед усієї множини продукцій; Q - сфера застосування продукції; предметна область, до якої вона відноситься; - умова застосування продукції; A B - ядро продукції; інтерпретація залежить від конкретної ситуації; часто ядро інтерпретується як "якщо маєш A, зроби B"; N - постумова продукції, постулює процедури, які необхідно виконати після реалізації ядра.
E.g.: МАГАЗИН; У ПОКУПЦЯ ГРОШІ; ЯКЩО ПОКУПЕЦЬ ХОЧЕ КУПИТИ РІЧ, ВІН ПЛАТИТЬ В КАСУ; ЗМІНИТИ БАЗУ ДАНИХ ПРО ТОВАРИ.
Інформаційні системи, побудовані на основі продукційних моделей, називаються продукційними системами(ПС). У ПС можна виділити базу фактичних знань, базу (набір) продукцій та систему керування продукціями. Остання визначає, в якій послідовності слід застосовувати продукції, щоб отримати потрібний результат. Особливо це стосується випадків, коли у деякій ситуації можна застосувати не одну, а декілька продукцій (вирішення конфліктів). Для керування застосовуються два загальні принципи: обмеження конфліктного набору та застосування алгоритмів вирішення конфлікту.
Відомі стратегії керування вирішенням конфліктів: принцип "стосу книг"; принцип найбільш довгої умови; принцип метапродукцій; принцип "класної дошки"; принцип пріоритетного вибору; принцип керування за іменами.
Компоненти ПС:
набір правил, які використовуються як база знань (база правил).
робоча пам`ять (де зберігаються умови, які відносяться до конкретних задач предметної області, і результати виведень, отриманих на їх основі).
механізм логічного виведення. Він використовує правила в відповідності до робочої пам`яті.
Дві основні стратегії логічного виведення у ПС:
для отримання заключення проводиться робота по вибору попередньо записаного вмісту робочої пам`яті, застосуванню правил і доповнень даних в пам`яті (прямим виведенням).
на основі фактів, які потребують підтвердження, щоб виступати в ролі заключення, досліджується можливість застосування правила, яке дає можливість підтвердження (зворотнім виведенням). У випадку застосування зворотнього виведення умова зупинки системи наступна: або досягається першочергова ціль, або закінчились правила, які застосовуються для досягнення цілі в ході виведення.
Вибір чергового правила впливає на ефективність виведення. Якщо на кожному етапі логічного виведення існує декілька правил застосування, тоді ця множина правил носить назву конфліктного набору, а вибір одного з них називають вирішенням конфлікту.
Для багатьох практичних застосувань продукційних систем недостатньо запису в робочу пам`ять тільки одного зразка і виникає потреба керувати даними, які уточнюють зміст. В таких випадках використовується спосіб задання конкретних даних з допомогою триплету: об`єкт - атрибут - значення. Тому кожна окрема субстанція із предметної області розглядається як один об`єкт. Можна вважати, що дані, які зберігаються в робочій пам`яті, показують значення, що приймають атрибути цього об`єкту. Наприклад, дані (студент1 ім`я Іван) описують той факт, що існує деякий студент і ім`я цього студенту Іван.
Випадок нечітких продукційних правил: В реальних системах продукцій іноді буває необхідним працювати з нечіткою інформацією. В таких випадках виділяють дві категорії нечіткості: а) нечіткість безпосередніх даних; б) нечіткість виведення.
Коли заключення виводиться за допомогою декількох правил, які включають в себе і нечіткі, виникає проблема визначення степені нечіткості всього заключення.
5. Розпізнавання образівВода на свой вкус (вступление)… Дальше… Базовий принцип: Будь-який об`єкт у природі - унікальний; унікальні об`єкти - типізовані. В природі не існує двох об’єктів, для яких співпадають абсолютно всі ознаки, і це теоретично дозволяє здійснювати ідентифікацію.
Опять Вода: поняття ознак, класифікація обєктів за ознаками, навчання, правила розпізнавання, навчальної вибірки, контрприкладу.
Задача розпізнання без учителя (кластерного аналізу). Класи попередньо не задаються; система повинна сама розділити відомі їй об’єкти на класи.
Зразок у розумінні "класу" визначається як деяка сукупність об’єктів, що мають спільні властивості, або певні спільні ознаки. Більш формально: об’єкти, для яких виконується відношення еквівалентності, або у крайньому разі відношення толерантності, у своїй сукупності складають образ.
Відношення еквівалентності = симетричності+рефлексивності+транзитивності. Відношення толерантності = симетричність+рефлексивність. Більш природним, ніж через відношення толерантності, видається визначення зразку (класу) у рамках теорії нечітких множин.
Системи розпізнавання: розробка системи розпізнавання та власне розпізнавання. 2) Власне розпізнавання - в три етапи: отримання первинної інформації; виділення ознак; класифікація. 1) Розробка системи розпізнавання: формування навчальної вибірки; вибір інформативної множини ознак; навчання.
Прості спеціалізовані методи розпізнавання: співставлення з еталоном, зондів, маркування, квазитопологічного розпізнання. Ці методи вимагають детального вивчення об’єктів, що розпізнаються. Навчання фактично відсутнє, і об’єкти, які розпізнаються, мало змінюються.
Два класи сучасних методів розпізнавання: 1) статистичні (дискримінантні) та 2) структурні (або синтаксичні, або лінгвістичні). Вибір методу розпізнавання істотно залежить від апріорної інформації про об’єкти, що розпізнаються.
1) Статистичні методи розпізнавання. Типова постановока задачі: Заданий певний набір класів K1, … , KM. Для кожного класу заданий деякий набір його представників. Потрібно для будь-якого об’єкту визначити, до якого класу він відноситься. Кожний об’єкт характеризується певним набором ознак, тобто відображається на деяку точку простору ознак. Цей набір ознак є фіксованим та спільним для всіх об’єктів.
Навчальній вибірці відповідає матриця даних Y=(yij; i =1,…,q; j = 1, … , n+1). Тут q - загальна кількість представників усіх класів, n - кількість ознак (розмірність простору ознак) yin+1 - клас, до якого відноситься i- й об’єкт. Будь - якому об’єктові відповідає вектор даних x = (x j; j = 1,…,n). При цьому природно визначити відстань у просторі ознак, яка являтиме собою мірило схожості об’єктів.
Статистичні методи явно або неявно спираються на гіпотезу компактності. Вважається, що класові відповідає компактна множина точок у деякому просторі ознак. Різні типи ознак: дихотомічні (ознака може бути присутня або відсутня; наприклад - є крила або немає крил); номінальні (наприклад, колір: червоний, синій, зелений і т.п.); порядкові (наприклад, "великий" - "середній" - "маленький"); кількісні. Метрики для кількісних ознак: евклідова відстань та зважена євклідова відстань. Для некількісних: відстані Хеммінга, Кендала, Юла, Рассела і Рао та ін.
"Первинні дані" можуть бути дуже різної природи. Обмежимося розпізнаванням неперервних сигналів та зображень. Типова схема розпізнавання таких об’єктів у загальних рисах відповідає раніше описаній схемі і включає до себе датчики, блок попередньої обробки, блок класифікатора і пам’ять. Первинні дані збираються за допомогою спеціалізованих датчиків. Стандартним прийомом є дискретизація, або цифрування.
Теорема Котельникова (теорема Шеннона, теорема відліків) (про частоту дискретизації): Нехай для функції u(t) визначене перетворення Фур’є, і спектр цієї функціїї неперервний та обмежений смугою частот від 0 до F. Тоді функція повністю визначається своїми дискретами, взятими через інтервали часу t =1 / (2F). Перетворення Фур’є U(f) функції u(t) визначається за формулою :
До класичних методів виділення ознак належать глобальні перетворення: лінійні або нелінійні. До таких перетворень відносяться перетворення Фур"є, Уолша, Хоара. Ознаки - спектральні коефіцієнти відповідних рядів => різке скорочення розмір. простору ознак ("стиск даних").
Попередньою обробкою є також зменшення шумів (фільтри Калмана, Вінера) Статистичні методи розпізнавання: а)імовірнісні та б)детерміністські.
а)Ймовірнісні методи. Матриця даних - набір реалізації деякого випадкового процесу. Класичним є байєсівській підхід. Iдея: мiнiмiзацiя ризику, пов’язаного з помилковим рiшенням. (Його можна розрахувати, якщо відомі умовні густини розподілу векторів ознак за умови, що об’єкт належить до певного класу.)
б)Детерміністський підхід: розподіл простору ознак на ділянки, які відповідають класам, відбувається на основі безпосереднього аналізу відстаней між об’єктами (точками цього простору). Класичним є правило найближчого сусіда. Об’єкт відноситься системою розпізнавання до того класу, до якого належить його найближчий сусід з навчальної вибірки.
2)Структурно-синтаксичні(лінгвістичні)методи розпізнавання розглядають структуру об’єктів та звязки між їх елементами. Декомпозиція здійснюється до атомарних елементів. Кожний клас описується деякою формальною мовою. Тоді набір атомарних елементів – це алфавіт цієї мови, а представники класу - це фразами, або речення цієї мови. Правила формування фраз з атомарних елементів складають граматику мови. Мова, породжена граматикою - це сукупність всіх ланцюгів, що складаються лише з основних символів на основі послідовного застосування правил граматики до початкового символа.
Типова система синтаксичного розпізнавання образів складається з трьох блоків: попередньої обробки; представлення об’єкта, метою якого є виділення атомарних елементів та відношень між ними; синтаксичного аналізу.
Основною задачею блоку представлення об’єкта є опис об’єкта деякою фразою, тобто деяким ланцюжком, що складається з атомарних елементів. Синтаксичний аналіз полягає у граматичному розборі фраз (зверху вниз та знизу вгору).
Традиційні граматики для утворення фраз використовують ланцюгову операцію конкатенації. Для опису складних зображень є більш складні граматики: графові граматики, мова опису зображень PDL, веб-граматики, плекс-граматики, ін.
Відомими є метод потенціальних функцій, метод групового урахування аргументів, метод припустимих перетворень, логічні методи розпізнавання. Останні традиційно відносяться до структурних методів. В їх основі лежить представлення відповіді про належність об’єкта до певного класу як логічної функції від його ознак. Ознаки при цьому є булевими. Класифікація при такому підході аналогічна логічному виведенню в експертних системах.

6. Поняття діалогової системи та її компонентиСистеми обробки природньої мови – СОПМ.
Спілкуванням – коммунікативна взаємодія.
Під діалогом будемо розуміти процес досягнення його учасниками, конкретних погоджених цілей, шляхом обміну зв`язаними висловеннями в деякій мові вибраної предметної області.
Мета діалога визначає структуру діалогу. Структура діалогу може розглядатись на трьох рівнях: глобальному, тематичному і локальному. Глобальний рівень визначає загальні властивості вирішуваних задач. Тематичний рівень визначається алгоритмом вирішення поставленої задачі і розподілом ролей між учасниками діалогу. На локальному рівні аналізуються конкретні пари “запит - відповідь”.
Узагальнена схема СОПМ
Серед обов`язкових функцій СОПМ можна виділити наступні:
з нової стрічки ведення діалогу - визначення його структури і ролі, яку виконує пара користувач - система на даному кроці діалогу;
розуміння - перетворення отримуваних від користувача висловлень на природній мові (ПМ) в висловлення мови внутрішнього задання;
обробка висловлень - формування і визначення завдань для вирішення задач і підзадач данного кроку діалогу;
генерація - формування вихідних висловлень природньою мовою.
До основних задач діалогового компонента (ДК) відносяться ведення діалогу і формування та обробка перехватів ініціатив. По структурі і поточному стану діалогу ДК формує (якщо ініціатива належить системі) або визначає (коли ініціатива належить користувачу) завдання, яке виконує система на поточному кроці: що це генерація питання, чи це розуміння відповіді і її формування і т.д.
Діалог може вестись або користувачем, або ж системою. Якщо ролі учасників спілкування визначаються під час спілкування, тоді структуру діалогу називають гнучкою.
Друга задача ДК заключається в обробці ситуації, коли реакція одного з учасників може не співпадати з очікуваннями іншого. Формування перехвату буває, коли система взнає, що поточна ситуація не відповідає ситуації передбаченої структурою діалогу. Якщо ж перехват ініціативи виконує користувач, тоді система повинна обробити його, розпізнати присутність ініціативи, визначити нову тему спілкування і перейти на структуру діалогу, яка відповідає новій темі.

7. Теорія ігор. Експліцитні та імпліцитні дерева гриТеорія ігор – це математична дисципліна, що вивчає питання поведінки учасників конфліктних ситуацій та має на меті виробити оптимальну для кожного з учасників стратегію такої поведінки. Конфліктною при цьому називають ситуацію, коли гравці мають різні цілі (різні функції виграшу) та можуть вибирати різні засоби досягнення своїх цілей (стратегії).
Залежно від кількості гравців розрізняють ігри двох та n гравців. Ігри трьох і більше гравців менше досліджені через принципові складності й технічні можливості отримання розв’язку.
За кількістю стратегій ігри поділяють на скінченні та нескінченні. Якщо у грі всі гравці мають скінченне число можливих стратегій, то її називають скінченною. Якщо ж хоча б один із гравців має необмежену кількість можливих стратегій, то гру називають нескінченною.
За характером взаємодії ігри поділяються на безкоаліційні (гравці не мають права вступати в угоди, утворювати коаліції) та коаліційні (кооперативні), з дозволом вступати в коаліції. У кооперативних іграх коаліції визначають заздалегідь.
За характером виграшу ігри класифікують так: ігри з нульовою сумою (загальний капітал усіх гравців не змінюється, а перерозподіляється між гравцями; сума виграшів усіх гравців дорівнює нулю) та ігри з ненульовою сумою.
За виглядом функцій виграшу ігри поділяють на матричні, біматричні, безупинні, опуклі, сепарабельні, типу дуелей та ін.
Матрична гра – це скінченна гра двох гравців із нульовою сумою, у якій задано виграш першого гравця у вигляді матриці (рядок матриці відповідає номеру застосованої стратегії першого гравця, стовпчик – номеру застосованої стратегії другого гравця; на перетині рядка і стовпця матриці – виграш першого гравця, що відповідає застосованим стратегіям). Для матричних ігор доведено, що будь-яка з них має рішення і його можна легко знайти шляхом зведення гри до задачі лінійного програмування.
Біматрична гра – це скінченна гра двох гравців із ненульовою сумою, у якій виграші кожного гравця можна задати матрицями окремо для відповідного гравця (у кожній матриці рядок відповідає стратегії першого гравця, стовпчик – стратегії другого гравця, на перетині рядка і стовпця в першій матриці знаходиться виграш першого гравця, у другій матриці – виграш другого гравця). Для біматричних ігор також розроблено теорію оптимальної поведінки гравців, однак пошук розв’язків для таких ігор складніший, ніж для звичайних матричних.
Неперервною вважають гру, в якій функція виграшів кожного гравця є неперервною, незалежно від стратегій. Доведено, що ігри цього класу мають розв’язки, однак практично не розроблено прийнятних методів їх знаходження.
Якщо функція виграшів є опуклою, то таку гру називають опуклою. Для таких ігор розроблено прийнятні методи рішення, суть яких у відшуканні чистої оптимальної стратегії (визначеного числа) для одного гравця та імовірностей застосування чистих оптимальних стратегій для іншого гравця. Таке завдання розв’язують порівняно легко.
Матричну гру двох гравців із нульовою сумою можна розглядати як наступну абстрактну гру двох гравців.
Перший гравець має m стратегій i = 1, 2, ..., m, другий – n стратегій j = 1, 2, ..., n. Кожній парі стратегій (i, j) поставлено у відповідність число аij, яке виражає виграш першого гравця за рахунок другого гравця, якщо кожен з гравців візьме свою стратегію.
Кожен із гравців робить один хід: перший гравець вибирає свою i-ту стратегію (), а другий – свою j-ту стратегію (), після чого перший одержує виграш аij за рахунок другого (якщо аij < 0, то це означає, що перший гравець винен другому суму |аij|). На цьому гру закінчують.
Кожну стратегію гравців ,  часто називають чистою стратегією.
Якщо розглянути матрицю
                               ,
то проведення кожної партії матричної гри за матрицею А зводиться до вибору першим гравцем i-го рядка, а другим – j-го стовпця й одержання першим гравцем  (за рахунок другого) виграшу аij.
Головним у дослідженні ігор є поняття оптимальних стратегій гравців. У це поняття інтуїтивно вкладають такий зміст: стратегія гравця є оптимальною, якщо застосування цієї стратегії забезпечує йому найбільший гарантований виграш за будь-яких стратегій іншого гравця. Враховуючи це, перший гравець досліджує матрицю виграшів А у такий спосіб: для кожного значення i () визначають мінімальне значення виграшу, залежно від стратегій другого гравця:
                                                    (),
тобто мінімальний виграш для першого гравця за умови, що він візьме свою i-ту чисту стратегію, далі із цих мінімальних виграшів відшукують таку стратегію i = iпро, за якої цей мінімальний виграш буде максимальним, тобто знаходять
                                             .                                          
Число , визначене за формулою (10.1), називають нижньою чистою ціною гри; воно показує, який мінімальний виграш може гарантувати собі перший гравець, застосовуючи свої чисті стратегії за будь-яких дій другого гравця.
Другий гравець за своєї оптимальної поведінки прагне завдяки своїм стратегіям максимально зменшити виграш першого гравця. Тому для другого гравця відшукують , тобто визначають найбільший можливий виграш першого, за умови, що другий гравець застосує свою j-ту чисту стратегію, а далі відшукає таку свою j = j1 стратегію, за якої перший гравець одержить мінімальний виграш, тобто знаходить
                                              .                                          
Число , обчислене за формулою (10.2), називають чистою верхньою ціною гри; воно показує, який максимальний виграш завдяки своїм стратегіям може собі гарантувати перший гравець.
Інакше кажучи, застосовуючи свої чисті стратегії, перший гравець може забезпечити собі виграш не менше , а другий гравець завдяки застосуванню своїх чистих стратегій може не допустити виграшу першого гравця більшого за .
Якщо в грі з матрицею А , то кажуть, що така гра має сідлову точку в чистих стратегіях та чисту ціну гри .
Пару чистих стратегій першого і другого гравців, що утворює сідлову точку і сідловий елемент, називають розв’язком гри.
Якщо ж у грі немає сідлової точки, тоді слід знайти нижню й верхню чисті ціни цієї гри, які вказують, що перший гравець не може сподіватись на виграш, більший за верхню ціну гри, і може бути впевненим в одержанні виграшу, не меншого за нижню ціну гри. Поліпшення рішень матричних ігор варто шукати у використанні таємності застосування чистих стратегій і можливості багатократного повторення ігор у вигляді партії. Цього результату досягають шляхом застосування чистих стратегій випадково, із визначеною ймовірністю.
Змішаною стратегією гравця називають повний набір імовірностей застосування його чистих стратегій.
Таким чином, якщо перший гравець має m чистих стратегій 1, 2, ..., m, то його змішана стратегія x – це набір чисел x = (x1, ..., xm), які задовольняють відношенню
                                         
Аналогічно для другого гравця, який має n чистих стратегій, змішана стратегія y – це набір чисел:
                         
Середній виграш першого гравця у матричній грі з матрицею А виражають у вигляді математичного очікування його виграшів:
                                    
Перший гравець має на меті за рахунок зміни своїх змішаних стратегій х максимально збільшити свій середній виграш Е(А, х, y), а другий – за рахунок своїх змішаних стратегій зробити Е(А, х, y) мінімальним, тобто для розв’язання гри необхідно знайти такі х і y, за яких досягають верхньої ціни гри:
                                             
Аналогічною має бути ситуація і для другого гравця, тобто нижня ціна гри є такою:
                                          
Подібно до ігор, які мають сідлові точки в чистих стратегіях, дамо визначення: оптимальними змішаними стратегіями першого і другого гравців називають такі набори хо, уо відповідно, які задовольняють рівності
              
Величину Е(А, хо, уо) називають ціною гри і позначають через v.
Оптимальні змішані стратегії та ціну гри називають розв’язком матричної гри
Теорема (про мінімакс). Для матричної гри з будь-якою матрицею А величини  і  існують і є рівними.
Вaжливою частиною більшості ігрових програм є процедура аналізу «дерева логічних можливостей».
Існує два типи дерев: дерева гри і дерева цілей. Гілки в дереві гри задають можливі ходи, ходи у відповідь і т. д. Дерево цілі показує, що деякої початкової цілі можна досягти, коли буде досягнуто певних підцілей; у свою чергу аналогічно перевіряють досягнення підцілей. Оскільки дерева мають тенденцію сильно розростатись, виникає потреба ефективного виділення істотних частин дерева. Дерево гри може бути експліцитним та імпліцитним. Експліцитне дерево гри задають у явному вигляді, імпліцитне ж дерево задають виділенням початкової позиції і правил формування дерева.
Корінь цього дерева збігається з початковою позицією. Кожен вузол цього дерева характеризується номером гравця, що має робити хід. Дуги відповідають ходам, тобто, якщо в позиції 1 можливий хід, який переводить позицію 1 в позицію 2, то з позиції 1 до позиції 2 йде орієнтована дуга, яка відповідає цьому ходу. Право вибору ходу в позиції 2 належить, звичайно, уже іншому гравцеві. Кожен вузол дерева корисно характеризувати також його рівнем, тобто відстанню від кореня. Якщо на k-му рівні право вибору ходу належить одному з гравців, то на (k + 1)-му рівні воно переходить до його суперника.
Нехай грають два гравці – А і В. Для визначеності вважатимемо, що право вибору ходу в початковій позиції належить гравцеві А. Функція виграшу збігається з функцією виграшу цього гравця, тобто гравець А аналізує дерево гри зі свого погляду та прагне максимізувати виграш. Вершини, в яких право ходу належить гравцеві А, прийнято називати α-вершинами; вершини ж, у яких право ходу належить його суперникові, називають β-вершинами.
Для будь-якої гри, що завершується за скінченну кількість ходів, є теоретично можливим побудувати повне дерево гри, що охоплює всі можливі позиції. Почнемо аналіз дерева з завершальних позицій (листків дерева). Розглянемо довільні завершальні позиції, які мають одного батька. Нехай для визначеності це α-вершини. Кожна завершальна позиція має оцінку, що збігається з функцією виграшу та є результатом гри. Ясно, що гравець В, якому належить право вибору ходу у батьківській вершині, вибере хід, що мінімізує цю оцінку (мінімізує його програш). Ця мінімальна оцінка передається даній вершині знизу.
Нехай всі наступники довільної β-вершини уже проаналізовані та кожному передано знизу певну оцінку. Загальне правило можна сформулювати у такий спосіб: з β-вершини має бути зроблений хід, що веде до позиції-наступника з найменшою оцінкою.
За допомогою аналогічних міркувань можна встановити правило, згідно з яким повинен вибирати ходи гравець А: з α-вершини має бути зроблений хід, що веде до позиції-наступника з найбільшою оцінкою.
Такий аналіз можна зробити для будь-якої позиції, включаючи початкову. Ця процедура носить назву мінімаксної процедури.


8. Метод резолюцій як основа логічного виведенняМетод резолюцій – логічне числення у мові логіки предикатів першого порядку, що використовує єдине правило виведення (т.зв. правило резолюції). Для мови численні висловлювань це правило формулюється так: із формул та , де - елементарна формула, виводиться формула , а з – виводиться "порожня" формула. Цього єдиного правила достатньо для встановлення того, чи є тотожно хибною довільна задана формула числення висловлювань, що подана в кон’юнктивній нормальній формі (КНФ). А саме, кон’юнкція скінченої множини М формул числення висловлювань, кожна з яких є диз’юнкцією елементарних формул і/чи їх заперечень, тотожно хибна тоді і тільки тоді, коли за допомогою правила резолюції із М виводиться порожня формула. Для логіки предикатів першого порядку правило резолюції формулюється більш складно - з використанням процедури уніфікації. Метод резолюцій вперше запропонував Дж.Робінсон в 1964. Його застосовують в мовах логічного програмування, при пошуку доведень теорем на ЕОМ, в доведеннях правильності програм, в системах планування поведінки роботів, в "питально-відповідальних" системах та ін. системах штучного інтелекту. Існують різні модифікації методу резолюцій, а також його узагальнень.

9. Мова функціонального програмування ЛІСПЗа однiєю з класифiкацiй мови програмування (МП) дiляться на процедурнi, якi також називаються операторними або iмперативними та декларативнi мови. До класу декларативних мов вiдносяться функцiональнi або апплiкативнi - Лiсп,.
Функцiональна програма складається з сукупностi визначених функцiй. Функцiї, в свою чергу, можуть викликати iншi функцiї. Обчислення починається з виклику деякої функцiї. Чисте функцiональне програмування не має присвоєнь та засобiв передачi керування. Повторнi обчислення здiйснюються за допомогою рекурсiї, яка є основним засобом функцiонального програмування.
Робота з Лiспом нагадує роботу з карманним калькулятором: користувач вводить вираз (вiн обов'язково повинен закiнчуватися символом та мати збалансовану кiлькiсть дужок), який читає машина, потiм обчислює (iнтерпретує), та видає результат. Цей процес введення-читання-обчислення-видачi результату буде вiдбуватися в циклi доти, доки користувач не введе команду (SYSTEM), яка завершує роботу з muLisp i передає керування операцiйнiй системi.
Приклад програми:
Напишемо функцію MEMBER, яка має два аргументи: nam - символ та lst - список і яка повинна перевірити чи належить символ списку.
(DEFUN MEMBER (nam lst)
((NULL lst) NIL)
((EQL nam (CAR lst)) T)
(MEMBER nam (CDR lst)) )

10. Мова логічного програмування ПРОЛОГЧислення предикатiв - математична основа мови.
В основі Прологу лежить поняття відношення, яке взяте з предикатних логік. Слово “предикат” відноситься до розділу математичної логіки, в якому досліджуються операції над логічними висловленнями. В логіці предикатів під предикатом розуміється деяка властивість, логічна функція від довільного числа аргументів, яка приймає тільки два значення - “істина” або ж “хибність”.
Логiку предикатiв, в деякiй мiрi, можна вважати спецiальним математичним апаратом формалiзацiї людського мислення. Звiдки, мови програмування логiчного типу є найбiльш зручними, для роботи з базами знань.
Факти та правила.
При побудовi речень Прологу використовується той же пiдхiд що й в предикатних логiках. Спочатку вiдкидаємо всi несуттєвi слова. Потiм трансформуємо речення, виставляючи на перше мiсце вiдношення.
Факти
В Пролозi зв'язок мiж об'єктами називається фактом. Факти можуть виражати як властивостi, так i вiдношення.
Запити
Враховуючи, що Пролог складається з множини фактiв, ми можемо задавати йому питання про цi вiдношення у виглядi запитiв. Пролог будує вiдповiдь i виводить її до друку.
Узагальнення
Програма на Пролозi будується iз двох типiв фраз (речень): фактiв i правил. Факти - це вiдношення, або ж властивостi, про якi ви, програмiст, знаєте, що вони iстиннi. Правила - це залежнi вiдношення; вони дозволяють Прологу робити виведення, порiвнюючи одну частину iнформацiї з iншою.
Правила Прологу складаються з трьох частин: голови, символу, тiла.
Голова - це факт, який буде вiрним, якщо деяка кiлькiсть умов виконається. Голову ще iнодi називають заключенням, або ж вiдношенням залежностi. Символ - вiддiляє голову правила вiд тiла; може бути текстовим типу or або ж if. Тiло - це множина умов (або список файлiв), котрi повиннi бути iстинними, для того щоб Пролог мiг довести, що голова правила вiрна.
Як змiннi отримують свої значення
В Пролозi не має операцiї присвоєння. Змiннi Прологу отримують свої значення, порiвнюючи їх з константами у фактах i правилах.
Поки змiнна не отримає свого значення, вона називається вiльною, а коли отримує значення - зв'язаною. Але вона залишається зв'язаною тiльки на час, який необхiдний для отримання одного розв'зку на запит, потiм Пролог звiльнює її, повертає i шукає альтернативнi розв' язки.

6. Обчислювальна геометрія, комп’ютерна графіка та комп’ютерна алгебра1. Складність алгоритмів, зведення задач, нижні оцінки складності задачЧас, який витрачається алгоритмом, як функція розміру задачі, називається часовою складністю цього алгоритму. Гранична поведінка цієї складності при збільшені розміру задачі називається асимптотичною часовою складністю.
Аналогічно, можна виділити об’ємну складність та асимптотичну об’ємну складність.
Оцінки складності:
верхні оцінки: OfN=gN | ∃c>0,N0>0:gN≤c∙fN,∀N≥N0;
нижні оцінки: ΩfN=gN | ∃c>0,N0>0:gN≥c∙fN,∀N≥N0;
ефективні оцінки: ΘfN=gN | ∃c1,c2,N0>0:c1∙fN≤gN≤c2∙fN,∀N≥N0;
Позначенням ofN визначаються функції, нехтувано малі у порівнянні з функцією fN. Вони визначаються умовою ofN=gN | ∀c>0 ∃N0>0:gN≤c∙fN,∀N≥N0.
Зведення задач. Метод зведення використовується для встановлення оцінки складності однієї задачі за відомою оцінкою складності іншої задачі.
Нехай маємо задачу A та задачу B. Кажуть, що задача A та перетворюється (зводиться) до задачі B, якщо:
Початкові дані задачі A перетворюються на відповідні початкові дані задачі B.
Розв’язується задача B.
Розв’язок задачі B (вихідні дані) перетворюється у правильний розв’язок задачі A.
Якщо кроки 1 та 3 можна виконати за час OrN, де N – розмір задачі A, то кажуть, що задача A є rN-звідною до задачі B. Цей факт позначають так: A∝rNB.
Зводимість не є симетричним відношенням. Якщо задачі A та B взаємно звідні, то вони називаються еквівалентними.
Нижні оцінки методом перетворення: Якщо відомо, що задача A вимагає щонайменше TN часу, і A∝rNB, то задачу B можна розв’язати за час не менший за TN-OrN.
Верхні оцінки методом перетворення: Якщо відомо, що задачу B можна розв’язати за час TN, і A∝rNB, то задачу A можна розв’язати за час, який не перевищує TN+OrN.
Відомі нижні оцінки складності деяких задач:
Для скінченної n-елементної множини S перевірка умови a∈S вимагає часу Ωlog2n;
Для впорядкування сукупності з n елементів необхідно часу Ωn∙log2n;
Якщо деяка задача у d-вимірному просторі вимагає fn часу, то для цієї ж задачі розмірністью k>d також потрібно принаймні fn часу;
Задачі із нижньою оцінкою складності Ωn∙log2n:
перевірка того, чи є у заданій сукупності два рівних елементи;
перевірка включення множин;
перевірка перетину множин;
перевірка на значимість: дано n точок на площині, визначити, чи усі вони належать опуклій оболонці;
перевірка ε-близькості: чи є серед елементів заданої n-елементної множини два елементи, які знаходяться на відстані ε.
2. Дерево відрізків та реберний список з подвійними зв’язками

3. Локалізація точки на планарному розбитті. Методи




4. Регіональний пошук. МетодиЗадача. На заданій множині S із N точок задано запитний регіон R. Знайти підмножину точок множини S ( або їх кількість), які містяться в регіоні R.
Одновимірний регіональний пошук. Множина з N точок на осі x являє файл, а запитним регіоном є відрізок [x',x"] ( який називається x- регіоном). Ефективний регіональний пошук реалізується через метод, який базується на методі двійкового пошуку. Структура даних, яка забезпечує вказану дію, є прошите двійкове дерево, т.т. таке збалансоване двійкове дерево, листки якого додатково зв’язані у списку, який виражає порядок абсцис; дерево і список обробляються на фазах відповідного пошуку й вибірки. Оцінки: оптимальна як по часу запиту (logN+k), так і по пам’яті (N).
Алгоритм 2-D-дерева. (складність попередньої обробки: , пошуку: ). Означення. Назвемо узагальненим прямокутником таку область на площині, яка визначена декартовим добутком [x1, x2][y1,y2] x- інтервалу - [x1, x2] та у – інтервалу - [y1,y2], включаючи граничні випадки, коли в довільній комбінації допускається: x1= - , x2 = , y1= - , y2 = .
Нехай задана множина S із N точок на площині. Для побудови структури даних, яка називається “2-D дерево” використовується схема “розподіляй та володарюй” суть якої полягає в рекурсивному розбиті площини на прямокутники R(v), означені вище. Результатом розбиття є бінарне дерево пошуку, вузлами якого є точки із заданої множини S на площині.
Проектуються усі точки множини S на вісі ОХ та ОУ. Знаходиться медіана списку точок впорядкованих по х, проводиться вертикаль. Точка буде коренем шуканого дерева і розіб'є список на дві рівнопотужні підмножини, для яких існують списки вопрядковані по у. Для них визначаються медіани і будуються горизонталі. Ті точки будуть наступними вузлами шуканого дерева. Для зручності при побудові шуканого дерева ведемо позначення для вузлів трьох різних типів: кружки - не листові вузли з вертикальною лінією розрізу, квадрати - не листові вузли з горизонтальною лінією розрізу, точки - листки.

Метод дерева регіонів. (складність попередньої обробки: , пошук:) . Будується дворівнева структура даних (дерево регіонів), перший рівень якої – дерево відрізків по одній із координат (наприклад х), а другий – вузли дерева відрізків прошиті упорядкованими списками по іншій координаті (наприклад у ).На побудованому дереві регіонів виконується операції вставки інтервалу ( проекція запитного регіону на вісь ОХ ), що дозволяє визначити вузли віднесення. Далі у вузлах віднесення застосовується дихотомія пошуку по іншій координаті (у).
Метод прямого доступу: Площина розбивається на комірки прямими, що проходять через всі дані точки (пари комірок утворюються класи еквівалентності відносно результатів пошуку). Для кожнох пари комірок встановлюється відповідна множина точок. Для співставлення точки одній комірці - двійковий пошук по x, у координатам. Звертання до файлу - константа. Пам'ять O(N5)

5. Побудова опуклої оболонки. Методи




6. Найближча пара, метод «Розділяй та пануй»
Примітка1: часову оцінку складності сортування списку точок по координаті х віднесемо до попередньої обробки вхідної множини, в найгіршому випадку сортування буде потребувати O(N^2), а в кращому O(Nlog2N). Сортування множини точок по координаті у можно виконувати за O(N) прямо під час кроку злиття двох вже відсортованих по у множин.
Примітка2: на етапі злиття, маючи відсортовані по y точки, ми розглядаємо відстань тільки між тими точками, між якими різниця ординат менше нашої мінімальної дистанції (а не відстань між всіма точками першої і другої множин).
Примітка3 (для тих, кто сумнівається, що крок 6 виконується за лінійний час):

Примітка4 (сама очевидність): щоб показати, що часова оцінка складності дійсно дорівнює O(Nlog2N) треба показати, що часова оцінка на кроці злиття дорівнює O(N), а враховуючи Примітку2 і Примітку3 бачимо, що це так і є.

7. Означення та властивості діаграми Вороного. Побудова діаграми Вороного.

Побудова (за час ONlogN):
Розділити множину точок S на дві приблизно рівні множини S1 та S2 горизонтальною прямою.
Рекурсивно побудувати діаграму Вороного для S1 та S2.
Побудувати ламану σ, яка розділяє S1 та S2.
Побудувати опорні відрізки до опуклих оболонок S1 та S2.
Проводити серединний перпендикуляр до одного з опорних відрізків до перетину з якоюсь прямою з вже побудованих діаграм Вороного.
Дві прямі, що перетнулись, розділяють три точки. Відкидаємо спільну точку з розгляду, і продовжуємо будувати серединні перпендикуляри для двох точок, що залишилися.
Так будувати доти, поки ламана, не співпаде з серединним перпендикуляром до якогось іншого опорного відрізка.
Видалити усі ребра з діаграми верхньої множини, які лежать нижче за ламану. Аналогічно з точністю до навпаки для нижньої множини.
8. Перетин та об’єднання опуклих многокутників. Перетин відрізків



9. Поняття замкненого півкільця. ПрикладиЗамкнене півкільце – це A;+,*;0,1, в якій виконуються наступні властивості:
за операцією + це ідемпотентний комутативний моноїд з нейтральним елементом;
за операцією * це просто моноїд з нейтральним елементом, в якому до того ж для довільного елемента a*0=0*a=0 (окрім властивості моноїда a*1=1*a=a);
* дистрибутивне відносно +;
визначеність нескінченних сум (∀a1,a2,… визначена (скінченна і єдина) сума a1+a2+…);
для нескінченних сум діють асоціативність та комутативність;
* дистрибутивне відносно нескінченних сум (aibj=aibj).
SiA +*0 1
Алгебра Буля 0, 1∨(max)∧(min)01Алгебра відстаней R0+min++∞0«Майже» регулярна алгебра мов βFXFX – множина всіх скінченних слів з алфавіту X∪∙(конкатенація) ∅εАлгебра відношень βA×A∪°(композиція відношень) ∅(порожнє відношення) iA(діагональне відношення)
Алгебра мариць з нулів та одиниць Mnмножина квадратних матриць розмірами n×n з коефіцієнтами 0, 1+S1(покомпонентне додавання) ×(матричне множення) [0]En
10. Лінійні коди. Алгебраїчна характеризація лінійних кодів.Породжуюча та перевірочна матриці.

11. Простий многочлен над скінченним полем та поле остач від ділення на цей многочленДопоміжні означення для означення поля:
Групоїд — це алгебра типу <2> без тотожностей.
Група (вільна) — це моноїд, в якому .
Кільце — це алгебра (A; +,*), в якій: (A; +) — комутативна група, (A; *) — групоїд, * дистрибутивна відносно +. Кільце називається комутативним, якщо * комутативна; кільцем з одиницею, якщо за * є одиниця; асоціативним, якщо (A; *) — півгрупа. Одиниця за додаванням позначається 0, за множенням (якщо є) — 1.
Тіло — це кільце (A; +,*), в якому (A\{0}; *) — група.
Поле — це тіло з комутативною операцією *, тобто це кільце, в якому (A\{0}; *) — комутативна група.
Означення. Многочлен a(x) над полем F — незвідний, якщо ділиться тільки на f*a(x) та f, де f — ненульовий елемент поля F. Простий многочлен над полем F — це зведений незвідний над F. Елемент f поля F — корінь многочлена a(x), якщо a(f)=0.
Нехай Fq — скінченне поле з q елементів. Многочлен a(x) з Fq[x] визначає множину остач Fq[x]/a(x) від ділення на нього. Якщо deg a(x) = m, то кількість остач дорівнює qm.
Означимо додавання елементів Fq[x]/a(x) як b(x)+c(x) = Ra(x)(b(x)+c(x)). Оскільки Fq є полем, аналогічно можна означити віднімання та множення: b(x)–c(x)=Ra(x)(b(x)–c(x)), b(x)*c(x)=Ra(x)(b(x)*c(x)). Неважко переконатися, що Fq[x]/a(x) є кільцем, у якому 0 — многочлен 0, 1 — многочлен 1.
Твердження. Fq[x]/a(x) є полем тоді й тільки тоді, коли a(x) є простим над полем Fq.
Доведення. Необхідність. Припустимо супротивне: нехай Fq[x]/a(x) є полем, але a(x) — не простий над Fq. Нехай a(x)=s(x)*r(x), де deg s(x)>0, deg r(x)>0. Звідси s(x) і r(x) є елементами кільця й є дільниками нуля, а це суперечить тому, що Fq[x]/a(x) є полем.
Достатність. Нехай a(x) є простим над полем Fq. Достатньо довести, що кожен елемент кільця остач має обернений елемент за множенням. Нехай b(x) — довільний елемент кільця остач. Оскільки a(x) — простий над полем, усі остачі від ділення на нього взаємно прості з ним. Тоді за висновком з алгоритму Евкліда існують многочлени над цим полем u(x) та v(x), за яких D(a(x),b(x))=a(x)u(x)+b(x)v(x). Отже,
1 = Ra(x)(a(x)u(x)+b(x)v(x)) = Ra(x)(b(x)v(x)) = Ra(x)(b(x)Ra(x)(v(x))).
Звідси Ra(x)(v(x)) = b–1(x).
Висновок. Простий многочлен степеня m над скінченним полем Fq визначає поле остач від ділення на нього, яке має qm елементів.

11. Кільце остач від ділення на многочлен над скінченним полем


Приложенные файлы

  • docx 26570021
    Размер файла: 5 MB Загрузок: 0

Добавить комментарий