Програма вступної фахової співбесіди на здобуття освітньо-кваліфікаційного рівня «Бакалавр» на базі освітньо-кваліфікаційного рівня «Молодший спеціаліст» за напрямом підготовки 6.050102 «Комп’ютерна інженерія» галузі знань 0501 «Інформатика та обчислювальна техніка»

ХЕРСОНСЬКИЙ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ

КАФЕДРА ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ

ЗАТВЕРДЖУЮ:

Голова приймальної комісії ХНТУ

«05» березня 2014р.

ПРОГРАМА

вступної фахової співбесіди

на здобуття освітньо-кваліфікаційного рівня «Бакалавр»

на базі освітньо-кваліфікаційного рівня «Молодший спеціаліст»

за напрямом підготовки 6.050102 «Комп’ютерна інженерія»

галузі знань 0501 «Інформатика та обчислювальна техніка»

	Програму схвалено методичною
	радою факультету кібернетики

Розглянуто на засіданні кафедри інформаційних технологій ХНТУ,

Херсон 2014

Програма вступної фахової співбесіди на здобуття освітньо-кваліфікаційного рівня «Бакалавр» на базі освітньо-кваліфікаційного рівня «Молодший спеціаліст» за напрямом підготовки 6.050102 «Комп’ютерна інженерія» галузі знань 0501 «Інформатика та обчислювальна техніка»

Укладачі: проф..В. Є.Ходаков, доцент

Рецензент: доцент

ЗАГАЛЬНІ ПОЛОЖЕННЯ

Програма розроблена на підставі Законів України «Про освіту» та «Про вищу освіту», Положення про приймальну комісію вищого навчального закладу, затвердженого наказом Міністерства освіти і науки України від 28.01.2008р. № 45, Положення про організацію навчального процесу у вищих навчальних закладах, затвердженого наказом Міністерства освіти і науки України від 2 червня 1993 р. № 000, Положення про організацію навчального процесу в Херсонському державному технічному університеті, затвердженого ректором 12 жовтня 2003р. та Положення про приймальну комісію Херсонського національного технічного університету.

Мета фахової вступної співбесіди полягає у діагностиці рівня теоретичних знань, практичних умінь та навичок абітурієнтів, необхідних для опанування нормативних і варіативних дисциплін за програмою підготовки фахівця освітньо-кваліфікаційного рівня «бакалавр з комп’ютерної інженерії».

Вимоги до здібностей і підготовленості абітурієнтів. Для успішного засвоєння дисциплін, передбачених навчальним планом підготовки фахівців освітньо-кваліфікаційного рівня «бакалавр з з комп’ютерної інженерії» абітурієнти повинні: мати освітньо-кваліфікаційний рівень «молодший спеціаліст» за спорідненою спеціальністю; володіти здібностями до засвоєння знань, умінь і навичок в галузі природничо-наукових, загальноекономічних та конкретно-економічних наук; вільно володіти державною мовою.

Характеристика змісту програми. Програма містить теоретичні питання з трьох змістових модулів, які відображають окремі аспекти напряму підготовки та інтегрує знання з декількох дисциплін, передбачених програмою підготовки молодших спеціалістів.

Організація проведення екзамену

Організація проведення фахової співбесіди визначається положенням про приймальну комісію ХНТУ. Для проведення фахової співбесіди наказом ректору ХНТУ створюється фахова комісія. Вступне випробування у формі співбесіди з кожним абітурієнтом проводять не менше двох членів комісії.

Фахова вступна співбесіда проводиться в усній формі. Абітурієнт отримує для відповіді білет, в якому визначені 3 питання з наведеного в програмі переліку. Тривалість підготовки абітурієнта до відповіді не повинна перевищувати 30 хвилин.

Під час співбесіди екзаменатори відмічають правильність відповідей в протоколі співбесіди, який по закінченню співбесіди підписується екзаменаторами та абітурієнтом.

Інформація про результати співбесіди оголошуються абітурієнту в день її проведення.

ЗМІСТ ПРОГРАМИ

Змістовий модуль 1. Програмування

Тема №1. «Лексичні елементи мови С».

Призначення та принцип дії препроцесора, компілятора, лінкера. Найпростіша програма на С. Структура програми. Директиви препроцесора define і include. Функція mаіт().Функції printf() і scanf(). Лексичні структури мови С. Ідентифікатори та зарезервовані слова. Константи цілого типу, плаваючого типу, символьного типу та рядкові. Управляючі коди. Правила побудови та використання. Операції мови С. Змінні і об'явлення. Операції привласнювання. Арифметичні операції. Операції відношення. Логічні операції. Побітові операції. Операція визначення розміру. Операція слідування. Пріоритет і порядок виконання операцій. Скалярні типи даних. Типи даних, діапазони значень і займані обсяги пам'яті. Ліво - та правоприпустимі вирази. Перерахування. Приведення та перетворення типів. Приведення типів. Перетворення типів при присвоюванні. Перетворення типів користувачем.

Тема №2 «Управляючі структури та покажчики».

