- •Змістовий модуль 1
- •Не 1.1. Структура системного програмного забезпечення Структура спз.
- •Місце ос в спз.
- •Поняття операційного середовища.
- •Операційні системи.
- •Системи керування файлами.
- •Інтерфейсні оболонки для взаємодії користувача з ос і програмні середовища.
- •Системи програмування.
- •Утиліти.
- •Основні функції ос.
- •Не 1.1. Базові поняття сучасних операційних систем Базові поняття операційної системи Linux. Файли, каталоги, робота з файлами. Права доступу до файлів і каталогів.Інструментарій.
- •Програми-фільтри. (немає) Командний інтерпретатор.
- •Змістовий модуль 2
- •Не 2.1. Загальна схема роботи компіляторів Визначення транслятора, компілятора, інтерпретатора.
- •Компілятор.
- •Різниця між інтерпретаторами і трансляторами.
- •Етапи трансляції.
- •Поняття проходу. Багатопрохідні і однопрохідні компілятори.
- •Не 2.2. Таблиці ідентифікаторів. Призначення та особливості побудови таблиць ідентифікаторів.
- •Найпростіші методики побудови таблиць ідентифікаторів.
- •Побудова таблиць ідентифікаторів методом бінарного дерева.
- •Не 2.3 Хеш-функції та хеш–адресація. Принципи роботи хеш-функцій.
- •Побудова таблиць ідентифікаторів на основі хеш-функцій.
- •Побудова таблиць ідентифікаторів методом ланцюжка.
- •Комбіновані способи побудови таблиць ідентифікаторів.
- •Змістовий модуль 3. Не 3.1.Кінцеві автомати. Визначення.
- •Детерміновані і недетерміновані кінцеві автомати.
- •Модель ка.
- •Розпізнавачі і перетворювачі. Визначення. Загальні поняття.
- •Класифікація розпізнавачів.
- •Не 3.2.Формальні мови та граматики. Способи завдання мов.
- •Операції над ланцюжками символів.(немає) Поняття мови.
- •Визначення формальної мови.
- •Визначення грамматики.
- •Класифікація граматик.
- •Способи задання схем грамтик Символічна, форма Наура-Бекуса, ітераційна форма й синтаксичні діаграми.
- •Чотири типи граматик по Хомському.
- •Правила побудови граматики із ланцюжка символів. (немає)
- •Змістовий модуль 4.
- •Не 4.1 Лексичні аналізатори (сканери).
- •Принципи побудови сканерів.
- •Призначення лексичного аналізатору.
- •Принципи побудови лексичних аналізаторів.
- •Граф кінцевого детермінованого автомата, що розпізнає граматику цілих чисел мови Сі(Немає) не 4.2.Синтаксичний та семантичний аналіз. Синтаксично-керований переклад.
- •Основні принципи роботи синтаксичних аналізаторів.
- •Дерево розбору. Перетворення дерева розбору в дерево операцій.
- •Призначення семантичного аналізу.
- •Етапи семантичного аналізу.
- •Ідентифікація лексичних одиниць мов програмування.
- •Розподіл пам’яті.
- •Не 4.3. Способи внутрішнього представлення програм Зв'язані облікові структури, що представляють синтаксичні дерева.
- •Багатоадресний код з явно іменованим результатом (тетради).
- •Багатоадресний код з неявно іменованим результатом (тріади).
- •Обернений (постфиксна) польський запис операцій.
- •Алгоритм Дейкстри.
- •Асемблерний код або машинні команди.
- •Розбір арифметичного виразу. Алгоритм Рутисхаузера.
- •Не 4.4 Генерація коду. Методи генерації коду.
- •Загальні принципи генерації коду.
- •Синтаксично керований переклад.
- •Змістовий модуль 5
- •Не 5.1. Керування процесами та ресурсами. Поняття обчислювального процесу та ресурсу.
- •Класифікація ресурсів.
- •Загальна схема виділення ресурсу.
- •Однопрограмний і мультипрограмний режими.
- •Основні риси мультипрограмного режиму.
- •Обчислювальні процеси.
- •Діаграма станів процесу.
- •Реалізація поняття послідовного процессу в ос.
- •Процеси і треди. (немає) Блок керування процесом.
- •Процеси в ос unix.
- •Події (переривання) - рушійна сила, що змінює стан процесів.
- •Механізм обробки переривань.
- •Функції механізму переривань.
- •Групи переривань.
- •Розподіл переривань по рівнях пріоритету.
- •Дисципліни обслуговування переривань.
- •Обробка переривань за участю супервізорів ос.
- •Не 5.2. Планування процесів та диспетчеризація задач. Функції ос, пов’язані з керуванням задач.
- •Організація черг процесів та ресурсів.
- •Priority queuing - (pq)
- •Стратегії планування.
- •Якість диспетчеризації та гарантії обслуговування.(Немає)
- •Безпріоритетні до: лінійні та циклічні.
- •Пріоритетні до: до з фіксованим пріоритетом та до з абсолютним пріоритетом.
- •Адаптивні до. (Немає) Визначення середнього часу знаходження заявки в системі. (Немає) Недоліки до з фіксованим пріоритетом.
- •Динамічне планування (диспетчеризація). (Немає) Диспетчеризація задач з використанням динамічних пріоритетів. Переваги і недоліки.
- •Критерії ефективності обчислювального процесу. (Немає) Методи підвищення продуктивності системи для багатопроцесорних систем.
- •Механізм динамічних пріоритетів в ос unix.
- •Змістовий модуль 6
- •Не 6.4. Керування пам’яттю. Пам'ять і відображення, віртуальний адресний простір.
- •Простий безперервний розподіл і розподіл з перекриттям (оверлейні структури).
- •Розподіл статичними і динамічними розділами.
- •Розділи з фіксованими границями. Розділи з рухливими границями.
- •Виділення пам'яті під новий розділ: перша придатна ділянка; сама придатна ділянка; сама невідповідна ділянка.
- •Сегментна, сторінкова і сегментно-сторінкова організація пам'яті. Сегментний спосіб організації віртуальної пам'яті.
- •Дисципліни заміщення: fifo; lru (1еаst recently used,); lfu (1еаst frequently used); random.
- •Сторінковий спосіб організації віртуальної пам'яті.
- •Сегментно-сторінковий спосіб організації віртуальної пам'яті.
- •Змістовий модуль 7
- •Не 7.1. Ос однопроцесорних кс. Класифікація ос.
- •Режими організації обчислювального процесу. (Немає) Основні принципи побудови операційних систем.
- •Принцип модульності.
- •Принцип функціональної вибірковості.
- •Принцип генерування ос.
- •Принцип відкритої і нарощуваний ос.
- •Принцип мобільності.
- •Принцип забезпечення безпеки обчислень.
Операції над ланцюжками символів.(немає) Поняття мови.
Позначимо через V* множину, що містить усі ланцюжки в алфавіті V, включаючи порожній ланцюжок e , а через V+ позначимо множину, що містить усі ланцюжки в алфавіті V, крім порожнього ланцюжка e . Отже, V* = V+ И {e }.
Мова в алфавіті V - це множина ланцюжків кінцевої довжини в цьому алфавіті. Зрозуміло, щокожна мова в алфавіті V є підмножиною множини V*.
Визначення формальної мови.
Формальні мови - це математичний апарат, що дозволяє математично грамотно створити мови програмування і писати компілятори для них.
Формальну мову можна задати як послідовність слів. Слово – це послідовність символів. Тоді навіть програму можна вважати просто словом.
Словами даної мови може бути не довільний набір символів, а лексично і синтаксично правильно побудований. Для того, щоб задати граматику, треба задати множини термінальних і не термінальних символів.
Термінальні – це символи, які використовуються в мові, а проміжні абонетермінальні– це символи, які використовуються для створення слів мови. Створюються слова за граматичними правилами. Застосування правила полягає в заміні в перетворюваному рядку якоїсь послідовності символів, що співпадає з лівою або правою частиною правила.
Компілятор, отримавши на вхід програму, робить зворотну роботу. Він згортає за граматичними правилами від правої до лівої частини початкові символи.
Кінцева множина символів, яка є неподільною, називається словником або алфавітом, а символи, що входять в множину – буквами алфавіту. Послідовність букв алфавіту називається словом аболанцюжкомцього алфавіту, число букв, що входить у слово, називається його довжиною.
Якщо задано алфавіт А, то А*- це множина всіх ланцюжків, які можна побудувати з алфавіту А. $ - порожній рядок (рядок, що не містить жодної букви) також входить в А. Для позначення всіх ланцюжків алфавіту А, що не містять порожнього використовується А+.
Визначення грамматики.
Формальною граматикоюГ називається сукупність таких об’єктів:
Г={VT,VN,<I>,R},
Де VT– термінальний алфавіт (словник). З букв цього алфавіту будуються ланцюжки, які породжуються граматикою.
VN– нетермінальний (допоміжний) алфавіт. Його букви використовуються при побудові ланцюжків, вони можуть входити в проміжні ланцюжки, але не можуть входити в результат побудови.
<I> - початковий символ.
R– множина правил виведення.
Множина кінцевих ланцюжків термінального алфавіту VTграматики Г, виведених з початкового символу <I> називаютьмовою, яка породжена граматикою Г і позначаєтьсяL(Г).
Якщо правило виведення граматики мінить один нетермінальний символ, як в лівій, так і в правій частині, то таке правило називається рекурсивним.
Класифікація граматик.
В теорії формальних мав виділяють 4 типи граматик, яким відповідають 4 типи мов. Ці граматики виділяються шляхом накладання обмежень на правила граматики:
Граматики типу 0це граматики загального виду не мають ніяких обмежень на правил породження. Правила виведення в таких граматиках повинні мати вигляд:
R=η->Ψ
Граматики типу 1називають контекстно-залежними граматиками(КЗК).
Правила виведення в таких граматиках повинні мати вигляд:
χ1<A>χ2->χ1ώχ2
Ланцюжки χ1 та χ2 залишаються незмінними при застосуванні правила залишаються незмінними(контекстом) і граматика відповідно контекстно-залежна.
Граматики типу 1 зручніші на практиці ніж граматики типу 0, оскільки в лівій частині правила заміняється завжди 1 не термінальний символ, в той час, як в граматиці типу 0 можна заміняти відразу декілька символів, в тому числі і термінальних.
Граматики типу 2називають контекстно-вільними або КВ граматиками, або без контекстними граматиками. Правила виведення мають вигляд:
<A>->α
Де не термінальний символ <A> належить множині не термінальних символів. α – належить множині термінальних символів.
Очевидно що ці правила слідують із правил граматики типу 1 за умови якщо χ1 та χ2 порожні. Оскільки контекстні умови відсутні, то правила КВ граматик простіші, ніж правила граматик типу 1. Саме такі граматики використовують для опису мов програмування.
Приклад такої граматики:
G1.6 Vt={a,b} Va{<I>},<I>
R:{<I>->a<I>a;
<I>->b<I>b;
<I>->aa;
<I>->bb;}
Приклад:
<I>->a<I>a->ab<I>ba->abaaba
Ця граматика породжує мову починається з а та симетрична відносно середини.
Граматика типу 3або автоматна граматика або А граматиками. Правила виведення в таких граматиках мають вигляд:
<A>->a
<A>->a<B>
<A>-><B>a
Причому граматика може мати правила або ліво лінійні <A>->a<B> або право лінійні <A>-><B>a.
G1.7 Vt={a,b} Va={<I>,<A>,<Z>}
R={<I>->a<I>;
<I>->a<A>;
<A>->b<A>|b<Z>;
<Z>->$;}
Приклад:
a<I>->aa<A>->aab<A>->aabb<Z>aabb;
G1.8 Vt={a,b} Va={<I>,<A>,<Z>}
R: { <I>-> <A>b;
<A>-><A>b;
<A>-><Z>a;
<Z>-><Z>a|$;}
Приклад:
<I>-><A>b-><A>bb-><Z>abb->abb
Класифікація мов може бути побудована, відповідно до типу граматик, що її породжують.
Одна і та сама мова може бути задана різними граматиками, тому тип мови визначають по типу тієї граматики, що не може бути представлена граматикою типу К+1.