ІНСТИТУТ КОМП’ЮТЕРНИХ ТЕХНОЛОГІЙ, АВТОМАТИКИ І МЕТРОЛОГІЇ Напрям: Комп’ютерна інженерія Спеціальність: Системне програмуванняI. Програмування1. Концептуальні основи сучасних мов програмуванняІнформація та її представлення в пам’яті комп'ютера. Сутності концепції дії, концепції розподілу пам'яті, концепції типів даних. Внутрішнє представлення даних в пам’яті комп'ютера. 2. Методи побудови та аналізу алгоритмівАлгоритми сортування та пошуку даних. Рекурсивні алгоритми. Алгоритми з поверненням. 3. Динамічні структури данихСтеки. Черги. Списки. Дерева. Графи. Приклади їх застосування для розв'язання прикладних задач. 4. Технології програмуванняМетодологія розробки великих програмних комплексів. Сучасні системи програмування. Ефективність і надійність програм. ^ II. Периферійні пристрої1. Основні принципи функціонуванняРоль і місце периферійних пристроїв (ПП) в ієрархії ЕОМ та комп’ютерних систем (КС). Класифікація ПП. Основні функції, компоненти, характеристики систем уведення-виведення інформації. Способи підключення ПП до пристроїв управління. 2. Інтерфейси периферійних пристроївВизначення, характеристики-класифікатори та загальні характеристики інтерфейсів ПП. Паралельні інтерфейси, основні характеристики, склад і призначення ліній зв'язку, особливості обміну інформацією і виконання основних операцій. Інтерфейси каналів уведення-виведення великих, малих та мікро- ЕОМ. Інтерфейси ISA, EISA, Q-bus, ІРПР-BS4421, ІРПР-М-Centronics; загальна шина, шина ІЕЕЕ-488, IPІ, ATA, SCSI. Послідовні інтерфейси, основні характеристики, склад і призначення ліній зв'язку, особливості обміну інформацією і виконання основних операцій (інтерфейси: RS232С, ІРПС-CL, USB, MIL-1553В). 3. Пристрої зв'язку з об'єктами, в яких використовуються аналогові сигналиДискретизація, квантування сигналів. Основні характеристики АЦП і ЦАП. Структурна схема периферійної підсистеми. 4. Зовнішні запам`ятовуючі пристроїМагнітні зовнішні запам`ятовуючі пристрої. Оптичні зовнішні запам`ятовуючі пристрої. Напівпровідникові зовнішні запам`ятовуючі пристрої. 5. Системи уведення-виведення текстової інформаціїКласифікація, загальні характеристики, принципи кодування текстової інформації. Принципи побудови, характеристики, структурні схеми пристроїв ручного та автоматичного уведення текстової інформації. Принципи побудови, характеристики, структурні схеми пристроїв реєстрації текстової інформації (друкуючі пристрої - принтери). 6. Системи уведення-виведення графічної інформаціїКласифікація, загальні характеристики. Принципи побудови, схеми, характеристики, функціювання пристроїв автоматичного та напівавтоматичного уведення графічної інформації. Пристрої реєстрації графічної інформації, основні характеристики, принципи побудови та функціювання. Пристрої відображення графічної інформації (монітори, відеоадаптери), основні характеристики, принципи побудови і функціювання, структурні схеми. 7. Пристрої уведення та виведення мовиПристрої уведення та виведення мови, основні характеристики, принципи побудови та функціювання. ^ III. Системне програмне забезпечення (СПЗ)1. Призначення системного програмного забезпечення (СПЗ)Структура та особливості побудови системного програмного забезпечення. Місце СПЗ в узагальненій структурі програмного забезпечення комп’ютерів. Класифікація операційних систем. 2. Основні складові СПЗСистеми програмування. Утиліти. Керуючі програми операційної системи (ОС) та її підсистеми. 3. Підсистема керування процесамиПоняття про обчислювальний процес. Призначення підсистеми. Принципи побудови підсистеми. Особливості керування процесами. Стани процесів та умови переходу зі стану в стан. Диспетчеризація процесів та засоби синхронізації. 4. Підсистема керування ресурсамиКласифікація ресурсів. Структура пам’яті обчислювальної системи. Види розподілу пам’яті. Віртуальна пам'ять. 5. Підсистема керування данимиКласифікація даних, файли. Файлові системи, їх призначення та застосування. Різновиди та способи організації зовнішньої пам’яті. Планування роботи з дисковою пам’яттю. 6. Особливості організації типових операційних системMS-DOS. MS Windows. UNIX. ^ IV. Паралельні та розподілені обчислення1. Основні поняття про паралельні та розподілені обчисленняОсновні принципи паралелізму. Рівні розпаралелювання. Організація паралельних та розподілених обчислень. Однорангові та колективні обчислення. Класифікації структур. 2. Побудова та аналіз алгоритмів паралельних та розподілених обчисленьМоделі паралельних та розподілених обчислень. Паралелізм даних, паралелізм задач. Етапи розробки паралельного алгоритму. Схеми алгоритмів задач. Алгоритми перемноження матриці на матрицю та їх реалізація на різних обчислювальних структурах. 3. Концепція паралельної та розподіленої обробкиСпівпрограми. Виникнення паралельних процесів. Об’єднання, синхронізація процесів. Проблеми та організація асинхронної і синхронної паралельності. 4. Організація мереж ПетріПрості, розширені мережі. Приклади реалізації мереж. 5. Основні класи сучасних паралельних комп'ютерів та структури зв’язку між нимиМережі з комутаторами. Структури, які забезпечують зв’язок типу «пункт-пункт». Методи комутацій. 6. Проблеми розподілених обчисленьЗупинки. Вибір лідера. Взаємне виключення. Передача повідомлень. Відмовостійкість. Причинні зв’язки. Синхронізація. 7. Мови і організація паралельного програмуванняКласифікація мов і систем паралельного програмування. Особливості організації паралельної програми. Технології паралельного програмування MPI. Операції обміну повідомленнями. Бібліотечні функції для паралельного програмування. Засоби взаємодії та синхронізації процесів. Шляхи забезпечення надійності програмного забезпечення. 8. Методи оцінки продуктивності алгоритмів і системХарактеристики продуктивності паралельних алгоритмів. Характеристики продуктивності паралельних систем. ^ 9. Балансування навантаження при організації паралельних та розподілених обчислень Види балансування. Алгоритми балансування.V. Основи алгоритмізації та програмування1. Метамова синтаксису стандартної (авторської) мови програмування ПаскальВикористання синтаксичних діаграм. Використання формул Бекуса-Наура. 2. Синтаксичне визначення понять мови ПаскальПрограма. Блок. опису міток. опису констант. опису типів. опису змінних. опису процедур та функцій. операторів. 3. Базовий словник мови ПаскальАлфавіт мови Паскаль. Набір ключових (зарезервованих) слів мови Паскаль. Правила запису імен (ідентифікаторів) та констант: числових, символьних, логічних, рядкових. 4. Типи даних мови Паскаль та засоби роботи з нимиСтандартні типи даних (integer, real, Boolean, char) та набір операції для цих типів даних. Стандартні функції для роботи із стандартними типами даних. Синтаксис виразів та правила їх обчислення. Правила визначення типу виразу. Стандартні процедури введення-виведення даних. Оператор присвоювання, умовні оператори, оператори циклу. Перелічувані (скалярні) та обмежені типи даних. Масиви, індексовані змінні, операції з індексованими змінними. Комбінований тип даних, операції з такими даними. Множини, операції з даними множинного типу. Файловий тип даних, стандартні процедури та функції для виконання файлових операцій. Динамічні операції і стандартні процедури для роботи з ними. Правила опису процедур та функцій, виклик описаних в програмі процедур та функцій, формальні та фактичні параметри, глобальні змінні. ^ VI. Комп’ютерні системи1. Основні передумови створення та еволюція КСОсновні галузі застосування паралельних КС. Приклади великих задач, які розв’язують КС та супер-ЕОМ. Характеристики та параметри КС. Визначення продуктивності паралельних комп’ютерів. Основні ознаки, за якими класифікуються КС. Основні структури та порівняний аналіз високопродуктивних КС. Поняття про розпаралелювання математичних задач та алгоритмів. Особливості програмного забезпечення паралельних КС. 2. Основні підходи до побудови високонадійних КССистеми високої готовності та відмовостійкості КС. КС в режимі реального часу. КС взаємодії з реальними об’єктами: вимірювально-обчислювальні системи. 3. Однорідні обчислювальні системи та середовищаДецентралізовані системи. Концепція самоорганізації, конфігурації та нарощування. КС з конвеєрною обробкою інформації. Асоціативні та матричні КС. 4. Мультипроцесорні КС з загальною пам’яттю та розподіленою пам’яттюАрхітектура та організація обчислювального процесу. Необхідність забезпечення узгодження вмісту КЕШ-пам’яті (архітектура ссNUMA). Концепція розподілених обчислень: обчислювальні кластери та гратчасті (решітчасті) обчислення. 5. Огляд сучасних високопродуктивних та високонадійних КС.Рейтинг Тор 500. Розвиток елементної бази. Особливості розвитку архітектур 64-розрядних мікропроцесорів. Досягнення та проблеми Internet: сучасний стан Internet. Перспективні напрями розвитку КС. VII. Комп’ютерні мережі1. Концептуальні основи побудови комп’ютерних мережРізновиди комп’ютерних мереж. Модель взаємодії відкритих систем (семирівнева модель OSI). 2. Середовища передавання данихТехніко-експлуатаційні характеристики середовищ передавання даних. Кабельні середовища передавання даних. Безкабельні (ефірні) середовища передавання даних. 3. Способи та форми передавання даних в каналах комп’ютерних мережСтруктурна схема ланки передавання даних. Форми передавання даних (сигнали) в каналах комп’ютерних мереж. Синхронізація передавання. Передавання даних в мережі за допомогою модему та мережного адаптера. 4. Протоколи передавання даних в комп’ютерних мережахМодернізована модель OSI. Протоколи фізичного та канального рівнів. Протоколи керування доступом до фізичного середовища передавання. Методи доступу до фізичного середовища передавання. Метод конкурентного доступу. Маркерні методи доступу. Протоколи керування логічним каналом. Протоколи модемів. Протоколи мережного рівня. Протоколи транспортного рівня. Данограмні мережі. Мережі віртуальних каналів. Методи маршрутизації. Протоколи сеансового рівня. Протокольні стеки. 5. Технології комп’ютерних мережТехнології локальних мереж Ethernet та Fast Ethernet. Технологія комутації кадрів у локальних мережах. Принципи функціонування та ефективність комутаторів. Віртуальні мережі (VLAN). 6. Особливості організації та функціонування глобальної мережі Internet.Структура мережі Internet. Абоненти мережі Internet. Проблеми, які виникають при підключенні до Internet. Стек протоколів ТСР/ ІР в мережі Internet. ІР-адресація. Класи ІР-адрес. ІР-маршрутизація. Інформаційні сервіси Internet. Основні компоненти технології WWW.^ VIII. Архітектура комп’ютерів та комп’ютерних систем1. Типи даних, формати і типи команд, способи адресаціїФормат команди, командний цикл. Класифікація команд відповідно до ініційованих ними типів операцій. Конвеєрне виконання команд. Стекова, акумуляторна, та на основі регістрів загального користування архітектури комп’ютера, їх переваги і недоліки. Способи адресації, включаючи безпосередню, пряму, непряму, базову, індексну, сторінкову і стекову. Комп’ютери з складною, з простою, з доповненою та орієнтованою системою команд. 2. Представлення даних в комп’ютеріПозиційні системи числення та представлення даних в двійковому, вісімковому і шістнадцятковому кодах. Переведення чисел із системи числення з основою k до десяткової, а також переведення чисел із десяткової до системи числення з основою k. Представлення чисел зі знаком в прямому, оберненому та доповняльному кодах. Формати даних з фіксованою та з рухомою комою, включаючи стандарт IEEE - 754. Кодування алфавітно-цифрової інформації кодами ASCII та EBCDIC. 3. Операції обробки данихОсновні алгоритми операцій обробки даних: логічних, зсуву, відношення, арифметичних, обчислення елементарних функцій, перетворення даних, реорганізації масивів і визначення їх параметрів, обробки символів та стрічок символів. Виконання вищеназваних операцій. 4. Принципи побудови арифметико-логічного пристроюАЛП з внутрішньою регістровою пам’яттю. АЛП на основі табличних операційних пристроїв. АЛП на основі багатотактових та конвеєрних операційних пристроїв. 5. Пристрої керуванняСтруктура та організація роботи пристроїв керування з жорсткою логікою. Методи проектування пристроїв керування з жорсткою логікою: на основі таблиць станів, на основі тактованих елементів часової затримки, та на основі лічильників. Робота пристрою мікропрограмного керування. Горизонтальне та вертикальне мікропрограмування. 6. Місце процесора в комп’ютері, його функції та складОдношинна структура процесора та виконання на ній основних операцій процесора: вибірки слова з пам'яті, запам'ятовування слова в пам'яті, обміну між регістрами, виконання арифметичних і логічних операцій. Порівняння одношинної і багатошинної структури процесора. Особливості побудови процесора комп’ютера з складною системою команд. Базові принципи побудови процесора комп’ютера з простою системою команд. Конфлікти в конвеєрі команд та методи їх усунення. Методи запобігання трьох класів конфліктів: структурних, конфліктів за даними та конфліктів керування. 7. Структура пам’яті комп’ютераОсновні характеристики пам’яті: ємність, організація, швидкодія, час доступу, період звернення, вартість. Організація взаємодії між рівнями ієрархічної пам’яті. Сегментна організація пам’яті та питання захисту пам'яті. 8. Взаємодія з пристроями введення-виведенняСпособи розпізнавання пристроїв введення-виведення з використанням шини введення-виведення, лінії активації та прихованого пам'яттю введення-виведення. Методи керування введенням-виведенням. Система переривання програм, основні поняття та характеристики системи переривання програм. 9. Загальна структура комп’ютераОсобливості комп’ютерних архітектур. Характеристики комп’ютера. 10. Автоматичні обчисленняЗадачі і комп’ютерні ресурси. Комп’ютер як система. Витрати процесорного часу. Продуктивність і кількістні оцінки продуктивності комп’ютера. Закон Мура і закон Амдаля. Критерії ефективності архітектур рівня машинних інструкцій.11. RISC архітектура RISC процесор. Операційний автомат. Алгоритми виконання RISC інструкцій. Автомат керування.12. Конвеєр виконання RISC інструкцій Конвеєризація операційного автомата. Мікропрограма керування конвеєром виконання машинних інструкцій. Боротьба з пригальмуваннями конвеєра виконання машинних інструкцій. Переривання на конвеєрі виконання машинних інструкцій.13. RISC процесор Мікроархітектури надконвеєрного і надскалярного процесорів. Мікроархітектура процесора з довгим словом інструкції (VLIW). Мікроархітектури надниткових і багатоядерних процесорів. Енергетичні характеристики процесора.14. Підсистема пам’яті Мікроархітектури основної пам’яті і перепускна спроможність. Когерентність пам’яті. Організація ієрархії, мікроархітектура і швидкодія кеша. Мікроархітектуура, швидкодія і надійність дискової пам’яті. Масиви RAID. Мікроархітектура апаратних засобів підтримки віртуальної пам’яті.15. Динамічне планування виконання потоку інструкцій Ідея і принципи реалізації динамічного планування. Алгоритм Томасуло. Спекулятивне розширення алгоритму Томасуло.16. 64 розрядні архітектури Архітектура Intel 64. Архітектура Intel EPIC. Архітектура IBM POWER. 17. Ненойманівські машини Мультипроцесор і мультикомп’ютер. Кластер. Машина потоку даних. Асоціативна машина.18. Реальний світФлеш-диск як класична комп’ютерна система на кристалі. Персональний комп’ютер і нетбук. Мейнфрейми IBM z/Series.^ IX. Прикладна теорія цифрових автоматів (ПТЦА)1. Інформаційні основи цифрових автоматів (ЦА)Аналогові та цифрові методи порівняння ЦА. Дискретизація та квантування. Загальні відомості про ЦА. Алгоритм, автомат, алфавіт. 2. Логічні основи ЦАЕлементарні функції алгебри логіки (ФАЛ). Функціонально повні системи. Алгебра Жегалкіна. Алгебра Буля. Форми представлення ФАЛ. 3. Синтез комбінаційних ЦАКанонічна та загальна задачі мінімізації ФАЛ в базисі Буля. Синтез комбінаційних ЦА з декількома виходами. Особливості синтезу комбінаційних ЦА в небулевих базисах. Монобазиси. Мажорітарний базис. 4. Базові комбінаційні вузли ЦАПеретворювачі кодів. Шифратори, дешифратори. Мультиплексори, демультиплексори. Схеми порівняння. Комбінаційні суматори. Великі інтегральні схеми з матричною структурою (ПЗП, ПЛМ, ПМЛ). 5. Послідовнісні ЦАЧасові ФАЛ 1, 2 та 3 роду. Тригери. Автомати Мілі та Мура. 6. Представлення числової інформації в ЦАСистеми числення (СЧ). Методи утворення та класифікація СЧ. Проблема визначення знаку числа. СЧ з симетричною основою. 7. Арифметичні та логічні операції над числами в різних СЧДвійкова СЧ. Двійково-кодовані СЧ. Двійково-десяткові СЧ та особливості виконання операцій в цих СЧ. Арифметичні операції в непозиційних СЧ. Контроль та діагностика ЦА. ^ X. СИСТЕМНЕ ПРОГРАМУВАННЯ 1. Засоби та задачі системного програмування Класифікація програм. Вимоги до програм. Процес створення програм. Технологія розробки та експлуатації програм. Мови системного програмування. 2. Архітектура та система команд базового процесора і8086Архітектура та програмна модель МП і8086. Призначення регістрів. Організація пам’яті. Формат машинної команди. Режими адресації операндів. Основні групи команд і режими їх виконання. 3. Програмування мовою Асемблер Структура програми. Формат рядка тексту асемблерної програми. Основні директиви. Вирази та операції. Директиви опису даних. Ініціалізація даних за допомогою виразів та міток. Іменовані константи. Процедури та макрокоманди. Проблема локальних міток в макрокомандах та процедурах. Створення процедур на асемблері. Методика ефективного програмування. Опрацювання числових даних. Програмування розгалужень та вибору одного із кількох варіантів. Типи циклів та їх програмування. Опрацювання структурованих даних. Особливості основних версій мови асемблер. Відлагодження та тестування програм на рівні машинних команд. Технологія модульного програмування. Використання директиви SEGMENT. Базові директиви для оформлення та зв’язування модулів. Організація міжмодульних зв’язків з мовами високого рівня. Інтерфейс С – асемблер та методика змішаного програмування. 4. Робота з математичним співпроцесоромАрхітектура і типи даних FPU. Базові команди арифметики з рухомою комою. Команди керування роботою FPU. Цикли та розгалуження при роботі із співпроцесором. Програмування з використанням операцій обчислення математичних функцій.5. Використання і програмування стандартних функцій мов програмування та ОСЗахищений режим мікропроцесора і80х86. Структури даних захищеного режиму. Організація багатозадачності. Організація захисту коду програм та даних. Керування переключенням задач, пам’яттю та інформаційним обміном в захищеному режимі. 6. Мови високого рівня в системному програмуванніВикористання об’єктно-орієнтованого підходу для вирішення задач керування. Програмування мовою асемблер в середовищі WINDOWS. Системне програмування в сучасних ОС. Статистика роботи системних програм.7. Базові системні програми і ОСПоняття переривання та їх реалізація в сучасних процесорах. Характеристика системи переривань процесора i8086. Використання переривань при програмування вводу-виводу. Використання програмних та апаратних переривань. Синхронізуючі примітиви та їх використання. Проектування резидентних програм для MS-DOS. Використання буферизації для інформаційного обміну і опрацювання даних.8. Програмування типових елементів системних програмРобота з внутрішніми структурами даних інформаційних систем. Структури інформаційних таблиць. Основні функції, методи та алгоритми роботи з ними. Системи програмування. Характеристика компонент систем програмування. Узагальнена структура компіляції. Перегляди при компіляції. Теорія формальних мов. Лексичний, синтаксичний та семантичний аналіз. Проміжні форми представлення програм. Генерація коду. Сутність та види оптимізації. Методики створення компіляторів. Поняття віртуальної машини. Асемблери та їх структури даних. Основні функції систем асемблювання. Асемблери на один, два та багато переглядів вхідної програми. Загальні принципи компонування. Статичне та динамічне компонування виконуваних файлів. Неявне і явне зв'язування при динамічному компонуванні. Використання динамічної бібліотеки. Структура виконуваних файлів. Завантажувачі. Функції завантажувачів та їх типи.