Управляючі структури. Прості конструкції вибору. Види управляючих структур. Представлення алгоритма в вигляді блок-схеми. Пустий оператор. Блоки та составні оператори. Оператори if і if else. Конструкції вибору. Тернарна операція?:, оператор - перемикач switch. Оператор goto. Управляючі структури: ітераційні структури (цикли). Типи циклів. Оператори циклу while і do while. Універсальний оператор циклу for. Управління циклами за допомогою операторів break і continue. Організація лічильників і підрахування підсумків. Вкладені цикли. Масиви. Одномірні та двомірні масиви. Використання простих та вкладених циклів для обробки масивів. Класи пам'яті. Класи пам'яті та область дії змінних. Час життя змінної. Локальні та глобальні змінні. Автоматичні змінні. Регістрові змінні. Зовнішні змінні. Статичні змінні. Зовнішні статичні змінні. Покажчики. Визначення, призначення, синтаксис покажчиків. Алгоритм виконання операції зняття посилання. Операції над покажчиками. Динамічний розподіл пам'яті. Розподіл оперативної пам'яті для програми на Сі. Моделі пам'яті, які підтримує Typ6o(Borland) Сі. Особливості використання покажчиків в різних моделях пам'яті. Бібліотека alloc.h. Функції alloc(), cailocQ, malloc(). Правила використання, призначення. Особливості застосування покажчиків. Способи ініціації покажчиків. Особливості використання покажчиків. Покажчики та масиви. Особливості використання покажчиків. Зв'язок між покажчиками та масивами. Арифметичні дії над покажчиками та масивами. Особливості використання масивів. Ініціація одновимірних масивів. Рядки та багатовимірні масиви. Символьні масиви (рядки) - особливості, призначення, використання. Функції введення-виведення рядків. Багатовимірні масиви. Ініціація багатовимірних масивів - структурна та безструктурна. Покажчики та багатовимірні масиви. Вільні масиви рядків. Правила вживання вільних масивів.

Тема №3 «Функції та складні структури даних».

Основні відомості про функції. Поняття функції. Представлення функції. Формальні та фактичні параметри. Обмін між функціями. Повернення значення функцією. Оператор return. Передача параметрів за значенням та за посиланням. Особливі функції. Функція main(). Параметри функції main(). Рекурсивні функції. Чотири способи виклику функцій. Структури. Призначення та визначення структур. Визначення структурного шаблона. Структурні змінні. Доступ до полів структури. Операції над структурами. Ініціація структур. Структури, що містять структури. Зв'язок між структурами, функціями та масивами. Особливі типи структур. Передача структур в функцію. Структури як значення, що повертається функцією. Створення масивів структур. Ініціація масивів структур. Бітові поля. Об'єднання union.

Тема №4 «Введення-виведення в С та препроцесор».

Організація введення-виведення в С. Стандартне введення-виведення в С. Потоки введення-виведення, текстові та двійкові потоки. Переадресація введення-виведення. Структура типу FILE. Функції відкриття та закриття файлів fopen(), fclose(). Посимвольне введення-виведення файла. Програмування з використанням файлів. Ім'я файлу як аргумент командного рядка. Форматоване введення-виведення файлу функції fprintf() і fscanfQ.Функції рядкового введення-виведення файлів fgets() і fputs(), читання-запису файла fread() і fwrite(). Прямий доступ до файла - функція fseek(). Перевірка та перетворення символів. Принцип побудови функцій перевірки та перетворення символів. Функції перевірки символів. Функції управління регістрами. Функції перетворення рядків в числа. Числа як аргументи командного рядка. Функції роботи з рядками. Препроцесор мови С. Використання директив препроцесора. Директиви препроцесора для підстановки імен. Директиви препроцесора для включення файлів. Директиви препроцесора для умовної компіляції.

Змістовий модуль 2. Прикладна теорія цифрових автоматів

Тема 1. Булеві функції (БФ) та їх нормальні форми. Оптимізація булевих функцій.

Вступ до дисципліни. Булеві функції. Основні поняття теорії булевих функцій (БФ). Засоби завдання БФ: табличний та аналітичний. Область визначення БФ від n змінних. змінних. Число різноманітних БФ від n змінних. БФ однієї і двох змінних. Булева алгебра (БА). Основні і похідні тотожності БА та їх доведення. Узагальнення основних тотожностей БА. Алгебра Жигалкіна (АЖ). Взаємозв'язок операцій БА й АЖ.. Елементарні диз’юнкції і кон’юнкції. ДНФ і КНФ. Алгоритми приведення будь-якого виразу БА до ДНФ і КНФ. Констітуенти 0 і 1, їхні властивості. ДДНФ і ДКНФ. Алгоритми приведення будь-якого виразу БА до ДДНФ і ДКНФ. Побудова ДДНФ і ДКНФ БФ, що задані таблицею. Функціонально повні системи БФ. Лема про розклад БФ по змінній та її наслідок. Залишкові функції. Представлення будь-якої БФ через диз'юнкцію, кон’юнкцію і заперечення. Теорема про функціональну повноту деяких систем бф. Передповні класи бф, теорема про їх замкнутість та приватність. Теорема Поста про функціональну повноту. Використання теореми Поста для синтезу комбінаційних схем. Мінімізація БФ. Канонічна задача мінімізації БФ. Основні поняття: імпліканта, проста імпліканта, повна та приведена системи імплікант, скорочена, тупікова та мінімальна днф. Теорема Квайна про зв’язок мінімальної та тупікової днф. Загальна схема вирішення канонічної задачі мінімізації БФ. Еврестичний метод розв’язання задач другого етапу мінімізації БФ: імплікантна таблиця, ядро БФ, знаходження тупикових і мінімальної ДНФ. Метод Петрика вирішення задач другого етапу мінімізації БФ. Основні методи розв’язання задач першого етапу мінімізації БФ: метод Квайна, метод Блейка, метод Нельсона.

Тема 2. Виконання алгебраїчних операцій в ЕОМ. Cистеми числення. Перетворення чисел з однієї системи числення в іншу. Представлення двійкових чисел в ЕОМ із фіксованою і плаваючою комою. Прямий код. Додатковий код. Обернений код.

Cистеми числення. Основні поняття. Класифікація систем числення. Код Грея. Кодовані позиційні системи числення. Системи залишкових класів. Перетворення чисел з однієї системи числення в іншу. Двійкова система числення. Навички роботи з двійковими числами Представлення двійкових чисел в ЕОМ із фіксованою і плаваючою комою. Прямий код. Представлення чисел у прямому коді. Додавання чисел у прямому коді. Додатковий код. Представлення чисел у (модифікованому) додатковому коді. Додавання чисел у (модифікованому) додатковому коді. Обернений код. Представлення чисел в оберненому коді. Додавання чисел в оберненому коді. Операція зсуву.

Тема 3. Функціонально повні системи БФ. Інформаційні основи цифрових автоматів.

Графічні методи мінімізації БФ: діаграми Вейча (карти Карно). Проблема факторизації. Факторний алгоритм. Мінімізація систем бф. Інформаційні основи цифрових автоматів.

Основні підходи до вивчення явищ навколишнього середовищаз інформаційного точку зору: дискретний та безперервний. Універсальність алфавітного способу задання інформації. Поняття про перетворення інформації. Алфавітні оператори і проблема їхнього задання. Поняття про абстрактний автомат.

Тема 4. Абстрактна теорія автоматів.

Абстрактні автомати (аа) 1-го та 2-го роду. Еквівалентність та ізоморфність аа. Автомати Милі і Мура. Способи задання аа: табличний і графовий. Інтерпретація автоматів І-го роду як автоматів 2-го роду. Часткові автомати. Автоматні відображення і їхнї властивості. Теорема Хафмена-Мілі. Способи задання автоматних відображень. Алгебра подій. Алгебра регулярних подій. Теорема Кліні про зв'язок абстрактних автоматів і подій. Мінімізація абстрактних автоматів.

Тема 5. Структурна теорія автоматів.

Структурна теорія автоматів. Основні поняття і відмінності структурної теорії автоматів від абстрактної теорії. Основна задача структурної теорії автоматів. Теорема про структурну повноту. Канонічний метод структурного синтезу автоматів з пам’яттю.

Змістовий модуль 3. Комп’ютерна схемотехніка

Тема 1. Загальні питання організації функціонування ЕОМ. Принципи побудови цифрових ЕОМ. Операційні пристрої. Концепція керуючого та операційного автоматів.

Ієрархічний і модульний принципи побудови ЕОМ. Класифікація ЕОМ. Поняття про функціональну і структурну організацію ЕОМ. Класи пристроїв ЕОМ. Концепція єдиного інтерфейсу і каналу введення-виведення. Концепція керуючиго і операційного автоматів. Система утворюючих алгоритму.

Тема 2. Операційні вузли цифрових ЕОМ та їх синтез: комбінаційні схем на їх синтез на мікросхемах різного ступеню інтеграції, синтез тригерів та регістрів.

Знаходження восьми нормальних форм бф та її операторного представлення. Побудова КС в заданому елементному базисі. Порівняння отриманих КС по швидкодії і затратам обладнання. Побудова перетворювача кодів на логічних елементах. Вплив систем мікрооперацій і логічних умов на характеристики операційних пристроїв. Задача проектування операційних пристроїв і методи її рішення. Побудова перетворювача кодів з використанням дешифратора. Побудова КС, що реалізує задану бф з використанням мультиплексора.

Класифікація тригерів. Формулювання задачі проектування тригерів і методи її розв’язання. Вибір запам’ятовуючого елементу з внутрішньою затримкою (побудованого по MS-схемі з інвертором у ланцюзі сінхросигнала, по MS-схемі зі зв'язками, що забороняються, за схемою трьох елементарних тригерів). Побудова повної таблиці переходів тригера. Приклади синтезу тригерів.

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

Тема 3. Операційні вузли цифрових ЕОМ та їх синтез: синтез лічильників та суматорів.

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

Тема 4. Структурна організація і синтез керуючих автоматів операційних пристроїв

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

Тема 5. Структурна організація і синтез операційних автоматів операційних пристроїв

Структурний базис ОА: шини (керуємі шини), регістри, комбінаційні схеми. Канонічна структура ОА і її синтез в заданому структурному базисі, виходячи з функцій, реалізація яких покладається на автомат. Функціонування ОА в часі. Характеристики ОА: продуктивність, швидкодія, затрати обладнання, регулярність, універсальність. Властивості канонічних структур ОА. Явище гонок. Проскок станів. Еквівалентні мікрооперації й узагальнені оператори. Структури, що реалізують узагальнені оператори. Синтез ОА з структурою І-автомату, що реалізує операції множення і ділення. Структура і властивості М-автоматів. Забезпечення стійкості М-автоматів. Розподілення регістрів по шинам. Визначення форматів і значень слів М-автомату. Визначення операторів, що реалізуються М-автоматом. Кодування мікрооперацій наборами керуючих сигналів. Визначення класів еквівалентних мікрооперацій. Побудова структурної схеми М-автомата, що реалізує операції множення і ділення. Розширювачі комбінаційної частини М-автомату. Побудова закодованого графа мікропрограми, що пов’язаний з М-автоматом. Засоби обчислення логічних значень.

ІМ-автомати з паралельною комбінаційною частиною та їх синтез. Області застосування ІМ-автоматів з паралельною і послідовною комбінаційними частинами. Способи підвищення швидкодії S-автоматів.

Тема 6. Методи проектування операційних пристроїв цифрових ЕОМ з «жорсткою» логікою (як композиції із зворотнім зв’язком керуючого і операційного автоматів).

Проектування і дослідження операційних пристроїв, що реалізують операцію алгебраїчного додавання (у прямих, обернених та додаткових кодах). Проектування і дослідження операційних пристроїв, що реалізують операцію множення методом накопичення часткових добутків (чотири схеми). Проектування і дослідження операційних пристроїв, що реалізують операцію ділення з відновленням і без відновлення залишків.

Тема 7. Керуючі автомати цифрових ЕОМ з логікою, що програмується (з «м’якою» логікою) та їх синтез.

Керуючі автомати цифрових ЕОМ з логікою, що програмується (з «м’якою» логікою) та їх синтез.

Програмування.

1. Історія виникнення, класифікація, сучасний стан мов програмування. Місце мови Сі серед сучасних мов програмування. Етапи розробки програми. Виконання програми на Сі – препроцесор, компілятор, завантажник.

2. Використання пам'яті в програмі на Сі. Моделі пам'яті. Покажчики: призначення, синтаксис, приклади. Операції над покажчиками. Ініціалізація покажчиків.

3. Використання функцій у програмі на Сі. Передача параметрів функції й повернення значення функцією. Формальні й фактичні параметри. Передача параметрів за значенням і за посиланням. Параметри функції main(). Рекурсивні функції.

4. Структура типової програми на Сі. Лексичні елементи мови Сі. Операції: види, правила виконання, приклади. Ідентифікатори й зарезервовані слова. Константи. Пріоритет і порядок виконання операцій. Приведення й перетворення типів.

5. Керуючі структури Сі. Порожній і складений оператори. Конструкції вибору. Цикли. Приклади.

6. Використання структур у програмі на Сі. Структурний шаблон і структурні змінні. Доступ до полів структури. Передача структур у функції. Бітові поля. Об'єднання. Приклади.

7. Файлове введення-виведення у Сі. Потоки. Структура типу FILE. Відкриття і закриття файлу. Посимвольне й порядкове введення-виведення файлу. Прямий доступ до файлу. Приклади.

8. Препроцесор Сі. Директиви препроцесора для включення файлів, підстановки імен, умовної компіляції. Приклади.

9. Використання масивів у програмі на Сі. Одномірні й багатомірні масиви. Зв'язок між покажчиками і масивами. Вільні масиви. Особливості використання масивів символів. Приклади.

10. Використання змінних в Сі. Типи даних й займані обсяги пам'яті. Локальні і глобальні Змінні. Класи пам'яті. Автоматичні, реєстрові, зовнішні, статичні, зовнішні статичні змінні. Приклади.

Прикладна теорія цифрових автоматів.

1. Бульові функції (БФ). Основні поняття теорії БФ. Область визначення БФ від n змінних. Число різноманітних БФ від n змінних. Засоби завдання БФ: табличний та аналітичний. БФ однієї і двох змінних. Приклади.

2. Класифікація систем числення. Основні поняття. Приклади.

3. Перетворення чисел з однієї системи числення в іншу. Приклади.

4. Двійкова система числення. Навички роботи з двійковими числами. Приклади.

5. Представлення двійкових чисел в ЕОМ з фіксованою комою і комою, що плаває.

6. Прямий код. Додавання чисел у прямому коді. Приклади.

7. Додатковий код. Додавання чисел у (модифікованому) додатковому коді. Приклади.

8. Обернений код. Додавання чисел в (модифікованому) оберненому коді. Приклади.

9. Операція зсуву. Приклади.

10. Додавання чисел у машинах із комою, що плаває. Приклади.

11. Загальні відомості про операцію множення. Приклади.

12. Множення, шо виконується методом накопичення часткових добутків. Приклади.

13. Множення чисел, що задані у додатковому коді. Приклади.

14. Ділення чисел без відновлення залишків. Приклади.

15.

16. Бульова алгебра. Основні визначення. Основні та похідні тотожності БА. Приклади.

17. Алгебра Жигалкіна (АЖ). Взаємозв'язок операцій БА й АЖ.

18. Нормальні форми в БА: елементарні кон’юнкції і ДНФ. Приклади. Алгоритм приведення будь-якого виразу БА до ДНФ. Приклади.

19. Нормальні форми в БА: елементарні диз’юнкції, КНФ. Приклади. Алгоритм приведення будь-якого виразу БА до КНФ.

20. Констітуенти 0 і 1, їхні властивості. Приклади. ДДНФ і ДКНФ. Приклади.

21. Алгоритм приведення будь-якого виразу БА до ДДНФ. Приклади.

22. Алгоритм приведення будь-якого виразу БА до ДКНФ. Приклади.

23. Побудова ДДНФ і ДКНФ БФ, що задані таблично. Приклади.

24. Функціонально повні системи БФ. Лема про розкладання БФ по змінній та її наслідки.

25. Представлення будь-якої БФ через диз'юнкцію, кон’юнкцію і заперечення.

26. Теорема про функціональну повноту деяких важливих систем БФ.

27. Передповні класи БФ, теорема про їх замкнутість та приватність.

28. Теорема Поста про функціональну повноту.

29. Канонічна задача мінімізації БФ. Основні поняття: імпліканта, проста імпліканта, повна та приведена системи простих імплікант. Скорочена, тупікова та мінімальна ДНФ. Приклади.

30. Теорема Квайна про зв’язок мінімальної та тупікової ДНФ та її наслідок. Приклади.

31. Основні методи розв’язання задач першого етапу мінімізації БФ: метод Квайна. Приклади.

32. Основні методи розв’язання задач першого етапу мінімізації БФ: метод Блейка. Приклади.

33. Основні методи розв’язання задач першого етапу мінімізації БФ: метод Нельсона. Приклади.

34. Основні методи розв’язання задач другого етапу мінімізації БФ: імплікантна таблиця. Приклади.

35. Основні методи розв’язання задач другого етапу мінімізації БФ: Метод Петрика. Приклади.

36. Графічні методи мінімізації БФ: діаграми Вейча (карти Карно). Приклади.

37. Проблема факторизації. Факторний алгоритм. Приклади.

38. Мінімізація систем БФ. Приклади.

39. Інформаційні основи цифрових автоматів. Основні підходи до вивчення явищ навколишнього середовищаз інформаційного точку зору: дискретний та безперервний. Універсальність алфавітного способу задання інформації. Поняття про перетворення інформації. Алфавітні оператори і проблема їхнього задання.

40. Поняття про абстрактний автомат. Абстрактні автомати 1-го та 2-го роду. Еквівалентність абстрактних автоматів. Інтерпретація автоматів роду як автоматів роду.

41. Автомати Мілі і Мура. Способи завдання абстрактних автоматів Мілі і Мура: табличний і графовий. Приклади.

42. Автоматні відображення і їхнї властивості. Теорема Хафмена-Мілі.

43. Способи задання автоматних відображень. Події. Теорема про зв’язок каночної множини подій і автоматних відображень.

44. Алгебра подій.

45. Алгебра регулярних подій. Теорема Кліні про зв'язок абстрактних автоматів і регулярних подій.

46. Структурна теорія автоматів. Основні поняття і відмінності структурної теорії автоматів від абстрактної теорії.

47. Теорема про структурну повноту.

Комп’ютерна схемотехніка

1. Принцип мікропрограмного управління. Концепція операційного і керуючого автоматів. Вплив систем мікрооперацій і логічних умов на характеристики операційних пристроїв. Система утворюючих алгоритму. Структурна реалізації мікрооперацій і логічних умов. Різноманіття операційних пристроїв.

2. Задача проектування операційних пристроїв і концепція функціонального мікропрограмування. Мова функціонального мікропрограмування. Мікрооперації (класифікація і сумісність). Логічні умови. Змістовний граф мікропрограми. Приклади функціональних мікропрограм: мікропрограма множення двійкових чисел у машинах з фіксованою комою починаючи з молодших розрядів множника зі зсувом суми часткових добутків вправо; мікропрограма ділення двійкових чисел у машинах з фіксованою комою без відновлення залишку.

3. Функція операційного автомату і її визначення. Закодований граф мікропрограми. Функція керуючого автомату і її визначення. Об'єднаний граф мікропрограми. Приклади.

4. Структурний базис: шини (мультиплексори), регістри, комбінаційні схеми. Канонічна структура операційного автомату і її синтез. Приклад канонічної структури операційного автомату, що реалізує операції множення і ділення. Операційний автомат як композиція операційних елементів.

5. Функціонування операційного автомату в часі. Характеристики операційного автомату: продуктивність, швидкодія, витрати устаткування, регулярність, універсальність. Властивості канонічних структур операційних автоматів. Забезпечення стійкості функціонування операційного автомату: явище гонок, проскакування станів. Часова діаграма операційного пристрою.

6. Еквівалентні мікрооперації й узагальнені оператори. Структурна організація і синтез І–автоматів. Приклади.

7. Структурна організація і синтез М–автоматів. Забезпечення стійкості М-автоматів. Приклади.

8. Структурна організація і синтез IM-автоматів з паралельною комбінаційною частиною. Приклади.

9. Структурна організація і синтез IM-автоматів з послідовною комбінаційною частиною. Приклади. Область застосування IM-автоматів з паралельною і послідовною комбінаційною частиною.

10. Використання запам’ятовуючих пристроїв у пам’яті автомату і клас S-автоматів. Способи підвищення швидкодії S-автоматів.

11. Тригери та їх синтез. Приклади.

12. Регістри. Метод синтезу синхронних регістрів на синхронних тригерах. Приклади.

13. Регістри. Метод синтезу синхронних регістрів на асинхронних тригерах. Приклади.

14. Регістри. Метод синтезу асинхронних регістрів на синхронних тригерах. Приклади.

15. Регістри. Метод синтезу асинхронних регістрів на асинхронних тригерах. Приклади.

16. Лічильники. Метод синтезу лічильника з довільним коефіціентом перерахунку та довільним порядком рахунку. Приклади.

17. Лічильники. Метод синтезу лічильника з коефіціентом перерахунку К≠2n, у якого вилучені стани, що слідують підряд. Приклади.

18. Лічильники. Метод синтезу кільцевого лічильника на зсуваючих регістрах. Приклади.

19. Суматори. Однорозрядні суматори та їх синтез. Метод синтезу комбінаційного двійково-десяткового суматору, що додає дві десяткові цифри у двійковій системі числення із штучними вагами розрядів. Приклади.

20. Синтезувати в “жорсткій” логіці - як композицію із зворотнім зв’язком керуючого і операційного автоматів - 4-розрядний операційний пристрій з фіксованою комою, що

a. реалізує функцію D=2*A2+0,5*B;

b. керуючий автомат синтезувати як автомат Мура з використанням логічних елементів І-НІ і D-тригерів;

c. операційний автомат побудувати згідно із структурною схемою, представленою на рисунку 2.2 лабораторної роботи №6.

21. Синтезувати в “жорсткій” логіці - як композицію із зворотнім зв’язком керуючого і операційного автоматів - 4-розрядний операційний пристрій з фіксованою комою, що

a. реалізує функцію D=2*A2+0,5*B;

b. керуючий автомат синтезувати як автомат Мілі з використанням логічних елементів І-НІ і Т-тригерів;

c. операційний автомат побудувати згідно із структурною схемою, представленою на рисунку 2.2 лабораторної роботи №6.

22. Синтезувати в “жорсткій” логіці - як композицію із зворотнім зв’язком керуючого і операційного автоматів - 4-розрядний операційний пристрій з фіксованою комою, що

a. реалізує операцію алгебраїчного додавання-віднімання чисел, представлених у прямому коді;

b. керуючий автомат синтезувати як автомат Мілі з використанням логічних елементів І-НІ і Т-тригерів;

c. операційний автомат побудувати згідно із структурною схемою, представленою на рисунку 2.11 лабораторної роботи №7.

23. Синтезувати в “жорсткій” логіці - як композицію із зворотнім зв’язком керуючого і операційного автоматів - 4-розрядний операційний пристрій з фіксованою комою, що

a. реалізує операцію алгебраїчного додавання-віднімання чисел, представлених у прямому коді;

b. керуючий автомат синтезувати як автомат Мура з використанням логічних елементів І-НІ і D-тригерів;

c. операційний автомат побудувати згідно із структурною схемою, представленою на рисунку 2.11 лабораторної роботи №7

24. Синтезувати в “жорсткій” логіці - як композицію із зворотнім зв’язком керуючого і операційного автоматів - 4-розрядний операційний пристрій з фіксованою комою, що

a. реалізує операцію додавання-віднімання чисел, представлених у додатковому коді;

b. керуючий автомат синтезувати як автомат Мілі з використанням логічних елементів І-НІ і JK-тригерів;

c. операційний автомат побудувати згідно із структурною схемою, представленою на рисунку 2.13 лабораторної роботи №7.

25. Синтезувати в “жорсткій” логіці - як композицію із зворотнім зв’язком керуючого і операційного автоматів - 4-розрядний операційний пристрій з фіксованою комою, що

a. реалізує операцію додавання-віднімання чисел, представлених у додатковому коді;

b. керуючий автомат синтезувати як автомат Мура з використанням логічних елементів І-НІ і RS-тригерів;

c. операційний автомат побудувати згідно із структурною схемою, представленою на рисунку 2.13 лабораторної роботи №7.

26. Синтезувати в “жорсткій” логіці - як композицію із зворотнім зв’язком керуючого і операційного автоматів - 4-розрядний операційний пристрій з фіксованою комою, що

a. реалізує операцію множення чисел, представлених у прямому коді, згідно з наступною схемою множення чисел:

Ci+1 = Ci +Ai+1*bi+1, Ai+1=Ai*2-1 , (при i=0, A0=A, C0=0);

b. керуючий автомат синтезувати як автомат Мура з використанням логічних елементів І-НІ і RS-тригерів;

c. операційний автомат побудувати згідно із структурною схемою, представленою на рисунку 2.17 (г) лабораторної роботи №8.

27. Синтезувати в “жорсткій” логіці - як композицію із зворотнім зв’язком керуючого і операційного автоматів - 4-розрядний операційний пристрій з фіксованою комою, що

a. реалізує операцію додавання-віднімання чисел, представлених у додатковому коді;

b. керуючий автомат синтезувати як автомат Мілі з використанням логічних елементів І-НІ і JK-тригерів;

c. операційний автомат побудувати згідно із структурною схемою, представленою на рисунку 2.15 лабораторної роботи №7, що реалізує операції алгебраїчного додавання-віднімання в послідовних додаткових кодах.

28. Синтезувати в “жорсткій” логіці - як композицію із зворотнім зв’язком керуючого і операційного автоматів - 4-розрядний операційний пристрій з фіксованою комою, що

a. реалізує операцію додавання-віднімання чисел, представлених у додатковому коді;

b. керуючий автомат синтезувати як автомат Мура з використанням логічних елементів І-НІ і RS-тригерів;

c. операційний автомат побудувати згідно із структурною схемою, представленою на рисунку 2.15 лабораторної роботи №7, що реалізує операції алгебраїчного додавання-віднімання в послідовних додаткових кодах.

29. Синтезувати в “жорсткій” логіці - як композицію із зворотнім зв’язком керуючого і операційного автоматів - 4-розрядний операційний пристрій з фіксованою комою, що

a. реалізує операцію множення чисел, представлених у прямому коді, згідно з наступною схемою множення чисел:

Ci+1 = Ci +Ai+1*bi+1, Ai+1=Ai*2-1 , (при i=0, A0=A, C0=0);

b. керуючий автомат синтезувати як автомат Мілі з використанням логічних елементів І-НІ і JK-тригерів;

c. операційний автомат побудувати згідно із структурною схемою, представленою на рисунку 2.17 (г) лабораторної роботи №8.

30. Синтезувати в “жорсткій” логіці - як композицію із зворотнім зв’язком керуючого і операційного автоматів - 4-розрядний операційний пристрій з фіксованою комою, що

a. реалізує операцію множення чисел, представлених у прямому коді, згідно з наступною схемою множення чисел:

Ci+1 = (Ci+A*bi+1)*2, (при i=0, C0=0);

b. керуючий автомат синтезувати як автомат Мура з використанням логічних елементів І-НІ і T-тригерів;

c. операційний автомат побудувати згідно із структурною схемою, представленою на рисунку 2.17 (в) лабораторної роботи №8.

31. Синтезувати в “жорсткій” логіці - як композицію із зворотнім зв’язком керуючого і операційного автоматів - 4-розрядний операційний пристрій з фіксованою комою, що

a. реалізує операцію множення чисел, представлених у прямому коді, згідно з наступною схемою множення чисел:

Ci+1 = (Ci+A*bi+1)*2, (при i=0, C0=0);

b. керуючий автомат синтезувати як автомат Мілі з використанням логічних елементів І-НІ і D-тригерів;

c. операційний автомат побудувати згідно із структурною схемою, представленою на рисунку 2.17 (в) лабораторної роботи №8.

32. Синтезувати в “жорсткій” логіці - як композицію із зворотнім зв’язком керуючого і операційного автоматів - 4-розрядний операційний пристрій з фіксованою комою, що

a. реалізує операцію множення чисел, представлених у прямому коді, згідно з наступною схемою множення чисел:

Ci+1 = Ci+Ai*bn-і, Ai=2*Ai-1, (при i=0, C0=0, A0=A);

b. керуючий автомат синтезувати як автомат Мура з використанням логічних елементів І-НІ і T-тригерів;

c. операційний автомат побудувати згідно із структурною схемою, представленою на рисунку 2.17 (б) лабораторної роботи №8.

33. Синтезувати в “жорсткій” логіці - як композицію із зворотнім зв’язком керуючого і операційного автоматів - 4-розрядний операційний пристрій з фіксованою комою, що

a. реалізує операцію множення чисел, представлених у прямому коді, згідно з наступною схемою множення чисел:

Ci+1 = Ci+Ai*bn-і, Ai=2*Ai-1, (при i=0, C0=0, A0=A);

b. керуючий автомат синтезувати як автомат Мілі з використанням логічних елементів І-НІ і D-тригерів;

c. операційний автомат побудувати згідно із структурною схемою, представленою на рисунку 2.17 (б) лабораторної роботи №8.

34. Синтезувати в “жорсткій” логіці - як композицію із зворотнім зв’язком керуючого і операційного автоматів - 4-розрядний операційний пристрій з фіксованою комою, що

a. реалізує операцію множення чисел, представлених у прямому коді, згідно з наступною схемою множення чисел:

Ci+1 = (Ci+A*bn-і)*2-1 , (при i=0, C0=0);

b. керуючий автомат синтезувати як автомат Мілі з використанням логічних елементів І-НІ і RS-тригерів;

c. операційний автомат побудувати згідно із структурною схемою, представленою на рисунку 2.17 (а) лабораторної роботи №8.

35. Синтезувати в “жорсткій” логіці - як композицію із зворотнім зв’язком керуючого і операційного автоматів - 4-розрядний операційний пристрій з фіксованою комою, що

a. реалізує операцію множення чисел, представлених у прямому коді, згідно з наступною схемою множення чисел:

Ci+1 = (Ci+A*bn-і)*2-1 , (при i=0, C0=0);

b. керуючий автомат синтезувати як автомат Мура з використанням логічних елементів І-НІ і JK-тригерів;

c. операційний автомат побудувати згідно із структурною схемою, представленою на рисунку 2.17 (а) лабораторної роботи №8.

36. Синтезувати в “жорсткій” логіці - як композицію із зворотнім зв’язком керуючого і операційного автоматів - 4-розрядний операційний пристрій з фіксованою комою, що

a. реалізує операцію ділення з відновленням залишків чисел, представлених у прямому коді;

b. керуючий автомат синтезувати як автомат Мілі з використанням логічних елементів І-НІ і D-тригерів;

c. операційний автомат побудувати згідно із структурною схемою, представленою на рисунку 2.20 лабораторної роботи №9.

37. Синтезувати в “жорсткій” логіці - як композицію із зворотнім зв’язком керуючого і операційного автоматів - 4-розрядний операційний пристрій з фіксованою комою, що

a. реалізує операцію ділення з відновленням залишків чисел, представлених у прямому коді;

b. керуючий автомат синтезувати як автомат Мура з використанням логічних елементів І-НІ і Т-тригерів;

c. операційний автомат побудувати згідно із структурною схемою, представленою на рисунку 2.20 лабораторної роботи №9.

38. Синтезувати в “жорсткій” логіці - як композицію із зворотнім зв’язком керуючого і операційного автоматів - 4-розрядний операційний пристрій з фіксованою комою, що

a. реалізує операцію ділення без відновлення залишків чисел, представлених у прямому коді;

b. керуючий автомат синтезувати як автомат Мілі з використанням логічних елементів І-НІ і JK-тригерів;

c. операційний автомат побудувати згідно із структурною схемою, представленою на рисунку 2.21 лабораторної роботи №9.

39. Синтезувати в “жорсткій” логіці - як композицію із зворотнім зв’язком керуючого і операційного автоматів - 4-розрядний операційний пристрій з фіксованою комою, що

a. реалізує операцію ділення без відновлення залишків чисел, представлених у прямому коді;

b. керуючий автомат синтезувати як автомат Мура з використанням логічних елементів І-НІ і RS-тригерів;

c. операційний автомат побудувати згідно із структурною схемою, представленою на наступному рисунку 2.21 лабораторної роботи №9.

40. Керуючі автомати з логікою, що програмується. Мікрокоманди та їх структура. Постійні запам’ятовуючі пристрої: їх структура та функціонування.

41. Структура і функціонування керуючого автомату з примусовою адресацією.

42. Розподіл мікрооперацій по операційним полям мікрокоманди: метод прямого включення. Приклади.

43. Визначення кількості операційних полів мікрокоманди. Кодування наборів мікрооперацій. Перетворення кодів мікрокоманд за допомогою додаткового постійного запам’ятовуючого пристрою.

44. Примусова адресація мікрокоманд. Формування адреси мікрокоманди за допомогою додаткового лічильника.

45. Природна адресація мікрокоманд. Операційні і керуючі мікрокоманди та їх структура. Автомат з природною адресацією мікрокоманд та алгоритм його функціонування.

46. Сегментація постійних запам’ятовуючих пристроїв. Обробка сегментованих адрес при примусовій адресації.

47. Сегментація постійних запам’ятовуючих пристроїв. Обробка сегментованих адрес при природній адресації.

48. Формування адрес мікрокоманд при організації складних переходів, що залежать від значень декількох логічних умов. Приклади.

49. Структурні методи підвищення швидкодії автоматів: паралельна вибірка мікрокоманд. Керуючий автомат з паралельною вибіркою мікрокоманд. Мікропрограма обробки паралельно вибраних мікрокоманд.

50. Структурні методи підвищення швидкодії автоматів: випереджаюча вибірка мікрокоманд. Діаграма функціонування операційного пристрою. Порівняння характеристик керуючих автоматів з “жорсткою” і “м’якою” логікою.

В процесі співбесіди абітурієнт має виявити достатній рівень набутих знань і вмінь. Підсумкова оцінка за результатами вступної фахової співбесіди визначається за шкалою від 100 до 200 балів за наступними критеріями.

КРИТЕРІЇ ОЦІНЮВАННЯ ВІДПОВІДЕЙ

191-200 балів абітурієнт отримує, виявивши такі знання та вміння:

· повне, логічне та послідовне розкриття змісту матеріалу, поставленого завдання

· вільне володіння спеціальною термінологією

· досконале застосування одержаних знань, умінь та навичок з різних дисциплін для правильного вирішення всіх поставлених завдань.

161-190 балів абітурієнт отримує, виявивши такі знання та вміння:

· послідовне розкриття змісту матеріалу, поставленого завдання

· вільне володіння спеціальною термінологією, можливі деякі неточності

· в основному правильне застосування одержаних знань, умінь та навичок з різних дисциплін для вирішення більшості поставлених питань.

124 – 160 балів абітурієнт отримує, виявивши такі знання та вміння:

· зміст питань викладено частково, не завжди послідовно

· у відповідях є помилки у використанні окремих понять

· при вирішенні поставленого завдання абітурієнт не розуміє шляхів практичного використання одержаних знань

100 – 123 бали абітурієнт отримує, виявивши такі знання та вміння:

· основний зміст завдання не розкрито

· допущені грубі помилки у відповідях

· відсутнє володіння спеціальною термінологією.

У разі використання заборонених джерел абітурієнт на вимогу члена комісії залишає аудиторію та одержує загальну нульову оцінку.

СПИСОК РЕКОМЕНДОВАНОЇ ЛІТЕРАТУРИ

Основна література

1. Язык программирования С. - М.: Радио и связь, 1988. – 96 с.

2. Язык программирования С. – М.: Финансы и статистика, 19992. – 271 с.

3. , Березин курс С и С++. – М.: ДИАЛОГ – МИФИ, 1998.

4. , и др. Прикладная теория цифровых автоматов. - Киев: Вища школа, 1987. – 396 с.

5. Савельев теория цифровых автоматов.- М.: Высшая школа, 1987. – 272 с.

6. , , Тарасенко ЭВМ. - К.: Вища шк., 1989. – 423 с.

7. , Новиков организации цифровых машин. - Л.: Машиностроение, 1974. – 432 с.

8. Баранов микропрограммных автоматов. - Л.: Энергия, 1979.-232с.

9. , , Жабин ЭВМ. Практикум. - К.: Вища шк., 19с.

Додаткова література

1. Автоматы. - М.: Мир, 19с.

2. Глушков цифровых автоматов. - М.: Физматгиз, 19с.

3. , , Кузняк . Киев: Технiка, 1986.

4. Аппаратние средства РС. 3-е издание. Дюссельдорф, Киев, Москва, Санкт-Петербург. – Изд-во «БХВ - Санкт-Петербург». – 1999