Комп’ютерна логіка (частина 1)

1.

Комп’ютерна логіка (частина 1)
Національний університет «Львівська
політехніка»
Слайдів
281

2. Лекція 1

• Вступ - мета та задачі курсу
• Організаційні питання
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
2

3. консультації – після закінчення аудиторних занять за розкладом викладача 503-V (каф. ЕОМ) або за домовленістю

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
3

4. Комп’ютерна логіка

• ЛОГІКА - наука про закони і різновиди мислення, способи пізнання
та умови істинності знань і суджень
• КОМП’ЮТЕР – пристрій для передавання, зберігання та оброблення
інформації
• КОМП'ЮТЕРНА ЛОГІКА - умовна назва області досліджень, що
ставиться до прикладної логіки, у якій логічні методи застосовуються
для обробки даних і знань у комп'ютерних системах, при створенні
системних програм, що забезпечують функціонування ЕОМ, при
автоматизації програмування й при створенні ЕОМ нових поколінь. К.
л. може виступати як сукупність засобів для імітації пізнавальних
процесів у комп'ютерних системах з підвищеним рівнем
інтелектуальних можливостей, забезпечуючи пошук необхідних знань
для досягнення обраної мети й процес виводу результату, що
відповідає цієї мети.
• КОМП'ЮТЕРНА ЛОГІКА – наука про закони і різновиди мислення,
якими користуються люди, коли описують роботу комп’ютерів та
працюють з ними (проектують, ремонтують, обслуговують,
користуються)
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
4

5. Національний університет “Львівська політехніка”

ІАРХ
ІБІД
ІГДГ
ІГСН
ІДН
ІЕПТ
ІНЕМ
ІЕСК
ІІМТ
ІКНІ
ІКТА
МІОК
ІППТ
ІПДО
ІНПП
ІМФН
ІТРЕ
ІХХТ
НУЛП 20192020 н.р.
Архітектури
Будівництва та інженерії довкілля
Геодезії
Гуманітарних та соціальних наук
Дистанційного навчання
Екології, природоохоронної діяльності та туризму ім. В’ячеслава
Чорновола
Економіки і менеджменту
Енергетики та систем керування
Інженерної механіки та транспорту
Комп'ютерних наук та інформаційних технологій
Комп'ютерних технологій, автоматики та метрології
Міжнародний інститут освіти, культури та зв’язків з діаспорою
Підприємництва та перспективних технологій
Післядипломної освіти
Права та психології
Прикладної математики та фундаментальних наук
Телекомунікацій, радіоелектроніки та електронної техніки
Хімії та хімічних технологій
Глухов В.С. Комп'ютерна логіка
5

6. Комп'ютерних технологій, автоматики та метрології

БІТ
ЕОМ
ЗІ
ІВТ
Кафедра безпеки інформаційних технологій
Кафедра електронних обчислювальних машин
Кафедра захисту інформації
Кафедра інформаційно-вимірювальних
технологій
КСА
Кафедра комп'ютеризованих систем
автоматики
МСС
Кафедра метрології, стандартизації та
сертифікації
ПТМ
Кафедра приладів точної механіки
СКС
Кафедра спеціалізованих комп'ютерних систем
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
6

7. Комп’ютерна інженерія і комп’ютерні науки

• material science – матеріалознавство
• natural science – природознавство
• computer science – комп’ютерознавство
• engineering – машинобудування
• material engineering – створення нових матеріалів
• computer engineering – створення нових
комп’ютерів
• program engineering – створення нових програм
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
7

8. Кафедри ЕОМ та СКС

• Бакалаврат (каф. ЕОМ та СКС) Комп’ютерна інженерія
• Магістри (спеціалізації каф. ЕОМ)
– Комп’ютерні системи та мережі
– Кіберфізичні системи
– Системне програмування
• Магістри (спеціалізація каф. СКС)
– Спеціалізовані комп’ютерні системи
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
8

9. Структура семестру

• 15 навчальних тижнів (15 лекцій, 7-8
практичних)
• Заліковий тиждень
• Сесія (2 тижні)
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
9

10. Державна оцінка (залік)

• 1. За результатами семестрової контрольної
роботи
• 2а. Оцінка на комісії
– або
• 2б. Оцінка за результатами повторного
вивчення курсу
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
10

11. Стандартні вимоги до відповідей на заліках та іспитах – цього року немає

• Повинна бути дана відповідь на усі питання
білету
• Під час підготовки до відповіді нічим не
можна користуватися
• Під час підготовки до відповіді ні с ким не
можна перемовлятися та обмінюватися
інформацією
• Для допуску до сесії потрібно виконати
навчальний план
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
11

12. Виконання навчального плану

• Студент погоджується самостійно опрацювати деякі
питання учбового плану
• Здана розрахункова робота (є оцінка)
• Виконано програму практичних занять
• Написано усі 15 лекційних контрольних робіт
• Дано відповідь на усі 10 питань семестрової контрольної
роботи
• Є конспект лекцій (приблизно 5 сторінок на лекцію)
• Правильно дано відповіді на усі питання тестів до 1-ої
частини Комп’ютерної логіки (1-ий курс) у ВНС
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
12

13. Полегшені умови отримання семестрової оцінки

• Білет семестрової контрольної роботи видається
достроково до початку 15-го навчального тижня
за умови:
–
–
–
–
Виконано розрахункову роботу
За практичні заняття отримано більше 20 балів (з 30)
Написано усі лекційні контрольні роботи на дану дату
Правильно дано відповіді на усі питання тестів до 1-ої
частини Комп’ютерної логіки (1-ий курс) у ВНС
– Є конспект лекцій (приблизно 5 сторінок на лекцію)
• Під час підготовки до відповіді дозволяється
користуватися чим завгодно
• Повинна бути дана відповідь на всі питання
білету
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
13

14. Оцінювання відповідей при стандартному підході – цього року не буде

Оцінка 100; Оцінка практичні 25; Оцінка ЛекційніКР 5; Оцінка білет 70
Оцінка Оцінка практичні Оцінка ЛекційніКР Оцінка білет
Оцінювання відповідей при полегшеному підході на заліку:
Оцінка Оцінка поточний контрольі
Сума балів ЛекційніКР * Сума балів за тести
N * 100
* Оцінка білет
Оцінка 100; Оцінка поточний контроль 30; Сума балів ЛекційніКР N ; Оцінка білет 70;
Сума балів за тести 100; N L * 5 , L кількість лекцій
Оцінювання відповідей при пол-егшеному підході на комісії
(якщо сума балів за лекційні контрольні роботи більше N/2) і
при повторному вивченні:
Оцінка
Сума балів ЛекційніКР * Сума балів за тести
N * 100
* Сума оцінок за бітети
Оцінка 100; Сума балів ЛекційніКР N ; Оцінка білет 100;
Сума балів за тести 100; N L * 5 , L кількість лекцій
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
14

15. Покращення оцінок

• Було 51 бал – 51% від 100 балів
(поточний контроль – 1 з 30, іспит - 50 з 70,
3% з 30 за поточку і 71% з 70 за іспит)
• Хоче “добре” (71 бал – 71% від 100 балів)
• Тоді треба набрати спочатку за поточний
контроль 71% від 30 = 21 бал,
а після того -71% від 70 =50 балів за іспит.
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
15

16. Вихід з особливих ситуацій

• Оформлення академвідпустки в деканаті
(до початку сесії)
• Оформлення
індивідуального
графіку
навчання в деканаті
• Продовження сесії в деканаті
• Довідка викладачу про роботу за
спеціальністю
–
поважна
причина
відсутності на парах
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
16

17. Методичні вказівки до курсової роботи “Арифметичні та логічні основи комп’ютерних технологій” з дисципліни "Комп’ютерна логіка"

Методичні вказівки до курсової роботи “Арифметичні та
логічні основи комп’ютерних технологій” з дисципліни
"Комп’ютерна логіка"
ВСТУП
ЗАВДАННЯ НА РОБОТУ, ВКАЗІВКИ ЩОДО ВИБОРУ ВАРІАНТА РОБОТИ
1 МЕТОДИЧНІ ВКАЗІВКИ ЩОДО КОДУВАННЯ ІНФОРМАЦІЇ ТА ПЕРЕТВОРЕННЯ
КОДІВ
1.1 W1
1.1.1. Переведення чисел до десяткової системи числення з іншої однорідної позиційної системи
числення з основою k, коли дії виконуються в десятковій системі
1.1.2. Переведення чисел із десяткової системи числення до іншої однорідної позиційної системи
числення з основою k, коли дії виконуються в десятковій системі
1.1.3. Переведення цілої частини числа
1.1.4. Переведення дробової частини числа
1.1.5. Переведення чисел з шістнадцяткової й вісімкової систем до двійкової і зворотне переведення
чисел
1.2 W2 Ефективне кодування. Система залишкових класів
1.2.1. Алгоритм ефективного кодування Шеннона – Фано
1.2.2. Ентропія.
1.2.3. Система залишкових класів
1.3 Код Геммінга
1.4 Визначення помилкових станів при зміні двійкових кодів
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
17

18. Методичні вказівки до курсової роботи “Арифметичні та логічні основи комп’ютерних технологій” з дисципліни "Комп’ютерна логіка"

Методичні вказівки до курсової роботи “Арифметичні та
логічні основи комп’ютерних технологій” з дисципліни
"Комп’ютерна логіка"
• 2 МЕТОДИЧНІ ВКАЗІВКИ ЩОДО
ВИКОРИСТАННЯ ФУНКЦІЙ АЛГЕБРИ
ЛОГІКИ ТА МІНІМІЗАЦІЇ ЦИХ ФУНКЦІЙ У
БАЗИСІ БУЛЯ
• 2.1 Функціональна повнота системи функцій
алгебри логіки і наборів логічних елементів
• 2.2 Мінімізація функцій методом КвайнаМакКласкі-Петрика
• 2.3 Мінімізація функцій за допомогою карт Карно
• 2.4 Визначення сполучного терма
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
18

19. Розрахункова робота

№ п.п.
Частина роботи
1
Отримання
завдання.
Задачі
Граничний термін здачі –
даної
практичне заняття на
частини
навчальному тижні
семестру
Максимальна
кількість
балів
1, 2
2
1
1, 2
3, 4
2
3
1
3, 4
5, 6
2
4
1
5, 6
7, 8
2
5
2
1
9,10
1
6
2
2
11,12
1
7
2
3
13,14
1
8
2
4
15
1
Усього
10
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
19

20. Робочий журнал

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
20

21. Відробка пропущених лекційних контрольних робіт

• Копія конспекту за пропущену лекцію
(якщо у журналі є порожня клітинка або Н)
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
21

22. Віртуальне Навчальне Середовище - ВНС

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
22

23. Тема у ВНС

НУЛП 20192020 н.р.
Системний
адміністратор [email protected]
ІКТА
Глухов В.С. Комп'ютерна логіка
23

24. Білет семестрової контрольної роботи

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
24

25. Конспект

• Поле – для важливих приміток (дата, №
лекції, № питання, NB, …)
• Основна частина – для скороченого запису
помилок, які робить викладач
– Графічна частина
– Текстові пояснення
• Знизу - № сторінки, Прізвище І.П.
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
25

26. Основні компетенції

• Досвід планування власного часу
• Досвід дотримання встановлених правил
• Вміння не заважати при цьому іншим
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
26

27. Внаслідок вивчення навчальної дисципліни студент повинен бути здатним продемонструвати такі результати навчання, а саме знати

та використовувати :
інформаційні основи комп’ютерної логіки;
методи представлення чисел в ЦА;
правила переведення чисел з однієї системи числення до іншої;
алгоритми виконання основних арифметичних і логічних операцій в
ЦА;
правила виконання арифметичних і логічних операцій у різних
системах числення;
основи формальної логіки;
форми запису логічних виразів;
основи синтезу і мінімізації функцій алгебри логіки у різних базисах;
правила створення схем електричних функціональних логічних вузлів
цифрових схем;
базові комбінаційні логічні вузли цифрової техніки;
методи і засоби контролю і діагностики логічних схем.
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
27

28. Підготовлений фахівець повинен вміти:

• записувати, читати і розуміти логічні
вирази;
• аналізувати і синтезувати ЦА в різних
логічних базисах;
• володіти методами мінімізації логічних
виразів;
• застосовувати набуті знання в практичній
діяльності.
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
28

29. Вивчення навчальної дисципліни передбачає формування та розвиток у студентів компетенцій (підтвердженого досвіду): загальних:

З письмової комунікації (на рівні передавання складної інформації);
З усної комунікації (на рівні передавання складних повідомлень);
Здатність спілкуватися першою (рідною) мовою, вміння правильно, логічно, ясно будувати своє усне й
писемне мовлення;
Володіння необхідними навичками професійного спілкування другою (іноземною) мовою;
Знання та розуміння предметної галузі, професії; основних концепцій, базових категорій, технічних
понять;
Здатність до безперервного та активного навчання, самоосвіти, постійного підвищення кваліфікаціі;
Аналітичного мислення (на рівні застосування загального аналізу);
абстрактного мислення, аналізу та синтезу;
міжособистісного спілкування; уміння працювати в команді, мотивувати людей та досягати спільної
мети; розуміння та повага до різноманітності та мультикультурності;
дій з урахуванням соціальної відповідальності та громадянських зобов’язань, з повагою ставитися до
права й закону;
визначення, формулювати та розв’язувати задачі, аналізу соціально-значущі процеси та приймати
обґрунтовані рішення;
Розв’язання проблем (на рівні розв’язання складних проблем);
Планування та організації (на рівні планування та організація багатокомпонентної складної діяльності);
Критичного мислення (на рівні формулювання загальних стратегій з багатовимірних стратегічних
питань);
розуміння значення інформації в сучасному суспільстві, відповідально ставитися до питань
інформаційної безпеки;
Уміння знаходити, обробляти та аналізувати інформацію з різноманітних джерел; здатність
використовувати інформаційно-комунікативні технології.
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
29

30. Фахових компетенцій (фаховий досвід):

Знання дискретних структур і вміння застосовувати сучасні методи дискретної математики для
аналізу і синтезу складних систем виконання кодування інформаційних повідомлень, у тому числі
користуючись методами побудови завадозахисних кодів та кодами Хеммінга;
застосування теоретичних (логічних та арифметичних) основ побудови сучасних комп’ютерів та
їх архітектури при рішенні професійних завдань.
Складання логічних виразів;
Читання і розуміння логічних виразів;
Спрощення логічних виразів;
Розроблення комбінаційних схем для реалізації системи перемикальних функцій у заданому
елементному базисі, сформулювавши задачу її побудови у термінах теорії перемикальних
функцій, виконавши мінімізацію функцій та отримавши необхідні операторні форми з
урахуванням засобів уникнення збою в схемах;
Виконання абстрактний синтезу цифрового автомата, зробивши формальний опис алгоритму його
функціонування у термінах теорії цифрових автоматів та виконавши процедуру мінімізації числа
станів автомата;
Виконання структурного синтезу синхронних та асинхронних автоматів, застосовуючи способи
мінімізації функцій збудження та виходів, а також уникнення збоїв в умовах використання для
побудови схеми автомата заданого елементного базису, в тому числі інтегральних схем, що
програмуються;
Розроблення алгоритмів функціонування арифметичного пристрою на підставі форми
представлення інформації, алгоритмів виконання арифметичних операцій в різних системах
числення в умовах застосування методів контролю роботи пристрою з використанням систем
автоматизованого проектування комп’ютерних засобів.
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
30

31. Результати навчання даної дисципліни деталізують такі програмні результати навчання:

Уміння застосовувати знання у практичних ситуаціях.
Уміння адаптуватись до нових ситуацій
Уміння ефективно працювати як автономно, так і у складі команди.
Уміння відповідально ставитись до виконуваної роботи та досягти поставленої мети
Уміння застосовувати знання і розуміння для розв’язання задач синтезу та аналізу цифрових вузлів.
Уміння спілкуватись включаючи усну та письмову комунікацію українською мовою та однією з іноземних мов
(англійською, французькою, німецькою).
Уміння використовувати інформаційні і комунікаційні технології для вирішення різних дослідницьких і
професійних завдань.
Уміння здійснювати пошук інформації в різних джерелах для розв’язання задач спеціальності.
Уміння приймати обґрунтовані рішення та оцінювати їх наслідки.
Уміння використовувати базові знання основ філософії, психології, педагогіки в професійній і соціальній
діяльності.
Уміння сприймати критику, критикувати особистість, самокритично відноситись до своїх поступків та
критикувати результати роботи.
Уміння дотримуватися кодексу професійної етики, керуватися в поведінці моральними нормами та цінностями,
дотримуватися правил етикету.
Уміння застосовувати сучасні методи дискретної математики для аналізу, синтезу та проектування цифрових
вузлів.
Уміння застосовувати базові знання стандартів в області інформаційних технологій під час розробки цифрових
вузлів.
Уміння обробляти отримані результати, аналізувати та осмислювати їх, представляти результати роботи і
обґрунтовувати запропоновані рішення на сучасному науково-технічному і професійному рівні
Уміння застосовувати комп’ютерніі засоби при проектуванні та створенні цифрових вузлів.
Уміння опановувати та розробляти документацію на системи, продукти і сервіси інформаційних технологій,
спілкуватись рідною мовою, професійно спілкуватись англійською мовою.
Підготовленість до використання існуючих та розроблення нових математичних методів для вирішення задач,
пов’язаних
НУЛП
2019- з проектуванням цифрових вузлів.
31
Глухов В.С. Комп'ютерна логіка
2020 н.р.

32. Досвід (компетенції) випускників

• конвертувати академічні знання і навички в результати
практичного вирішення технічних задач;
• вирішувати складні задачі в галузі комп'ютерної техніки
та ефективно адаптуватися у швидко мінливому
середовищі;
• використовувати систематичний і методичний стиль
роботи;
• застосовувати правильну термінологію і позначення як у
письмовій формі так і в усній;
• обговорювати основні теорії та методи аналізу і обробки
аналогових і цифрових сигналів з використанням
правильної термінології;
• застосувати знання математики та фізики (у тому числі
теорії ймовірності, статистики та дискретної математики,
диференціального та інтегрального числення), інші
досягнення науки і техніки;
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
32

33. Досвід (компетенції) випускників

• визначити, формулювати та проводити дослідження,
направлені на вирішення інженерної завдачі за допомогою
відповідного огляду літератури, робити обгрунтовані
висновки;
• планувати і проводити експерименти та тести, а також
аналізувати та інтерпретувати отримані експериментальні
дані та робити обґрунтовані висновки;
• критично мислити, аналізувати і приймати рішення, які
належним чином враховують глобальні проблеми в
–
–
–
–
–
НУЛП 20192020 н.р.
бізнесі,
етиці,
моралі,
суспільстві і
навколишньому середовищі;
Глухов В.С. Комп'ютерна логіка
33

34. Досвід (компетенції) випускників

• проектувати комп’ютерні системи, компоненти або
процеси для задоволення бажаних потреб в рамках
реалістичних обмежень:
–
–
–
–
–
–
–
–
НУЛП 20192020 н.р.
економічних,
екологічних,
соціальних,
політичних,
етичних,
здоров'я та безпеки,
технологічності і
стійкості;
Глухов В.С. Комп'ютерна логіка
34

35. Досвід (компетенції) випускників

• розробляти та реалізовувати апаратні засоби або
програмне забезпечення системи вбудованих компонентів
для задоволення бажаних потреб та вимог, у тому числі:
–
–
–
–
–
–
–
–
НУЛП 20192020 н.р.
продуктивності,
економічної ефективності,
безпеки,
маса-габаритних характеристик,
часу,
споживання,
ефективності і
ергономічності та ефективності користувальницьких інтерфейсів;
Глухов В.С. Комп'ютерна логіка
35

36. Досвід (компетенції) випускників

• розуміти вплив технічних рішень в соціальному контексті
і бути в змозі ефективно реагувати на потреби сталого
розвитку суспільства;
• бути в змозі оцінити можливості та обмеження теорій та
методів, застосовуваних на практиці;
• працювати в команді;
• ефективно працювати в рамках міждисциплінарних
команд, у тому числі вміння працювати з колегами для
того, щоб розробити і побудувати комплексну
комп’ютерну систему;
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
36

37. Досвід (компетенції) випускників

• розуміти фундаментальні засади ефективного управління проектами;
• визначити, формулювати і вирішувати технічні задачі;
• обговорювати концепції створення комп’ютерних системи та мереж,
особливостей використання Інтернет-технологій;
• визначати необхідність, проектувати, впроваджувати та оцінювати
життєздатність рішень для вбудованих комп’ютерних систем, що
працюють у реальному часі;
• виявляти, формулювати, аналізувати і створювати інженерні рішення
з використанням відповідних сучасних технологій, методів та
інструментів, в тому числі і з міжперсональним спілкуванням;
• доводи доцільність та правильність обраних теорій, методів, дизайну
та реалізацій;
• пояснювати та відстоювати методичний та системний підхід до
проектування;
• аргументувати вибрані рішення та пояснювати їхні обмеження;
• оцінювати сильні і слабкі сторони різних рішень і тестів;
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
37

38. Досвід (компетенції) випускників

• підтримувати проектування для забезпеченням заданої
функціональності
за
допомогою
розрахунків,
моделювання та імплементації результатів моделювання;
• комбінувати
варіанти
об'єднання
апаратного
і
програмного забезпечення для отримання бажаної
функціональності комп’ютерної системи;
• комбінувати загальнотехнічні та специфічні рішення при
роботі з комп’ютерними системами;
• представляти
результати
досліджень
у
вигляді
презентацій, публікації та / або доповідях на конференціях
та семінарах;
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
38

39. Досвід (компетенції) випускників

• демонструвати розуміння та дотримуватися професійних
та етичних обов'язків;
• мати уявлення, розуміти необхідність та дотримуватися
особистої чесності, професійної етики та культурної
свідомості;
• розуміти і нести професійну, етичну і моральну
відповідальність;
• ефективно спілкуватися та обмінюватися технічною
інформацією в різних форматах і різними способами
(усно, письмово, електронними засобами) як із
спеціалістами так і з неспеціалістами в галузі
Комп’ютерної інженерії;
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
39

40. Досвід (компетенції) випускників

визначити власні потреби в навчанні і планувати та здійснювати своє власне
навчання в різних середовищах навчання;
самостійно набувати ширшої освіти, необхідної для розуміння впливу
інженерних рішень в
–
–
–
–
глобальному,
економічному,
екологічному та
соціальному значеннях;
визнавати необхідність і здатність займатися самоосвітою протягом усього
життя;
розвиватися і підтримувати на належному сучасному рівні необхідні знання, а
також відповідний рівень компетентності в сучасних наукових технологіях
так, щоб бути в змозі формулювати і вирішувати нові технічні задачі і далі
розвивати і підтримувати свої професійні навички впродовж усієї кар'єри;
розуміти необхідність, прагнути до безперервного навчання, бути
винахідливим і здатним прийняти глобальні виклики та використати всі
можливості, щоб зробити позитивний вплив на суспільство;
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
40

41. Досвід (компетенції) випускників

• демонструвати знання сучасних проблем;
• розуміти і використовувати методи, навички та сучасні
інженерні інструменти необхідні для інженерної практики
з відповідними міркуваннями щодо забезпечення:
–
–
–
–
–
НУЛП 20192020 н.р.
громадського здоров'я та безпеки,
культурних,
соціальних,
моральних,
екологічних обмежень.
Глухов В.С. Комп'ютерна логіка
41

42. Спеціальний досвід (компетенції) випускників

• Проектування вбудованих комп'ютерні систем
для
–
–
–
–
–
–
НУЛП 20192020 н.р.
споживчих товарах
медичних пристроях
системи керування для автомобілів, літаків і поїздів
телекомунікацій,
фінансових операцій,
інформаційних систем
Глухов В.С. Комп'ютерна логіка
42

43. Спеціальний досвід (компетенції) випускників

апаратно-програмні інтерфейси;
проектування НВІС;
проектування цифрових, аналогових та змішаних схем;
автоматизація проектування;
тестування та діагностика;
комп’ютерні мережі;
вбудовані комп’ютерні системи;
розробка програмного забезпечення для широкого кола
задач;
• кібер-фізичні системи;
• мови програмування: JAVA, C++, C, Assembly, VHDL,
Matlab, Python;
• операційні системи Android, iOS, UNIX, Linux, Windows.
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
43

44. Придбані в ВНЗ навички, що стали в нагоді в найбільшій мірі у професійній діяльності (Head Hunter Україна, 2017)

• 49% респондентів відзначили вміння знаходити
вихід з будь-якої ситуації
• 46% відзначили корисним навиком критичне
мислення
• 41% - вміння знаходити підхід до різних людей
• 39% заявили про важливість теоретичних знань
• 25% - практичних навичок
• 22% - робота в команді,
• 18% - навички самопрезентації
• 15% - правильного управління часом
• 13% - університетські контакти
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
44

45. Зарплати розробників України - вересень 2018 https://https://dou.ua/lenta/articles/salary-report-june-july-2018/?from=special

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
45

46. Зарплати розробників у Львові - вересень 2018 https://https://dou.ua/lenta/articles/salary-report-june-july-2018/?from=special

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
46

47. Популярність мов програмування

2018
2015
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
47

48. Зарплаты Java, C# и C++ разработчиков (Украина, Львов, 2018 г.)

Зарплаты Java, C# и C++ разработчиков (Украина, Львов, 2018 г.)
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
48

49. Зарплаты Java Android и Java не-Android разработчиков (Украина, 2018 г.)

Зарплаты Java Android и Java не-Android разработчиков
(Украина, 2018 г.)
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
49

50. Зарплаты сисадминов и DevOps-инженеров (2018 р)

Зарплаты сисадминов и DevOps-инженеров (2018 р)
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
50

51. Розподіл по предметних областях

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
51

52. Зарплати випускників вузів (2018 р)

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
52

53. Зарплаты студентов вузов, 2018 г.

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
53

54. Динамика зарплат, Java

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
54

55. Динамика зарплат, C#/.NET

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
55

56. Динамика зарплат, C++

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
56

57. Динамика зарплат, JavaScript

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
57

58. Динамика зарплат, QA (quality assurance - гарантія якості)

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
58

59. У Львові приблизно 150 IT-компаній (Інформаційні Технології) 50 найбільших IT-компаній України (що працюють у Львові, 2018 р.)

№
Компания
Специалисты в Украине
Δ 01.01/07.31
Технические
специалисты
Вакансии в
Украине
1
EPAM
5500
+700
4900
128
2
SoftServe
4863
+258
3896
200
4
GlobalLogic
3367
+362
3107
355
5
Ciklumzz
2456
-37
2124
238
6
Infopulse
1614
+153
1301
115
8
DataArt
1230
+84
1097
143
9
ELEKS
1192
+37
952
54
11
ZONE3000
1000
+100
250
49
15
Sigma/Software
847
+67
667
104
16
Intellias
820
+160
720
80
18
N-iX
745
+75
670
71
19
Plarium
723
+3
297
9
20
Lohika
718
+48
573
31
22
ISD
700
650
10
24
GeeksForLess/Inc.
646
+15
593
15
29
Gameloft
600
-50
32
Oracle
505
+2
34
Svitla/Systems, Inc.
500
39
TemplateMonster
420
46
CoreValue
50
Intetics/Inc.
НУЛП 20192020 н.р.
26
455
14
400
50
+20
210
15
376
+20
314
19
320
+20
263
58
Глухов В.С. Комп'ютерна логіка
59

60. GlobalLogic

Cписок вимог, на які в компанії GlobalLogic звертається особлива увага при
відборі:
Профільна технічна освіта
Математичний склад розуму
Англійська на рівні Pre-intermediate - Intermediate+
Базові знання мов програмування - C та C++
Знання алгоритмів
Розуміння особливостей структур даних
Навички роботи з “залізом”
Знання теорії операційних систем - основні компоненти ОС
Розуміння стандартної системи роботи з проектами і досвід роботи з
класичним тулсетом девелопера (Git, Jira)
Практичний досвід (лабораторні роботи, курсові, виконані практичні заняття
на базі STM, власні проекти з посиланням на Git, де їх можна переглянути)
буде великим плюсом
Вміння швидко вчитись
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
60

61. Комп’ютерна логіка і „Комп’ютерна інженерія”

Архітектура
комп'ютерів
Комп’ютерні
системи
Комп'ютерна
схемотехніка
Теорія
алгоритмів
Програмування
Комп’ютерна
логіка
Математика
Фізика
Комп'ютерна
електроніка
НУЛП 20192020 н.р.
Філософія
Глухов В.С. Комп'ютерна логіка
61

62. Лінгвістичні основи – грецька абетка

Α α — альфа
Γ γ — гамма
Ε ε — епсилон
Η η — ета
Ι ι — йота
Λ λ — лямбда
Ν ν — ню
Ο ο — омікрон
Ρ ρ — ро
Τ τ — тау
Φ φ — фі
Ψ ψ — псі
НУЛП 20192020 н.р.
Β β — бета
Δ δ — дельта
Ζ ζ — дзета
Θ θ — тета
Κ κ — каппа
Μ μ — мю
Ξ ξ — ксі
Π π — пі
Σ σ ς — сигма
Υ υ — іпсилон
Χ χ — хі
Ω ω — омега
Глухов В.С. Комп'ютерна логіка
62

63. Лінгвістичні основи – латинська абетка

Літера
Aa
Bb
Cc
Dd
Ee
Ff
Gg
Hh
Ii
Jj
Kk
Ll
Mm
НУЛП 20192020 н.р.
Назва
а
бе
це
де
е
еф
ґе, же
га, аш
і
йот, жі
ка
ель
ем
Літера
Nn
Oo
Pp
Qq
Rr
Ss
Tt
те
Uu
Vv
Ww
Xx
Yy
Zz
Назва
ен
о
пе
ку
ер
ес
у
ве
дубль ве
ікс
іпсилон, ігрек
зет (зета)
Глухов В.С. Комп'ютерна логіка
63

64. Математичні основи Просте число — це натуральне число, яке має рівно два різних натуральних дільники (лише 1 і саме число).

• 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61,
67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113 , 127, 131,
137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193,
197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263,
269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337,
347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409,
419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479,
487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569,
571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641,
643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719,
727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809,
811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881,
883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971,
977, 983, 991, 997…
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
64

65. Таблиця множення

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
65

66. Математичні основи

(m + n)·k = m·k + n·k - дистрибутивний закон
(a+b)+c=a+(b+c) – асоціативний закон
ab=ba – комутативний закон
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
66

67. Математичні основи

n! = 1 ⋅ 2 ⋅ 3 ⋅ ... ⋅ (n − 1) ⋅ n
НУЛП 20192020 н.р.
0! = 1
Глухов В.С. Комп'ютерна логіка
67

68. Математичні основи – математичні константи

e i 1 0
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
68

69. Математичні основи – модульна арифметика

Два цілих числа a і b називаються рівними (конгруентними)
за модулем n, якщо при цілочисельному діленні на n вони
мають однакові залишки. Рівність чисел a і b за модулем n
записують так:
Еквівалентні визначення:
Різниця a-b ділиться на n націло. Тобто a - b = kn, де k —
якесь ціле число.
Число a може бути записано у вигляді a = b + kn, де k —
якесь ціле число.
Nmod(±M)=±R
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
69

70. Системи числення

8 2
3
16 2
4
16 2 4
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
70

71. Позиційні системи числення

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
71

72. Степені 2

10-ва
система
числення
2n
2-ва система
16-ва
числення
система
числення
1024
512
256
128
64
32
16
8
4
2
1
0,5
0,25
0,125
0,0625
0,03125
0,015625
0,007813
0,003906
0,001953
0,000977
10000000000
1000000000
100000000
10000000
1000000
100000
10000
1000
100
10
1
0,1
0,01
0,001
0,0001
0,00001
0,000001
0,0000001
0,00000001
0,000000001
0,0000000001
n
10
9
8
7
6
5
4
3
2
1
0
-1
-2
-3
-4
-5
-6
-7
-8
-9
-10
НУЛП 20192020 н.р.
400
200
100
80
40
20
10
8
4
2
1
0,8
0,4
0,2
0,1
0,08
0,04
0,02
0,01
0,008
0,004
8-ва
система
числення
Степені 2
2000
1000
400
200
100
40
20
10
4
2
1
0,4
0,2
0,1
0,04
0,02
0,01
0,004
0,002
0,001
0,0004
Глухов В.С. Комп'ютерна логіка
72

73. Фізичні основи

Напруга U (В), струм I (А), потужність P (Вт),
опір R (Ом), ємність C (Ф), індуктивність L (Гн)
Закон Ома I = U/R
Потужність P = UI
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
73

74. Основи електроніки

Транзистори – біполярні та польові
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
74

75. Швидкість, продуктивність

• v=F/t (F – шлях, об’єм води, кількість
операцій, кількість інформації, …)
• v=(Fк-Fп)/(tк-tп)=ΔF/ Δt
• Δt →0 => dt
• v=dF/ dt – перша похідна
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
75

76. Філософські основи

• Матерія - філософська категорія для позначення
об'єктивної реальності, яка дана людині у відчуттях її, яка
копіюється, фотографується, відображується нашими
відчуттями, існуючи незалежно від них
• Катего́рія — загальне філософське поняття, яке
відображає універсальні властивості і відношення
об'єктивної дійсності, загальні закономірності розвитку
всіх матеріальних, природних і духовних явищ.
• Діале́ктика (грец. διαλεκτική — «мистецтво сперечатись»,
«міркувати») — метод філософії, що досліджує категорії
розвитку.
• Атрибут – невід’ємна характеристика
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
76

77. Матерія

Атрибути
Властивості
Види
Форми руху
Простір
об'єктивність
Речовина
Механічний
Час
вічність
Поле
Фізичний
Рух
нестворенність
Хімічний
Інформація
взаємодія
Біологічний
інші
відображення
інші
Матерія
інші
Основні закони діалектики
Закон єдності і боротьби протилежностей
Закон взаємного переходу кількісних змін у якісні
Закон заперечення заперечення
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
77

78. Відображення

• Відобра́ження — загальна властивість, що
виявляється в здатності матеріальних систем
відтворювати визначеність інших матеріальних
систем у формі зміни власної визначеності в
процесі взаємодії з ними.
• Приватними
і
специфічними
формами
відображення є інформація, відчуття і свідомість.
• Загальне поняття інформації подано у філософії,
де під нею розуміють відображення реального
світу.
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
78

79. Інформація

• Інформація - Відомості про факти, концепції, об'єкти,
події та ідеї, які в даному контексті мають цілком певне
значення (ДСТУ ISO/IEC 2382-5:2005 Інформаційні
технології. Словник термінів. Частина 5. Подання даних)
• Інформація – це поняття, що пов'язано з об'єктивною
властивістю матеріальних об'єктів і явищ (процесів)
породжувати різноманіття станів, які за допомогою
взаємодії (фундаментальні взаємодії) передаються до
інших об'єктів та відображаються в їх структурі. (В.М.
Глушков, М.М. Амосов «Енциклопедія кібернетики»,
Київ. 1975 р.)
• Конце́пція (лат. conceptio — розуміння) — система
поглядів, те або інше розуміння явищ і процесів; єдиний,
визначальний задум.
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
79

80. Стандарти AAAA NNNN-Ч:YYYY

Стандарт
Стандарти підприємства
Галузеві стандарти
Державні (національні) стандарти:
Державний стандарт України
Государственный стандарт (СРСР, до 1992 р.),
Міждержавний стандарт (СНД, з 1992 р.)
Государственный стандарт (Росія, з 1992 р.)
Американська організація стандртизації
Стандарти Німеччини
Міжнародні стандарти:
Міжнародна організація стандартизації
Міжнародна електротехнічна комісія
Міжнародний інститут інженерів електриків
НУЛП 20192020 н.р.
Позначення
(AAAA)
СТП
ГСТ
Приорітет
0 (найнижчий)
1
2
ДСТУ
ГОСТ
ГОСТ Р
ASA
DIN
3 (найвищий)
ISO
IEC
IEEE
Глухов В.С. Комп'ютерна логіка
80

81. Властивості інформації

Інформація
Властивості
Скінченість у просторі
Скінченість у часі
Цінність
Старіння
Розсіювання
інші
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
81

82. Комп’ютерна логіка у системі наук інформаційної сфери

Наука і техніка
Матерія
Речовина
Інформація
Поле
Отримання
Збереження
Перетворення
Пересилання
Комп’ютерна
логіка
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
82

83. Структурна схема процесу передачі або оброблення інформації

Джерело
інформації
Кодер
джерела
інформації
Кодер
захисту
інформації
Кодер
каналу /
обчислювача
Джерело
завад
Приймач
інформації
НУЛП 20192020 н.р.
Декодер
приймача
інформації
Декодер
захисту
інформації
Декодер
каналу /
обчислювача
Глухов В.С. Комп'ютерна логіка
Модулятор
Канал /
обчислювач
Демодулятор
83

84. Кодек, Модем

• Кодек = кодер + декодер
• Модем = Модулятор + демодулятор
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
84

85. Баланс швидкостей

vi = vi1+vi2+…+vin
vo = vo1+vo2+…+von
Повинно бути: vi ≤ vo .
Інакше швидкість заповнення пам’яті буде
v = vi -vo > 0
Джерело
інформації
1
Джерело
інформації
2
...
Джерело
інформації
n
НУЛП 20192020 н.р.
ti1
F
ti2
tin
V
to1
Приймач
інформації
1
to2
Приймач
інформації
2
...
tom
Приймач
інформації
m
Глухов В.С. Комп'ютерна логіка
85

86. Функції кодера джерела інформації

Джерело
інформації
1.
2.
3.
НУЛП 20192020 н.р.
Інформація
Кодер
джерела
інформації
Дані
Код
Кодер
захисту
інформації
Перетворення неелектричних величин в електричні
Перетворення інформації в дані - аналого-цифрове
перетворення інформації
Усунення
надлишковості
інформації
Глухов В.С. Комп'ютерна логіка
86

87. Дані

• Дані - Інформація, представлена у вигляді, придатному для обробки
автоматичними засобами при можливій участі людини
• Дискретний - Визначення, що відноситься до даних, представлених
окремими елементами, наприклад, знаками або фізичними величинами,
які приймають кінцеве число цілком певних значень
• Числовий - Визначення, що відноситься до даних, які складаються з
чисел
• Цифровий - Визначення, що відноситься до даних, які складаються з
цифр
• Аналоговий - Визначення, що відноситься до даних, які представлені
безперервними значеннями будь-якої фізичної змінної
ДСТУ 3044-95 ПОДАННЯ ДАНИХ Терміни та визначення
ISO/IEC/IEEE 24765-2010 Systems and software engineering — Vocabulary
ISO/IEC 2382:2015 Information technology — Vocabulary
ДСТУ ISO/IEC 2382-5:2005 Інформаційні технології. Словник термінів.
Частина 5. Подання даних
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
87

88. Кодування

• Кодування даних Кодування
Процес побудови даних з елементів скінченої множини за
встановленими правилами
• кодовий набір
Скінчена множина елементів, з яких будують дані при
кодуванні
• алфавіт
Кодовий набір, в якому встановлено відношення порядку
• кодон
Елемент кодового набору
• Код даних Код
Система, утворена кодовим набором і правилами, за
якими з елементів цього кодового набору будують дані
при кодуванні
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
88

89. Сигнал та повідомлення

• Фізичне явище, наявність, відсутність або
зміна якого представляє Дані.
• Сигнал - матеріальний носій інформації, який
використовується для передачі повідомлень в
системі зв'язку.
• Сигнал може генеруватися, але його прийом не
обов'язковий, на відміну від повідомлення, яке
розраховане
на
прийняття
приймаючою
стороною, інакше воно не є повідомленням.
• Сигналом може бути будь-який фізичний процес,
параметри якого змінюються відповідно до
переданого повідомлення.
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
89

90. АЦП та ЦАП (ADC and DAC)

АЦП – аналого-цифровий перетворювач
ЦАП – цифро-аналоговий перетворювач
ЦАП
Всесвіт
Аналоговий
Цифровий
Комп’ютер
АЦП
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
90

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

Характеристика
Аналогові способи
Цифрові способи
Швидкодія
+
-
Універсальність
-
+
Мікромініатюризація
-
+
Точність
-
+
Масштабування
-
+
Передача у просторі
-
+
Передача у часі (пам’ять)
-
+
Програмування
-
+
Надійність
-
+
Тестування, відлагодження,
діагностика
-
+
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
91

92. Найпоширеніший аналоговий обчислювач (комп’ютер, помножувач)

Кут повороту = U*I*t*k
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
92

93. Найновіший аналоговий обчислювач (квантовий комп’ютер)

N 1
0 , 1 , ..., N 1 - Запис Дірака. i j - хвильова функцція
j 0
N 1
- Спін електрона
P i2 1 - Сума імовірностей
j 0
Ілюстрація поведінки кубіта
Сфера Блоха
НУЛП 20192020 н.р.
- Орбиталі
електрона
Одиничне коло
cos 0 sin 1
P=sin2θ+cos2θ=1 -
-хвильова функцція для одиничного кола
сума імовірностей для одиничного кола
Глухов В.С. Комп'ютерна логіка
93

94. цифровий квантовий копроцесор

0 Re z0
( 1 Re z1 ,..., i Re z i )
Quantum
coprocessor
цифровий квантовий
копроцесор
n/Qbit
1/Qbit
0
Initial
settings
Measurement
instruction
Instructions for
changing the wave
function
Check
result
Classical computer
y
0 0 11 ,
/ 2
yθ
cos 0 sin 1
10 0 1 ,
1 0 0 1 ,
xθ 0
0 0 1 1 ,
3 / 2
НУЛП 20192020 н.р.
x
Одиничне коло цифрового кубіта
Глухов В.С. Комп'ютерна логіка
94

95. Квантовий процесор з 2 кубітів

cos
1
y
0 sin
3
3
1
3
0
1
2
2
1
1
y
cos
6
0
x 0
0
/6
/ 3
1
p0( 1 ) 1 / 4 , p1( 1 ) 3 / 4
1
0
0 sin
p0( 2 ) 3 / 4 , p1( 2 ) 1 / 4
1 3 3
4 4 16
p10 p1( 1 ) p0( 2 )
3 3 9
4 4 16
p01 p0( 1 ) p1( 2 )
1 1 1
4 4 16
p11 p1( 1 ) p1( 2 )
3 1 3
4 4 16
Глухов В.С. Комп'ютерна логіка
6
1
3
1
0 1
2
2
x
p00 p0( 1 ) p0( 2 )
НУЛП 20192020 н.р.
95

96. Визначення частоти квантовим комп’ютером (квантове перетворення Фур’є)

Вхідний спектр станів |XXX..X0>
Input states spectrum
14
12,5
12,5
12,5
12,5
12,5
12,5
12,5
12,5
12
Probability
10
8
6
4
2
0,0
0
0
1
0,0
2
3
0,0
0,0
4
5
6
0,0
7 8 9
Input states
0,0 0,0
0,0
10 11 12 13 14 15
Output states spectrum
Квантова схема описує зміну станів кубітів у часі
50
38,5
Probability
40
30
22,3
20
13,5
8,6
7,3
10
0,0
2,7
0,0
5,3
0,0
1,7
5
6
0,0
0,0
0
0
1
2
3
4
7
8
0,0
0,0
0,0
9 10 11 12 13 14 15
Output states
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
96

97. Дискретизація та квантування

квантування
y
0
НУЛП 20192020 н.р.
Під квантуванням (англ. quantization) неперервної або дискретної
величини розуміють розбивку діапазону її значень на кінцеве
число інтервалів. Квантування часто використовується при
обробці цифрових сигналів, у тому числі при стисканні звуку й
зображень. Квантування приводить сигнал до заданих значень,
тобто, розбиває за рівнем сигналу (на графіку — по горизонталі).
Не слід плутати квантування з дискретизацією (і, відповідно,
рівень квантування з частотою дискретизації). При дискретизації
величина, що змінюється в часі (сигнал) заміряється із заданою
частотою (частотою дискретизації), таким чином, дискретизація
розбиває сигнал за часовою складовою (на графіку — по
вертикалі).
Сигнал, до якого застосована дискретизація й квантування,
називається цифровим.
дискретизація
x
Глухов В.С. Комп'ютерна логіка
97

98. Дискретиза́ція

• Дискретиза́ція — перетворення функцій
неперервних змінних у функції дискретних
змінних, за якими початкові неперервні
функції можуть бути відновлені із заданою
точністю.
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
98

99. Квантування

• Під квантуванням розуміють перетворення
неперервної за значеннями величини у величину з
дискретною шкалою значень з скінченної
множини дозволених, які називають рівнями
квантування.
• Квант (крок квантування) - відстань між
сусідніми рівнями квантування
• Імпульс (електричний) – короткочасне
збільшення або зменшення напруги або струму
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
99

100. Дискретизація та квантування

Неперервний у часі.
Дискретний за рівнем
НУЛП 20192020 н.р.
Дискретний у часі.
Неперервний за рівнем
Дискретний у часі.
Дискретний за рівнем
Глухов В.С. Комп'ютерна логіка
100

101. Дискретизація (у часі)

s(t)
T
Аналоговий сигнал:
Неперервний у часі.
Неперервний за рівнем
t
s
T
s 2n-1
s3
s2
s 2n
Δt
s1
s0
t
t0
t1
t2
t3
НУЛП 20192020 н.р.
Дискретний у часі.
Неперервний за рівнем
t 2n-1 t 2n
Глухов В.С. Комп'ютерна логіка
101

102. Квантування за рівнем

s(t)
T
Аналоговий сигнал:
t
s(t)
sk
Неперервний у часі.
Неперервний за рівнем
sk-1
Δs
s4
s3
Неперервний у часі.
Дискретний за рівнем
s2
s1
t
s0
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
102

103. Дискретизація за часом і квантування за рівнем

s(t)
T
Аналоговий сигнал:
t
s
Неперервний у часі.
Неперервний за рівнем
T
s8
s7
s6
Δs
s5
s4
Дискретний у часі.
Дискретний за рівнем
s3
s2
Δt
s1
t
s0
t0
t1
t2
НУЛП 20192020 н.р.
t3
t 2n-1 t 2n
Глухов В.С. Комп'ютерна логіка
103

104. Теорема Котельнікова – як часто треба вимірювати сигнал?

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
104

105. Переваги кодування двома символами (переваги двійкової системи числення)

• Просто
• Надійно
+U
формування
аналіз
S1
VD1
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
105

106. Додатня і від’ємна логіка

• (0 – менша напруга, 1 – більша напруга) –
додатня логіка, використовується
приблизно в 50%
• (1 – менша напруга, 0 – більша напруга) –
від’ємна логіка, використовується
приблизно в 50%
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
106

107. Варіанти представлення двійкових значень на фізичному рівні

Інтервали часу
t0
0
t1
1
t2
0
t3
0
t4
1
t5
1
t6
0
t7
1
• Амплітудний (рівнем)
• Частотний
t0
0
t1
1
Моменти часу
t2
t3
t4
t5
0
0
1
1
t6
0
t7
1
• Фазовий
• Імпульсний
• Інтервальний
• Інші
НУЛП 20192020 н.р.
t0
0
t1
1
Інтервали часу
t2 t3 t4
t5 t6
0 0 1
1 0
Глухов В.С. Комп'ютерна логіка
t7
1
107

108. Параметри імпульсу

Фронт, перепад з високого рівня на
низький, у цьому прикладі це "задній
" фронт, оскільки у часі він перший
Параметр
A - амплітуда
T - період
t - тривалість
F = 1/T - частота
t
A
T
Час
Фронт, перепад з низького рівня на
високий, у цьому прикладі це
"передній" фронт, оскільки у часі
він перший
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
108

109. Характеристики імпульса

• Амплітуда - найбільше значення, яке приймає будь-яка
величина, що змінюється за гармонійним законом
• Перíод колива́нь — проміжок часу між двома
послідовними максимальними відхиленнями фізичної
системи від положення рівноваги. Період коливань
позначається зазвичай великою літерою T (c, 1 мс=10-3с, 1
мкс=10-6с, 1 нс=10-9с, 1 пс=10-12с)
• Частота коливань обернено пропорційна періоду F = 1/T
(Гц, 1 кГц =103 Гц, 1 МГц =103 Гц, 1 ГГц =103 Гц)
• Фаза — кількісна характеристика коливання, що визначає
відмінність між двома подібними коливаннями, які
починаються в різні моменти часу.
• Спектр - розподіл значень фізичної величини
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
109

110. Структурна схема процесу передачі або оброблення інформації

Джерело
інформації
Кодер
джерела
інформації
Кодер
захисту
інформації
Кодер
каналу /
обчислювача
Джерело
завад
Приймач
інформації
НУЛП 20192020 н.р.
Декодер
приймача
інформації
Декодер
захисту
інформації
Декодер
каналу /
обчислювача
Глухов В.С. Комп'ютерна логіка
Модулятор
Канал /
обчислювач
Демодулятор
110

111. Функції кодера джерела інформації

Джерело
інформації
1.
2.
3.
НУЛП 20192020 н.р.
Інформація
Кодер
джерела
інформації
Дані
Код
Кодер
захисту
інформації
Перетворення неелектричних величин в електричні
Перетворення інформації в дані - аналого-цифрове
перетворення інформації
Усунення
надлишковості
інформації
Глухов В.С. Комп'ютерна логіка
111

112. Дані

• Числа
– ФК
• Без знаку
• Із знаком (ПК, ОК, ДК, МДК)
– РК
• IEEE 754 (S, D, E, Q)
• Текст
– Укр (КОІ-8У), Рос (КОІ-7, КОІ-8Р), англ (ASCII)
– Windows 1251, UTF
• Відео
• Аудіо
• Інші
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
112

113. Числа з фіксованою комою

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
113

114. Порядок байтів

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
114

115. Числа з рухомою комою. Стандарт IEEE-754

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
115

116. Кодова таблиця КОИ-7

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
116

117. Кодова таблиця KOI-8U

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
117

118. Кодові таблиці:

Windows1251
KOI8-U
KOI8-R
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
118

119. Структура кодів UTF-8 (Unicode Transformation Formats )

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
119

120. Кодування зображень. Матричні та векторні формати

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
120

121. Кодування відтінків кольору

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
121

122. Кількість кольорів

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
122

123. Формати аудіфайлів

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
123

124. Міри інформації

• Міри кількості інформації
– Структурні
– Статистичні
• Міри якості інформації – комп’ютерна
логіка такими мірами не займається
– Семантичні
• Інші
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
124

125. 2. Семантична міра (за значенням)

• властивості інформації:
–
–
–
–
–
–
–
–
–
–
–
НУЛП 20192020 н.р.
повнота,
достовірність,
цінність,
адекватність,
актуальність,
чіткість,
доступність,
невичерпність,
кумулятивність,
зрозумілість,
суб'єктивність.
Глухов В.С. Комп'ютерна логіка
125

126. Семантична міра

• Повнота
інформації
характеризує
якість
інформації і визначає достатність даних для
прийняття рішень.
• Достовірність інформації - її властивість
відображати реальні об'єкти з необхідною
точністю.
• Цінність інформації не може бути абстрактною.
Інформація має бути корисною і цінною для
певної
категорії
користувачів.
Цінність
інформації залежить від того, які задачі можна
вирішувати за її допомогою.
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
126

127. Семантична міра

• Адекватність інформації характеризує ступінь
відповідності інформації реаліям. Адекватна
інформація - це повна і достовірна інформація.
• Актуальність інформації - ступінь зберігання
цінності інформації для керування в момент її
використання, що залежить від динаміки зміни її
характеристик і від інтервалу часу, що пройшов із
моменту виникнення певної інформації.
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
127

128. Семантична міра

• Своєчасність інформації - її надходження
не пізніше заздалегідь визначеного часу,
узгодженого з часом вирішення
поставленого перед користувачем завдання.
• Чіткість інформації - інформація має бути
зрозуміла для того, кому вона призначена.
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
128

129. Семантична міра

• Доступність інформації - це можливість
отримання і перетворення інформації.
• Точність інформації - ступінь подібності
отриманої інформації до реального стану
об'єкта, процесу, явища тощо.
• Суб'єктивність інформації. Інформація має
суб'єктивний характер, оскільки її цінність
визначається ступенем сприйняття суб'єкта
(одержувача інформації).
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
129

130. Семантична міра

• Корисна інформація - властивість, що
зменшує невизначеність прийняття
рішення.
• Репрезентативність інформації правильність її відбору і формування для
адекватного відображення властивостей
об'єкта.
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
130

131. Семантична міра

• Змістовність інформації - це відношення
кількості семантичної інформації в
повідомленні до обсягу даних, які
обробляються.
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
131

132. Семантична міра

• Семантична міра використовується
викладачами на іспитах – дуже суб’єктивна,
дуже ненадійна, виникає дуже багато
помилок, тому небхідні комісії, щоб
усунути ці помилки.
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
132

133. Семантична міра

• Гарантоздатність – здатність надавати
задані послуги, яким можна виправдано
довіряти.
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
133

134. Структурні міри інформації

Структу́ра — це характеристика складу та просторова
картина складу об'єкта, речовини (ізотропна, анізотропна,
кристалічна, аморфна, гомогенний чи колоїдний розчин,
фазові суміші) взаєморозміщення формацій, частин,
деталей, елементів, певний функціональний взаємозв'язок
складових частин об'єкта, внутрішня будова.
• 1.1 Фізичні – вага, швидкість, тиск, інші фізичні величини
• 1.2 Геометричні – розміри, габарити
– 1 Н = 1кг*м/с2
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
134

135. 1.3 Структурні комбінаторні міри

• 1.3.1 Сполучення по l елементів з h (різняться складом)
• Нехай є множина М, яка складається з l різних елементів. Будь-яка
підмножина множини М, яка містить h елементів (h=0, 1, 2, ..., l),
називається сполученням (combination) або комбінацією з даних l
елементів по h елементів, якщо ці підмножини відрізняються хоча б
одним елементом. Число різних сполучень із l елементів по l
позначається (combination від combinare лат. сполучати).
h!
C
l! ( h l )!
5!
1 2 3 4 5
3
C5
10
3! ( 5 3 )! 1 2 3 1 2
l
h
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
135

136. Структурні комбінаторні міри

• 1.3.1a Сполучення з повторенням
(h l - 1)!
~l
l
Ch Ch l 1
l! ( h 1 )!
7!
1 2 3 4 5 6 7
~ 3 ( 5 3 1 )!
C5
35
3! ( 5 1 )! 3! 4! 1 2 3 1 2 3 4
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
136

137. Структурні комбінаторні міри

• 1.3.2 Перестановлення h елементів (різняться порядком)
Q h!
Q 5! 1 2 3 4 5 120
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
137

138. Структурні комбінаторні міри

• 1.3.3 Розміщення по l елементів з h (різняться складом та порядком)
h!
A
( h l )!
l
h
5!
1 2 3 4 5
A
60
( 5 3 )!
1 2
3
5
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
138

139. Структурні комбінаторні міри

1.3.3a Розміщення по l елементів з h з повторенням (різняться складом та
порядком)
~l
l
Ah h
~3
3
A5 5 125
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
139

140. 1.4 Міра Хартлі, США, 1928 р. (Ральф Хартлі)

h – кількість різних елементів, система числення
l - довжина, розрядність
Q – можлива кількість повідомлень
Q h
l
1.4a Адитивна двійкова логарифмічна
міра Хартлі
I log 2 Q log 2 h l log 2 h
l
I( M N ) I( M ) I( N )
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
140

141.

Одиниця кількості інформації
I 1 log 2 Q log 2 h l log 2 h 1 log 2 2
l
• Один двійковий розряд – Binary Digit – bit (b, б)
• Байт (B, Б) – найчастіше це 8 біт.
I log 2 Q log 2 hl l log 2 h
N 613; I N log 2 613 9 ,26 10
N 61310 10011001012 I N 10 біт
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
141

142. Похідні одиниці кількості інформації

• 1 К = 1024
1 М = 1024 К;
1 Г = 1024 М;
1 Т = 1024 Г;
1 П = 1024 Т.
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
142

143. 3. Статистична міра, Клод Шеннон, 1948, США

1
I log 2 h log 2 Q log 2 log 2 p
Q
l
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
143

144. Ентропія джерела повідомлення – характеризує здатність джерела віддавати інформацію

N –дослідів, k – різних,
i-тий результат повторюється ni разів та дає Ii
інформації
I сер
n1 I 1 n2 I 2 ... nk I k
; I i log 2 pi ;
N
ni
pi
N
k
I сер p1 log 2 p1 p 2 log 2 p 2 ... p k log 2 p k pi log 2 pi ;
k
i 1
H pi log 2 pi ;
i 1
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
144

145. Властивості ентропії

• Невід’ємна
• = 0, коли ймовірність однієї події = 1
• Максимальна, коли ймовірності всіх подій
однакові
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
145

146. Залежність ентропії двох подій від їх імовірності

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
146

147. Кількість отриманої в результаті досліджень інформації

• I = Hпочаткове – Hкінцеве
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
147

148. Усунення надлишковості інформації. Алгоритм ефективного кодування Шеннона – Фано

повідомлення, які складаються з літер
певного алфавіту, можна закодувати так, що
середнє число двійкових символів на літеру
буде як завгодно близьке до ентропії
джерела цих повідомлень, але не менше
цієї величини
7
H - pi log 2 pi 1/2 1 1/4 2 1/8 3 1/16 4 ... 1/128 7 127/64.
i 0
7
Lсер.еф. pi ni 1/2 1 1/4 2 1/128 7 127/64. Lсер.еф. H.
i 0
7
Lсер.нееф. pi ni 1/2·3 1/4·3 ... 1/128·3 3 H
i 0
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
148

149. Абетка Морзе

А.Б -…
В .--
Л .-..
М -Н -.
Ц -.-.
Ч ---.
Ш ----
Г--.
Д -..
Е.
О --П .--.
Р .-.
Щ --.Ъ .--.-.
Ы -.--
Ж …З --..
И ..
С…
ТУ ..-
Ь -..Э ..-..
Ю ..--
Й .--К -.-
Ф ..-.
Х ….
Я .-.-
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
149

150. Послідовний, паралельний та паралельно-послідовний способи передачі інформації

Послідовний, паралельний та паралельнопослідовний способи передачі інформації
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
150

151. SerDes

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
151

152. Строб (вказівник, спрацьовувати)

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
152

153. Способи опрацювання даних – способи з’єднання цифрових автоматів

X
ЦА1
Y1
ЦА3
ЦА2
Y=f(Y1,Y2)
Y2
а
X
ЦА1
Y1
ЦА2
Y=f(Y1)
б
X
ЦА1
X1=f(X,Y2)
ЦА2
Y=f(X1)
Y2=f(Y)
ЦА3
в
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
153

154. Послідовний, паралельний та послідовно-паралельний способи опрацювання даних

Послідовний, паралельний та послідовнопаралельний способи опрацювання даних
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
154

155. Опрацювання даних з використанням зворотних зв’язків

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
155

156. Опрацювання даних в ієрархічних структурах

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
156

157. Кодер захисту інформації

Джерело
інформації
Кодер
джерела
інформації
Кодер
захисту
інформації
Кодер
каналу /
обчислювача
Джерело
завад
Приймач
інформації
Декодер
приймача
інформації
Декодер
захисту
інформації
Декодер
каналу /
обчислювача
Модулятор
Канал /
обчислювач
Демодулятор
Кодер захисту інформації необхідний для забезпечення інформаційної безпеки
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
157

158. Захист інформації

Види захисту інформації
Технічний — забезпечує обмеження доступу до носія повідомлення апаратнотехнічними засобами (антивіруси, фаєрволи, маршрутизатори, токіни, смарт-карти
тощо):
Інженерний — попереджує руйнування носія внаслідок навмисних дій або
природного впливу інженерно-технічними засобами (сюди відносять обмежуючі
конструкції, охоронно-пожежна сигналізація).
Криптографічний — попереджує доступ за допомогою математичних перетворень
повідомлення (ІП):
Організаційний — попередження доступу на об'єкт інформаційної діяльності
сторонніх осіб за допомогою організаційних заходів (правила розмежування
доступу)
Юридичний – неминучисть покрання за порушення захисту з боку закону
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
158

159. Загальна схема криптографічної системи

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
159

160. Перемішування

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
160

161. Накладання ключа

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
161

162. Коди, що коректують

• Коди, які виявляють помилки
– Коди с контролем на парність
– Коди с контролем на непарність
– Інші
• Коди, які виправляють помилки
– Коди Хеммінга
– Циклічні контрольні суми
– Інші
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
162

163. Контроль на парність / непарність

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
163

164. Код Хеммінга

i
i
F
k
F
Лінія зв’язку
==
Код
помилкового
k біта
n
i
k
7
4
3
15
11
4
31
26
5
F – вузол формування контрольнихих розрядів кода Хеммінга
K1 = i3 i5 i7 i9 i11 i13 i15
K2 = i3 i6 i7 i10 i11 i14 i15
K4 = i5 i6 i7 i12 i13 i14 i15
K8 = i9 i10 i11 i12 i13 i14 i15
K k = <K8 k8><K4 k4><K2 k2><K1 k1>
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
164

165. Код Хеммінга

Таблиця 1.6.2
n1
n2
n3
n4
n5
n6
n7
n8
n9
n10
n11
n12
n13
n14
n15
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
k1
k2
i3
k4
i5
i6
i7
k8
i9
i10
i11
i12
i13
i14
i15
k1 = i3 i5 i7 i9 i11 i13 i15;
k2 = i3 i6 i7 i10 i11 i14 i15;
k4 = i5 i6 i7 i12 i13 i14 i15;
k8 = i9 i10 i11 i12 i13 i14 i15;
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
165

166. Код Хеммінга

Сформувати код Геммінга для двійкового коду i = 010 0110 0011 і перевірити, як він розпізнає помилку в розряді i13.
n1 n2 n3 n4 n5 n6 n7 n8 n9 n10 n11 n12 n13 n14 n15
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
0
0
0
1
0
1
1
0
1
0
1
1
1
1
0
0
0
0
0
1
0
1
1
0
1
0
1
1
1
1
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
k1 k2 i3 k4 i5
i6
i7 k8 i9 i10 i11 i12 i13 i14 i15
0
0
0
1
1
1
0
0
0
1
i
i
F
k
Код
помилкового
k біта
==
Лінія зв’язку
F
F – вузол формування контрольнихих розрядів кода Хеммінга
1
Передавач сформує перевірочні розряди (k) коду Геммінга за таблицею
k1 = i3 i5 i7 i9 i11 i13 i15 = 0 1 0 1 0 0 1 = 1;
k2 = i3 i6 i7 i10 i11 i14 i15 = 0 0 0 1 0 1 1 = 1;
k4 = i5 i6 i7 i12 i13 i14 i15 = 1 0 0 0 0 1 1 = 1;
k8 = i9 i10 i11 i12 i13 i14 i15 = 1 1 0 0 0 1 1 = 0.
Тобто, приймач повинен отримати код n = 110 0100 0110 0011.
n
i
k
7
4
3
15
11
4
31
26
5
n1 n2 n3 n4 n5 n6 n7 n8 n9 n10 n11 n12 n13 n14 n15
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
0
0
0
1
0
1
1
0
1
0
1
1
1
1
0
0
0
0
0
1
0
1
1
0
1
0
1
1
1
1
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
k1 k2 i3 k4 i5
i6
i7 k8 i9 i10 i11 i12 i13 i14 i15
0
0
0
1 1
НУЛП 20192020 н.р.
1
1
0
Глухов В.С. Комп'ютерна логіка
1
1
0
0
0
1
1
166

167. Код Хеммінга

Сформувати код Геммінга для двійкового коду i = 010 0110 0011 і перевірити, як він розпізнає помилку в розряді i13.
n1 n2 n3 n4 n5 n6 n7 n8 n9 n10 n11 n12 n13 n14 n15
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
0
0
0
1
0
1
1
0
1
0
1
1
1
1
0
0
0
0
0
1
0
1
1
0
1
0
1
1
1
1
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
k1 k2 i3 k4 i5
i6
i7 k8 i9 i10 i11 i12 i13 i14 i15
0
0
0
1 1
1
1
0
1
1
0
0 01 1
1
Приймач сформує перевірочні розряди (k) коду Геммінга за таблицею
K1 = i3 i5 i7 i9 i11 i13 i15 = 0 1 0 1 0 1 1 = 0;
K2 = i3 i6 i7 i10 i11 i14 i15 = 0 0 0 1 0 1 1 = 1;
K4 = i5 i6 i7 i12 i13 i14 i15 = 1 0 0 0 1 1 1 = 0;
K8 = i9 i10 i11 i12 i13 i14 i15 = 1 1 0 0 1 1 1 = 1.
i
i
F
k
Лінія зв’язку
==
Код
помилкового
k біта
F
F – вузол формування контрольнихих розрядів кода Хеммінга
K k = <K8 k8><K4 k4><K2 k2><K1 k1> = <1 0><0 1><1 1><0 1> = 11012=1310.
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
167

168. Методичні вказівки

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
168

169. Контроль виконання операцій. Числовий контроль за модулем

i-розрядні
операнди
:m
k-розрядні
модулі
операндів
i-розрядний
арифметичний
пристрій
k-розрядний
арифметичний
пристрій
i-розрядний
результат
:m
k-розрядний
модуль
результату
k << i
Ознака
помилки
==
k-розрядний результат арифметичної
операції над модулями операндів
:m - вузол формування модуля
13+17=30
(13mod3 + 17mod3)=(1+2)mod3=3mod3=0;
30mod3=0;
0=0 – помилки немає
13х17=
13-17=
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
169

170. Перегони сигналів. Сусідні коди. Карти Карно

i3 i2 i1 i0
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
170

171. Скручування карти Карно по вертикалі і горизонталі

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
171

172. Карти Карно

d
b
d
0
1
3
2
10
11
13
12
4
5
7
6
14
15
17
16
8
C
D
F
E
8
1C
1D
1F
1E
8
9
B
A
18
19
1B
1A
*
e
НУЛП 20192020 н.р.
c
b
c
a
e
Глухов В.С. Комп'ютерна логіка
172

173. Перегони сигналів. Сусідні коди.

На вхід пристрою подавався спочатку код 0=0002, а потім він
змінився на код 7=1112. Визначити можливі помилкові коди, які
виникають з-за неодночасної зміни двійкових розрядів.
НУЛП 20192020 н.р.
0
1
3
2
4
5
7
6
8
C
D
F
E
8
9
B
A
Глухов В.С. Комп'ютерна логіка
173

174. Перегони сигналів. Сусідні коди.

0-1-3-7
0=000
1=001
3=011
7=111
0=000
2=010
3=011
7=111
0=000
4=100
5=101
7=111
0-1-5-7
0
1
3
2
0
1
3
2
4
5
7
6
4
5
7
6
0
1
3
2
0
1
3
2
4
5
7
6
4
5
7
6
0
1
3
2
0
1
3
2
4
5
7
6
4
5
7
6
0-2-3-7
0=000
1=001
5=101
7=111
0-2-6-7
0-4-6-7
0=000
2=010
6=110
7=111
0=000
4=100
6=110
7=111
0-4-5-7
0
1
3
2
0
1
3
2
4
5
7
6
4
5
7
6
Якщо два коди відрізняються n двійковими розрядами, то
помилкових проміжних станів буде 2n-2 (якщо n=0 або n=1, помилкових станів і перегонів не
буде);
їхніх можливих послідовностей - n! (n факторіал), n!=1·2·…·(n-1) ·n;
довжина кожної послідовності - n-1.
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
174

175. Кодер каналу / обчислювача

Джерело
інформації
Кодер
джерела
інформації
Кодер
захисту
інформації
Кодер
каналу /
обчислювача
Джерело
завад
Приймач
інформації
НУЛП 20192020 н.р.
Декодер
приймача
інформації
Декодер
захисту
інформації
Декодер
каналу /
обчислювача
Глухов В.С. Комп'ютерна логіка
Модулятор
Канал /
обчислювач
Демодулятор
175

176. Позиційні системи числення

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
176

177. Двійково-десяткові коди

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
177

178. Двійково-десяткові коди

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
178

179. Трійкова симетрична (врівноважена) система числення

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
179

180. Системи числення з іраціональними основами Класичний CORDIC-метод обчислення тригонометричних ф-цій Coordinate Rotation Digital

Computer
метод Дж. Волдера
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
180

181. Система залишкових класів

Таблиця 1.5.1
Система залишкових класів
— індикт змінювався від 1 до 15 і знову скидався на 1;
— коло Сонця змінювалося від 1 до 28 і знову скидалося на 1;
— коло Місяція змінювалося від 1 до 19 і знову скидалося на 1.
7980 = 15 х 28 х 19
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
Чис- Залишки від Код
ло
ділення на
у
2 3 5 СЗК
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
0
0,0,0
1,1,1
0,2,2
1,0,3
0,1,4
1,2,0
0,0,1
1,1,2
0,2,3
1,0,4
0,1,0
1,2,1
0,0,2
1,1,3
0,2,4
1,0,0
0,1,1
1,2,2
0,0,3
1,1,4
0,2,0
1,0,1
0,1,2
1,2,3
0,0,4
1,1,0
0,2,1
1,0,2
0,1,3
1,2,4
0,0,0
181

182. Системи числення

Основа системи
числення
Вага i-го розряду
Значення коефіцієнтів перед вагою
розрядів
Назва системи числення
10
10i = 0..010..010
{0, 1, 2, …, 8, 9}
Десяткова
2
2i = 0..010..02
{0, 1}
Двійкова
2
2i = 0..010..02
{-1, 1}
Двійкова симетрича
3
3i = 0..010..03
{0, 1, 2}
Трійкова
3
3i = 0..010..03
{-1, 0, 1}
Трійкова симетична
8
8i = 0..010..08
{0, 1, 2, …, 6, 7}
16
16i = 0..010..016
{0, 1, 2, …, 8, 9, A, B, …, E, F}
СЗК
В0 =(0,…, 0,1),
В1 =(0,…0,1,0),
…
Вn-1 =(1,0,…,0)
{0, 1}, {0, 1, 2}, {0, 1, 2, 3, 4}, {0, 1, 2,
…, 6}, …
arctg(2-i)
{0, 1}
pi = 0..010..0p
{0, 1}, …, {0, 1, 2, 3, 4, 5, 6}, …
іраціональна
p
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
Вісімкова
Шістнадцятькова
Система залишкових
класів
Одна з систем числення з
іраціональною основою
поля Галуа
182

183. Поля Галуа Galois Fields GF(Q) Q – порядок поля

• Прості поля Галуа GF(p)
– GF(7) – {0,1,2,3,4,5,6}
– У полі GF(7) 5+6=11mod7=4, 5+6=4 => 4-6=5.
– У полі GF(7) 5x6=30mod7=2, 5x6=2 => 2:6=5.
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
183

184. Поля Галуа Galois Fields GF(Q)

• Розширені поля Галуа GF(pn);
p – характеристика:
n - розмір поля, розрядність
GF(72) – x1x0 {00,01,…,26,30,...,65,66}
56=5x1+6x0, 66=6x1+6x0
56+66=(11mod7 12mod7)=45=
=4x1+5x0
P=x2+4x1+5x0=0 (простий поліном)
x2=-4x1-5x0 ; 2x2=-8x1-10x0
56x66=25 =2x1+5x0
=>25:56=66.
x2
x1
5
6
x0
6
6
30
30 36
30 66
36
×
+
2
P=x2+4=0 (простий поліном)
P=x2+x+6=0 (простий поліном)
P=x2+2x+2=0 (простий поліном)
P=x2+2x+3=0 (простий поліном)
P=x2+4x+1=0 (простий поліном)
P=x2+4x+6=0 (простий поліном)
P=x2+5x+3=0 (простий поліном)
НУЛП 20192020 н.р.
+
Глухов В.С. Комп'ютерна логіка
3
-5
2
36 mod7
1
-9 mod7
5
184

185. Поля Галуа

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
185

186. Сусідній код (код Грея)

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
186

187. Сусідні коди

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
187

188. Карти Карно

d
b
d
0
1
3
2
10
11
13
12
4
5
7
6
14
15
17
16
8
C
D
F
E
8
1C
1D
1F
1E
8
9
B
A
18
19
1B
1A
*
e
НУЛП 20192020 н.р.
c
b
c
a
e
Глухов В.С. Комп'ютерна логіка
188

189. Скручування карти Карно по вертикалі і горизонталі

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
189

190. Структурна схема процесу передачі або оброблення інформації

Джерело
інформації
Кодер
джерела
інформації
Кодер
захисту
інформації
Кодер
каналу /
обчислювача
Джерело
завад
Приймач
інформації
НУЛП 20192020 н.р.
Декодер
приймача
інформації
Декодер
захисту
інформації
Декодер
каналу /
обчислювача
Глухов В.С. Комп'ютерна логіка
Модулятор
Канал /
обчислювач
Демодулятор
190

191. Декодер приймача інформації. Семисегментний індикатор

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
191

192.

а
б
a
f
g
e
b
c
d
Выход
8
4
2
1
a
b
c
d
e
f
g
Символ
0
0
0
0
1
1
1
1
1
1
0
0
0
0
0
1
0
1
1
0
0
0
0
1
0
0
1
0
1
1
0
1
1
0
1
2
0
0
1
1
1
1
1
1
0
0
1
3
0
1
0
0
0
1
1
0
0
1
1
4
0
1
0
1
1
0
1
1
0
1
1
5
0
1
1
0
1
0
1
1
1
1
1
6
0
1
1
1
1
1
1
0
0
0
0
7
1
0
0
0
1
1
1
1
8
0
0
1
1
1
1
1
1
1
1
1
0
1
1
9
DI
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
192

193. Декодер приймача інформації. Матричний індикатор

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
193

194. Алгоритм

• Система формальних правил або приписів,
які
визначають
процес
досягнення
конкретної мети – перетворення деяких
даних у бажаний результат, а також набір
умов, які визначають порядок застосування
цих правил до даних, що обробляються
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
194

195. GlobalLogic

Cписок вимог, на які в компанії GlobalLogic звертається особлива увага при
відборі:
Профільна технічна освіта
Математичний склад розуму
Англійська на рівні Pre-intermediate - Intermediate+
Базові знання мов програмування - C та C++
Знання алгоритмів
Розуміння особливостей структур даних
Навички роботи з “залізом”
Знання теорії операційних систем - основні компоненти ОС
Розуміння стандартної системи роботи з проектами і досвід роботи з
класичним тулсетом девелопера (Git, Jira)
Практичний досвід (лабораторні роботи, курсові, виконані практичні заняття
на базі STM, власні проекти з посиланням на Git, де їх можна переглянути)
буде великим плюсом
Вміння швидко вчитись
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
195

196. Характеристики алгоритму

• 3 множини:
– Множина вхідних даних
– Множина можливих результатів
– Множина проміжних результатів
• 4 правила:
–
–
–
–
НУЛП 20192020 н.р.
Правило початку роботи
Правило безпосереднього перетворення даних
Правило закінчення роботи
Правило вилучення результату
Глухов В.С. Комп'ютерна логіка
196

197. Властивості алгоритму

Скінченність, результативність
– алгоритм має завжди завершуватись після виконання скінченної кількості кроків. Процедуру,
яка має решту характеристик алгоритму, без, можливо, скінченності, називають методом
обчислень.
Дискретність
– процес, що визначається алгоритмом, можна розчленувати (розділити) на окремі елементарні
етапи (кроки), кожен з яких називається кроком алгоритмічного процесу чи алгоритму.[31]
Визначеність, однозначність
– кожен крок алгоритму має бути точно визначений. Дії, які необхідно здійснити, повинні бути
чітко та недвозначно визначені для кожного можливого випадку.
Масовість, універсальність, повторюваність
– властивість алгоритму, яка полягає в тому, що алгоритм повинен забезпечувати розв'язання
будь-якої задачі з класу однотипних задач за будь-якими вхідними даними, що належать до
області застосування алгоритму.
Ефективність
– Алгоритм вважають ефективним, якщо всі його оператори досить прості для того, аби їх
можна було точно виконати за скінченний проміжок часу з допомогою олівця та аркушу
паперу.
Вхідні дані
– алгоритм має деяку кількість (можливо, нульову) вхідних даних, тобто, величин, заданих до
початку його роботи або значення яких визначають під час роботи алгоритму.
Вихідні дані
– алгоритм має одне або декілька вихідних даних, тобто, величин, що мають досить визначений
зв'язок із вхідними даними.
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
197

198. Представлення алгоритмів http://uk.wikipedia.org/wiki/Алгоритм

• У процесі розробки алгоритму можуть використовуватись
різні способи його опису, які відрізняються за простотою,
наочністю, компактністю, мірою формалізації, орієнтації
на машинну реалізацію тощо.
–
–
–
–
–
словесна або вербальна (неформальні мови, формульно-словесна);
псевдокод (формальні алгоритмічні мови);
Таблична;
Часові діаграми;
схемна:
• Функціональні схеми;
• блок-схема, виконується за вимогами стандарту
• граф автомата
– інші
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
198

199. Блок-схема алгоритму

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
199

200. Граф автомата Мура та позначки у вершинах графа з двійковим кодуванням станів

Граф – це множина
вершин і пар вершин,
які з’єднано дугами
(стрілочками) або
ребрами (лініями)
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
200

201. Граф автомата

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
201

202. Блок-схема алгоритму та граф автомата

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
202

203. Таблиці переходів та виходів автомата Мура

№
0
1
2
3
4
5
6
7
Попередній стан
автомата
Позначення
Код
ai
Q1 Q0
a0
0
0
a0
0
0
0
1
a1
0
1
a1
1
0
a2
1
0
a2
a3
1
1
1
1
a3
x
0
1
0
1
0
1
0
1
Наступний стан
автомата
Позначення
Код
aj
q1
q0
a1
0
1
a0
0
0
1
0
a2
1
0
a2
1
1
a3
1
1
a3
a0
0
0
0
0
a0
Сигнали
збудження
тригерів
D1
D0
0
1
0
0
1
0
1
0
1
1
1
1
0
0
0
0
№
0
1
2
3
НУЛП 20192020 н.р.
Попередній стан
автомата
Позначення
Код
ai
Q1 Q0
0
0
a0
0
1
a1
1
0
a2
1
1
a3
Глухов В.С. Комп'ютерна логіка
Вихідні
сигнали
автомата
y
1
1
0
0
203

204. Функціональна схема автомата Мура

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
204

205. Часова діаграма роботи автомата Мура

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
205

206. Опис автомата формальною (з правилами без винятків) або неформальною (з правилами та винятками з них) мовами

Опис автомата формальною (з правилами без винятків) або
неформальною (з правилами та винятками з них) мовами
State_machine: process (c)
begin
if rising_edge(c) then
case State is
when a0 =>
if x='1' then
State <= a0;
elsif x='0' then
State <= a1;
end if;
when a1 =>
State <= a2;
when a2 =>
State <= a3;
when a3 =>
State <= a0;
when others =>
null;
end case;
end if;
end process;
y_assignment:
y <= '1' when (State = a0) else
'1' when (State = a1) else
'0';
end fsm1_arch;
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
206

207. Теза Черча -Т’юрінга (1936)

Теза Черча -Т’юрінга (1936)
• Теза Т’юрінга - Будь-яка обчислювана в природному сенсі функція
може бути обчислена універсальною машиною Тьюрінга
• Теза Черча —
– усі обчислювальні пристрої можуть бути змодельовані на машині
Т’юрінга
– Будь-який фізична обчислювальний пристрій може бути змодельований
машиною Т’юрінга, причому цей процес поліноміален за кількістю
ресурсів, які були б витрачено цим обчислювальним пристроєм.
– для кожного алгоритму може бути побудована формальна алгоритмічна
система (ФАС), яка його реалізує
Quantum theory, the Church-Turing principle and the universal quantum computer. By D. Deutsch. Proc. R. Soc. Lond. A 400, 97-117 (1985)
Квантовый компьютер и квантовые вычисления (сборник) Дэвид Дойч, Виктор Садовничий, Ричард Фейнман, Ч. Беннет, Р. Ландауэр, П. Бенев, Р. Джозса, П. Шор, Ю. Манин. Серия: Библиотека "R&C Dynamics“. НИЦ "Регулярная и хаотическая
динамика“. 2001
P. W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput., 26:5, 1997, 1484-1509.
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
207

208. Універсальні ФАС – можуть реалізувати будь-який алгоритм

Рекурсивні функції
Машина Тюринга (фільм “Гра в імітацію”)
Машина Поста
Схеми Колмогорова-Успенського
Нормальні алгорифми Маркова
Скінченні цифрові автомати (комп’ютери та їх програми)
зараз ФАС –
– програма для універсального комп’ютера або
– новий (спеціалізований) комп’ютер і програма для нього
http://uk.wikipedia.org/wiki/Алгоритм
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
208

209. Повна побудова алгоритму

• формулювання задачі;
• побудови моделі абстрактного алгоритм;
– АБСТРАКТНИЙ - той, що є наслідком мисленого виділення з усіх
ознак, властивостей і зв'язків конкретного предмета його основних,
найзагальніших;
розроблення абстрактного алгоритму;
перевіряння правильності абстрактного алгоритму;
реалізації структурного алгоритму;
аналізу алгоритму і його складності;
перевіряння реалізації структурного алгоритму;
оформлення документації.
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
209

210. Загальна структурна схема цифрового автомата складається з двох цифрових схем

КСх
ПА
δ
{X}
КСх - комбінаційна схема
ПА - пам’ять автомата
δ – функція переходів
λ – функція виходів
λ
{A}
{Y}
{X} – множина вхідних сигналів
{Y} – множина вихідних сигналів
{A} – множина внутришніх станів
-Цифрові схеми поділяються на комбінаційні (без зворотних зв’язків) та
схеми з пам’яттю (із зворотними зв’язками, послідовнісні, секвенційні)
-Комбінаційна схема:
цифрова схема без пам’яті =
= цифрова схема без зворотних зв’язків =
= цифрова схема, стан виходів якої у момент часу t залежить тільки від
стану її входів у цей же момент часу t.
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
210

211. Структура комп’ютера

Пам'ять
Пристрій
вводу
Пристрій
керування керуючий
автомат
Пристрій
виводу
Операційний
пристрій операційний автомат
Процесор
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
Дані
Стан
Керування
Команда
211

212. Структурна схема автомата Мура

i
КСх
ПА
δ
{X} j
{A}
КСх
λ
1
КСх - комбінаційна схема
ПА - пам’ять автомата
δ – функція переходів
λ – функція виходів
j – кількість вхідних сигналів
k – кількість вихідних сигналів
НУЛП 20192020 н.р.
i
k
{Y}
2
{X} – множина вхідних сигналів
{Y} – множина вихідних сигналів
{A} – множина внутришніх станів
i – розрядність зворотного зв’язку,
кількість тригерів у пам’яті
автомата
Глухов В.С. Комп'ютерна логіка
212

213. Структурна схема автомата Мілі

КСх
{X}
δ
ПА
{A}
КСх
λ
1
{Y}
2
КСх - комбінаційна схема
ПА - пам’ять автомата
δ – функція переходів
λ – функція виходів
НУЛП 20192020 н.р.
{X} – множина вхідних сигналів
{Y} – множина вихідних сигналів
{A} – множина внутришніх станів
Глухов В.С. Комп'ютерна логіка
213

214. Алгебра логіки (Булева логіка, двійкова логіка, двійкова алгебра)

• Використовується для опису комбінаційних схем
• Розділ математичної логіки, що вивчає систему
логічних операцій над висловлюваннями.
Найчастіше передбачається, що висловлювання
можуть бути тільки істинними або помилковими,
тобто використовується так звана бінарна або
двійкова логіка, на відміну від, наприклад,
тризначної логіки.
• Вивчає функції, які можуть приймати тільки два
значення: 0 (істина) та 1 (хибність), так само, як і
їх аргументи
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
214

215. Змінні, набори і функції алгебри логіки – для опису комбінаційних схем цифрових автоматів

кількість
змінних
0
кількість
наборів
1
кількість
ФАЛ
2
1
2
3
2
4
8
4
16
256
4
…
n
16
…
65536
…
n
2
2
2n
n
n 1
2
An 2 C n
НУЛП 20192020 н.р.
n 2
An 1 C n
h!
C h l!(h l )!
l
1
...
Cn
An 2
Глухов В.С. Комп'ютерна логіка
A A
1
0
215

216. ФАЛ0, ФАЛ1

f0
f1
a
f0(a)
f1(a)
f2(a)
f3(a)
0
1
0
0
0
1
1
1
0
1
0
1
Фактично є
ФАЛ0
ФАЛ0
A0 2 2
20
A1 2 A0 2
21
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
216

217. Повторення, порогова функція “> 0”, f = a . Інверсія, заперечення, порогова ФАЛ1 “= 0”, f =a

Повторення, порогова функція “> 0”, f = a .
Інверсія, заперечення, порогова ФАЛ1 “= 0”, f = a
Діаграма Венна
a
1
a
a
a
a
а
a
1
а
a
(a=1)
б
a
a
( a 0)
a
б
a
f0(a)
f1(a)
f2(a)
f3(a)
0
0
0
1
1
1
0
1
0
1
Фактично є
ФАЛ0
f=a
f = a
ФАЛ0
Інверсія, інвертор, НЕ
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
217

218. Функції алгебри логіки двох змінних

A2 2 C21 A1 A0 16 2 2 2 10
22
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
218

219. Кон'юнкція (від латинського conjunctio – сполучник, зв'язок), логічне множення, функція мінімуму або функція І (И, AND),

порогова ФАЛ2 “= 2” (ФАЛn - “= n” )
Діаграма Венна
a b
a
a
&
b
а
ab
b
Зафарбована область - a & b
a
b
ab
б
Кон'юнкція, кон’юнктор, І
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
219

220. Диз'юнкція (від латинського disjunctio - роз'єднання), логічне додавання, функція максимуму або функція АБО (ИЛИ, OR), порогова

функція “> 0”
Діаграма Венна
ab
a
1
b
а
a b
a
b
a b
a
б
b
Зафарбована область - a v b
Диз'юнкція, диз’юнктор,
АБО
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
220

221. Функція (штрих) Шеффера або функція І-НЕ (NOT AND, NAND, И-НЕ), порогова ФАЛ2 “< 2” (ФАЛn “< n” )

Функція (штрих) Шеффера або функція І-НЕ (NOT AND,
NAND, И-НЕ), порогова ФАЛ2 “< 2” (ФАЛn “< n” )
Діаграма Венна
ab
a
b
Зафарбована область - ab
a
&
b
а
НУЛП 20192020 н.р.
ab
a
b
ab
б
Глухов В.С. Комп'ютерна логіка
221

222. Функція (стрілка) Пірса (Вебба) або функція АБО-НЕ (ИЛИ-НЕ, NOT OR, NOR), порогова ФАЛ “= 0”

Діаграма Венна
a b
a
a
1
b
а
НУЛП 20192020 н.р.
a b
a
a b
b
b
Зафарбована область - a b
б
Глухов В.С. Комп'ютерна логіка
222

223. Виключне АБО (XOR), додавання з модулем 2, додавання без переносів, порогова функція “=1”, доповнення до парності

Діаграма Венна
a
a
=1 a b
b
а
НУЛП 20192020 н.р.
a
b
a b
b
Зафарбована область - a b
б
Глухов В.С. Комп'ютерна логіка
223

224. Рівнозначність (еквівалентність), доповнення до непарності

Діаграма Венна
a
a
b
b
= = a b
Зафарбована область - a b
а
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
224

225. Імплікація (пряма)

x
a
b
а
a
b
б
x
a
b
x b
a
в
г
Діаграми Венна
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
225

226. Імплікація зворотна

x
b
a
а
b
a
б
x
b
a
x a
b
в
г
Діаграми Венна
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
226

227. Заперечення імплікації (прямої)

Заперечення зворотної імплікації
b
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
227

228. Теорема Поста-Яблонського про функціонально повні системи (ФПС, базиси)

• З ФАЛ, які мають якусь властивість, можна
утворити тільки ФАЛ, які мають цю ж властивість
• З ФАЛ, які мають якусь властивість не можна
утворити ФАЛ, які не мають цієї властивості
• До ФПС повинна входити хоча би одна ФАЛ, яка:
–
–
–
–
–
НУЛП 20192020 н.р.
1) не зберігає 0;
2) не зберігає 1;
3) несамодвоїсна;
4) немонотонна;
5) нелінійна
Глухов В.С. Комп'ютерна логіка
228

229. Теорема Поста-Яблонського про функціонально повні системи (ФПС, базиси)

Якщо функція f на нульовому наборі змінних дорівнює 0, тобто, f(0,0,...,0)=0, то ця функція зберігає
константу "0".
Якщо функція f на одиничному наборі змінних дорівнює 1, тобто, f(1,1,...,1)=1, то ця функція
зберігає константу "1".
ФАЛ називається монотонною, якщо при будь-якому зростанні кількості "1" у послідовності
сусідніх (тобто, таких, які відрізняються тільки в одному розряді) наборів змінних (х 0,х1,...,xn)
значення функції не зменшується.
ФАЛ називається самодвоїстою, якщо на кожній парі протилежних наборів (x0,x1,...,xn) та ( x0 , x1 ,..., xn )
вона приймає протилежні значення, тобто, якщо виконується умова
f(x0,x1,...,xn) = f ( x0 , x1 ,..., xn. )
ФАЛ називається лінійною, якщо її можна зобразити поліномом Жегалкіна без добутків змінних
f(x0,x1,...,xn) = a0·x0 a1·x1 ... an·xn,
де ai = (0, 1);
· - позначення операції І;
- позначення операції "додавання за модулем 2".
x = х 1,
х х ... х = х, якщо кількість х непарна;
х х ... х = 0, якщо кількість х парна;
х·х·...·х = x.
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
229

230. Властивості ФАЛ

x
Властивості ФАЛ
№
0
1
2
3
4
5
6
7
a
0
0
0
0
1
1
1
1
a
0
0
0
1
b
0
0
1
1
b
0
0
1
1
0
0
1
1
c
0
1
1
1
c
0
1
0
1
0
1
0
1
f
1
0
1
0
Перевірити, чи створює функція трьох змінних функціонально повну систему.
f
1
0
1
1
0
0
1
0
a
0
0
1
1
а
b
0
0
0
1
1) Оскільки на нульовому наборі f(0,0,0) = 1, то ця функція не зберігає константу "0".
2) Оскільки на одиничному наборі f(1,1,1) = 0, то ця функція не зберігає константу "1".
3) Послідовності сусідніх наборів подано в таблиці (а, ..., е). Овалами відмічено значення функції
f на сусідніх наборах, на яких вона зменшується при зростанні кількості 1 в наборах, тобто є
немонотонною. Стрілочкою позначено напрям збільшення кількості 1 у сусідніх наборах змінних
a, b, c. Оскільки на всіх шести послідовностях сусідніх наборів функція немонотонна (а досить
було б і на одному), то функція немонотонна взагалі.
c
0
1
1
1
б
f
1
0
0
0
a
0
0
0
1
b
0
1
1
1
c
0
0
1
1
в
f
1
1
1
0
a
0
0
1
1
b
0
1
1
1
c
0
0
0
1
г
f
1
0
1
0
a
0
1
1
1
b
0
0
0
1
c
0
0
1
1
д
f
1
0
0
0
a
0
1
1
1
b
0
0
1
1
c
0
0
0
1
f
1
0
1
0
е
1
2
3
4
a
0
0
0
0
b
0
0
1
1
c
0
1
0
1
f
1
0
1
1
a
1
1
1
1
b
1
1
0
0
c
1
0
1
0
f
0
1
0
0
4) 4 пари протилежних наборів наведено в таблиці (номери пар проставлено збоку).
Оскільки на кожній парі протилежних наборів функція f приймає протилежні значення, то
функція самодвоїсна.
5) Для визначення лінійності функції подамо її у вигляді полінома Жегалкіна
f a b c abc abc abc = (1 a)(1 b)(1 c) (1 a)b(1 c) (1 a)bc ab(1 c) =
=1 a c ab ac bc.
Оскільки поліном містить добутки (ab, ac, bc) змінних, то функція нелінійна.
Отже, із п'яти необхідних для створення ФПС властивостей відсутня одна несамодвоїстість, тому дана функція не утворює ФПС.
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
230

231. Властивості ФАЛ, монобазиси, базиси

0 1 Л М С
х0 0 0 1 1 Назва ФАЛ
х1 0 1 0 1
* *
f1
0 0 0 1 кон'юнкція, І
*
f7
0 1 1 1 диз'юнкція, АБО х0 v х1
1 1 0 0 інверсія х0
x0
НУЛП 20192020 н.р.
x
0
x
1
1
1
1
1
x
0
1
x
x
x
x
x
x
x
1
x
0
x
1
1
1
x
x
x
1
1
1
1
x
1
0
0
0
0
0
0
x
x
x
x
x
x
x
1
1
x
x
0
0
x
x
1
1
x
x
1
1
1
x
x
x
1
0
0
x
1
0
*
*
x0
*
1
x
1
0
0
x
x
x
1
x
*
1
* *
x
0
x
1
1
0 1 Л М С
*
1
x
x
x
1
1
1
0
0
x
x
x
x
x
Властивості
0
x
1
1
1
x
x
x
0
0
0
x
x
x
Вираз
ФАЛ
0 1 1 1 диз'юнкція, АБО х0 v х1
1 1 0 0 інверсія х0
x0
Глухов В.С. Комп'ютерна логіка
Властивості
Базис АБО, НЕ
х0 0 0 1 1 Назва ФАЛ
х1 0 1 0 1
f12
0
0
x
x
x
x
x
* *
x
х0 ·х1
x
0 0 0 1 кон'юнкція, І
*
f7
* * *
* * *
x
f1
x
1
*
0 1 Л М С
0
x0 x1
*
Вираз
ФАЛ
0
х0 0 0 1 1 Назва ФАЛ
х1 0 1 0 1
f12 1 1 0 0 інверсія х0
*
Властивості
1
*
*
*
x
x0 x1 x0 x1 *
x
0 1 1 0 сума за mod 2
0
* *
0
х0 ·х1
x
0 0 0 1 кон'юнкція, І
x
0 1 Л М С
x
x0 x1
x0
f12 1 1 0 0 інверсія х0
f13 1 1 0 1 імплікація пряма x0 x1
f14 1 1 1 0 І-НЕ (Шефера)
f15 1 1 1 1 константа "1"
Вираз
ФАЛ
0
f11
x1
*
Базис І, НЕ
* *
*
1
f10
1 0 1 0 інверсія х1
1 0 1 1 імплікація звор.
x0 x1 x0 x1
*
1
1 0 0 1 рівнозначність
Властивості
Базис Жегалкіна
f15 1 1 1 1 константа "1"
*
x
f9
* *
x
f8
0 1 1 1 диз'юнкція, АБО х0 v х1
1 0 0 0 АБО-НЕ (Пірса) x0 x1
x
f7
x
f6
*
x
x0 x1 x0 x1 *
x
0 1 1 0 сума за mod 2
0
f6
0
f1
* * * * *
0
х1
f4
1
х0 0 0 1 1 Назва ФАЛ
х1 0 1 0 1
x
*
x
x0 x1
f5
0 1 0 0 заборона по х0
0 1 0 1 х1
x
* * * * *
1
х0
f3
f12
*
x0 x1
*
x
f2
0 0 1 0 заборона по х1
0 0 1 1 х0
* *
1
* *
0
х0 ·х1
*
0
0 0 0 1 кон'юнкція, І
* *
0
f1
х0 ·х1
*
x
0
0
0 0 0 0 константа "0"
0 1 Л М С
0
f0
Вираз
ФАЛ
x
Властивості
Базис Буля
Вираз
ФАЛ
0
х0 0 0 1 1 Назва ФАЛ
х1 0 1 0 1
231
*

232. Деякі ФАЛ3

A3 2 C32 A2 C31 A1 A0 256 3 10 3 2 2 218
23
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
232

233. Сингулярні таблиці

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
233

234. Базис Буля

a
b
a
&
a b ... z
...
z
елемент І (AND),
кон'юнктор
НУЛП 20192020 н.р.
b
1
a b ... z
...
z
елемент АБО (OR),
диз'юнктор
a
1
a
елемент НЕ (NOT),
інвертор
Глухов В.С. Комп'ютерна логіка
234

235. Кон'юнкція (від латинського conjunctio – сполучник, зв'язок), логічне множення, функція мінімуму або функція І (И, AND),

порогова ФАЛ2 “= 2” (ФАЛn - “= n” )
Діаграма Венна
a b
a
&
b
ab
a
a
b
b
ab
Зафарбована область - a & b
а
б
Кон'юнкція, кон’юнктор, І
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
235

236. Диз'юнкція (від латинського disjunctio - роз'єднання), логічне додавання, функція максимуму або функція АБО (ИЛИ, OR), порогова

функція “> 0”
Діаграма Венна
ab
a
1
b
а
a b
a
b
a b
a
б
b
Зафарбована область - a v b
Диз'юнкція, диз’юнктор,
АБО
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
236

237. Інверсія, заперечення, порогова ФАЛ1 “= 0”, f =a

Інверсія, заперечення, порогова ФАЛ1 “= 0”, f = a
a
a
1
а
a
a
a
(a=1)
a
( a 0)
б
Діаграма Венна
Інверсія, інвертор, НЕ
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
237

238. Аналітичне представлення функцій алгебри логіки Досконалі нормальні форми

ДДНФ:
f(a, b, c) = F0(0, 0, 0) F3(0, 1, 1) F4(1, 0, 0) = a b c a b c a b c.
ДКНФ:
f(a, b, c) = Ф1(0,0,1)& Ф2(0, 1, 0) & Ф5(1, 0, 1) & Ф6(1, 1, 0) & Ф7(1, 1, 1) =
= (a b c)&(a b c)&( a b c)&( a b c) &( a b c).
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
238

239. Терм

• Терм - це група літер і констант, об'єднаних тим самим знаком
логічного зв'язування: логічного додавання або ж логічного
множення. У термі кожна літера і кожна константа зустрічається
тільки один раз, тобто в терм може входити або змінна, або її
заперечення.
• Диз'юнктивний терм (макстерм, елементарна диз’юнкція) - це
логічна функція, що зв'язує всі літери знаком диз'юнкції.
• Наприклад:
• f1 = a b c d;
f2 = a b.
• Макстерм називають також конституентою нуля, тому що ця логічна
функція дорівнює 0 тільки тоді, коли всі її літери рівні 0 одночасно.
• Кон'юнктивний терм (мінтерм, елементарна кон’юнкція) - це
логічна функція, що зв'язує літери знаком кон'юнкції.
• Наприклад:
• f1 = a & b & c & d;
f2 = a b c.
• Мінтерм називають також конституентою одиниці, тому що ця
функція дорівнює 1 тільки тоді, коли всі її літери одночасно
дорівнюють одиниці.
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
239

240. Досконалі нормальні форми

ДДНФ – Досконала диз’юнктивна нормальна форма
ДКНФ – Досконала кон’юнктивна нормальна форма
Ознаки ДНФ:
1) Кількість термів в ДДНФ (ДКНФ) дорівнює кількості одиничних
(нульових) значень ФАЛ у таблиці істинності цієї ФАЛ
2) Усі терми різні
3) У кожному термі присутні усі змінні
Кожна ФАЛ має лише одну ДДНФ і лише одну ДКНФ
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
240

241. Синтез логічних схем з одним виходом у базисі Буля на елементах з довільною кількістю входів

Матриця
Диз'юнктор
кон'юнкторів
a
&
1
a b c
b
c
Входи
a
Матриця
інверторів
a
1
a
b
b
1
b
c
c
1
c
a
b
c
&
a
&
a b c
&
a b c
a b c
Вихід
f
b
c
a
b
c
f a b c a b c a b c a b c
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
241

242. Переваги базису Буля (І, АБО, НЕ)

• Звичне для людини використання
сполучників І, АБО та частки НЕ
• Найбільш розвинутий математичний апарат,
що використовується при спрощенні
(мінімізації) логічних виразів
– Багато формул і правил спрощення
– Формули і правила здебільшого знайомі людині
із повсякденного життя
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
242

243. Основні правила виконання операцій у базисі Буля

ab = ba
a (bc ) = (ab )c
a (b v c ) = ab v ac
a = 0, якщо a 1;
Якщо a = 1, то a = 0
0 0 = 0;
1 0 = 0;
1 1 = 1;
1 = 0;
a 1 = a;
a 0 = 0;
a a = a;
a vb = b va
a v (b v c ) = (a v b ) v c
a v bc = (a v b )(a v c )
a = 1, якщо a 0;
Якщо a = 0, то a = 1
0 v 0 = 0;
0 v1 = 1
1 v1 = 1
0 = 1
a v0 = a
a v1 = 1
a va = a
a a
a v a = 1
a a
a a = 0;
a b c a b c
a (a v b ) = a
a v ab = a v b
ab v ab = b (a v a ) = b
НУЛП 20192020 н.р.
Закон комутативності
Закон асоціативності
Закон дистрибутивності
abc a b c
Правило де Моргана
a v ab = a
a ( a v b ) = ab
(a v b )( a v b ) = b
(закон поглинання)
(закон поглинання)
(закон склеювання)
Глухов В.С. Комп'ютерна логіка
243

244. Використання базису з 2-х ФАЛ: (І, НЕ)

Диз'юнктор
a b a b
Матриця
Матриця
кон'юнкторів
інверторів
a
1
&
a b c
b
кон'юнктор
&
c
Входи
a
Матриця
інверторів
a
1
b
b
1
c
1
c
НУЛП 20192020 н.р.
a
b
c
&
a
b
b
c
a
c
b
c
&
a b c
1
&
a b c
1
a
a b c
1
інвертор
Вихід
1
Глухов В.С. Комп'ютерна логіка
f
244

245. Використання базису з 2-х ФАЛ: (АБО, НЕ)

ab a c
Входи
a
Матриця
диз'юнкторів
a
1
b
c
Матриця
інверторів
a
1
b
b
1
c
1
a
Диз'юнктор
1
Вихід
c
a
b
b c
1
1
a
1
1
f
a
c
1
1
b
c
НУЛП 20192020 н.р.
1
Матриця
інверторів
b
c
Глухов В.С. Комп'ютерна логіка
245

246. Мінімізація ФАЛ

• Канонічна задача мінімізації
– У базисі Буля
– Над нормальними формами
– Мета – зменшення кількості літер
• Загальна задача мінімізації
– Усі інші методи
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
246

247. Методи розв’язання канонічної задачі мінімізації

• Аналітичні
– Квайна-МакКласскі-Петрика
– Інші
• Табличні
• Геометричні
• Графо-аналітичні
– Карти Карно
– Діаграми Вейча
• Алгебро-топологічні
• інші
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
247

248. Перегони сигналів - виникнення

a=1, b=1, c=0→1→ 0 →1
с
1
b
1
c
0
1
4
5
3
1
7
1
1
-c
f
2
6
t
t*
1
a
f a c bc
b
&
1
НУЛП 20192020 н.р.
1
f
c
a
c
&
-c
f
t
Глухов В.С. Комп'ютерна логіка
f=0 – результат гонок
248

249. Перегони сигналів – боротьба: сполучний терм

b
a
0
1
4
5
3
1
7
1
1
2
6
1
c
f ac ab bc
a
&
1
f
c
1
&
b
&
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
249

250. Двовходові елементи базису Буля

a
b
&
a
b
ab
елемент 2І (2AND),
кон'юнктор
a
a
b
&
ab
&
abc
c
a
b
&
c
&
d
ab
&
&
cd
c
d
&
e
a b
ab
&
abc
a
b
1
a b
c
1
a b c
a
b
1
c
1
a b
&
1
a
елемент НЕ (NOT),
інвертор
1
abc deh
de
&
1
deh
h
i
j
a
елемент 2АБО (2OR),
диз'юнктор
b
abcd
1
hi
&
abc deh ijk
ijk
k
1
a b c d
c d
d
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
250

251. Основні правила виконання операцій у монобазисах І-НЕ (Шеффера) та АБО-НЕ (Пірса)

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
251

252. Монобазис І-НЕ (NAND)

a
a
&
b
b
a b ... z
...
z
&
a
a b ... z
...
z
елемент І-НЕ (NAND)
a
1
a
елемент НЕ-АБО
1
a
a
&
b
a b ... z
1
ab... z
a
1
a
b
1
b
a b ... z
...
z
елемент І-НЕ (NAND)
...
елемент НЕ (NOT)
z
1
елементи НЕ
НУЛП 20192020 н.р.
1
z
елемент НЕ-АБО
Глухов В.С. Комп'ютерна логіка
252

253. Синтез логічних схем з одним виходом у монобазисі І‑НЕ

Синтез логічних схем з одним виходом у монобазисі І-НЕ
Матриця
Елемент НЕ-АБО
елементів І-НЕ
a
&
1
a b c
b
c
d
Входи
&
e
d e h
Вихід
h
i
j
f=abc v deh v іjk
f
&
i j k
k
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
253

254. 2І-НЕ

a
2І-НЕ
&
a b
&
a b
1
b
b
елемент 2І-НЕ
a
b
a
1
ab
&
c
a
ab
&
b
1
ab
&
abc
c
b
c
cd
&
cd
1
a a a
елемент НЕ-2АБО
&
&
a
1
a b
b
a
b
a
b
c
d
&
&
елементи 2І-НЕ
ab
елементи 2І-НЕ
&
a
&
1
a b
елемент НЕ-2АБО
&
b
&
a b
1
a b c
c
abcd
&
d
НУЛП 20192020 н.р.
1
елемент НЕ-2АБО
ab
&
a
елемент 2І-НЕ
a
a
a a a
1
c
&
&
ab cd
d
cd
&
a
1
a b
&
b
c
1
c d
d
&
a b
1
a b c d
c d
елемент НЕ-2АБО
Глухов В.С. Комп'ютерна логіка
254

255. Синтез логічних схем з одним виходом у монобазисі 2І-НЕ (Шеффера)

a
&
ab
f=abc v deh v іjk
1
b
ab
&
c
d
e
h
i
j
&
&
k
НУЛП 20192020 н.р.
de
ij
abc
1
de
&
deh
ij
&
ijk
1
abc deh
&
abc deh
1
f
1
Глухов В.С. Комп'ютерна логіка
255

256. Монобазис АБО‑НЕ (NOR)

Монобазис АБО-НЕ (NOR)
a
a
1
b
a b ... z
...
z
a
b
a b ... z
...
z
елемент АБО-НЕ (NOR)
a
&
b
1
a
a
елемент НЕ-І
&
a
a
1
a
b
1
b
a b ... z
1
a b ... z
...
z
&
a b ... z
елемент НЕ (NOT)
...
z
1
елемент АБО-НЕ (NOR)
елементи НЕ
НУЛП 20192020 н.р.
&
z
елемент НЕ-І
Глухов В.С. Комп'ютерна логіка
256

257. Синтез логічних схем з одним виходом у монобазисі АБО‑НЕ

Синтез логічних схем з одним виходом у монобазисі
АБО-НЕ
Матриця
Елемент НЕ-І
елементів АБО-НЕ
a
1
&
a b c
b
f=(avbvc)&(dvevh)&(іvjvk)
c
d
Входи
1
e
d e h
Вихід
h
i
j
f
1
i j k
k
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
257

258. 2АБО-НЕ

a
1
a
a a a
&
елемент 2АБО-НЕ
a
a b
1
&
a b
a
b
1
a b
1
c d
&
b
елемент 2АБО-НЕ (NOR)
a
1
a
елемент НЕ-2І
c
1
&
a
1
b
c
d
1
елементи 2АБО-НЕ
a
1
b
c
НУЛП 20192020 н.р.
a b
a
b
b
елементи 2АБО-НЕ
a
1
1
a b c d
&
1
b
ab
&
abc
c
1
c
( a b ) (c d )
c d
a
1
a
b
1
b
&
c
1
c
1
a b c
d
&
ab
елемент НЕ-2І
a b
&
ab
1
елемент НЕ-2І
a b
c d
елемент НЕ-2І
d
ab
b
&
a b
a a a
1
1
ab
&
abcd
&
cd
d
Глухов В.С. Комп'ютерна логіка
1
cd
258

259. Синтез логічних схем з одним виходом у монобазисі 2АБО-НЕ (Пірса)

Синтез логічних схем з одним виходом у монобазисі 2АБОНЕ (Пірса)
f (a b c)( d e h)(i j k )
a
1
a b
&
b
c
d
e
h
i
j
1
1
d e
i j
&
&
(a b c)( d e h)
(a b c)(d e h)
a b
1
a b c
&
1
&
d e
1
d e h
i j
1
i j k
f
k
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
259

260. Схеми елементів монобазисів на КМОН-транзисторах

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
260

261.

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
261

262. Елеманти монобазисів на КМОН-транзисторах

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
262

263. Основні правила виконання операцій у базисі Жегалкіна

a b a b a b ( a b )( a b )
Для цієї функції справедливі наступні аксіоми:
a a = 0; a a a = a;
a a 1 a a 1
a 0 a
На підставі розглянутих аксіом і властивостей
елементарних логічних функцій можна, наприклад,
вивести правила представлення функцій І, АБО, НЕ
через функцію додавання за модулем 2 і навпаки:
a v b = a b ab;
ab = (a b) (a v b).
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
263

264. Виключне АБО (XOR)

a
a
=1 a b
b
а
НУЛП 20192020 н.р.
a
b
a b
b
Зафарбована область - a b
б
Глухов В.С. Комп'ютерна логіка
264

265. Реалізація XOR

a b a b a b
a b ( a b )( a b )
Входи
Матриця
інверторів
a
1
1-ий ступінь
a
a
b
b
1
b
a
b
a
b
&
&
a
1
&
1-ий ступінь
a
a
b
&
b
b
2-ий ступінь
a b
Матриця
інверторів
Входи
a
b
a
&
2-ий ступінь
a b
&
1
Вихід
f
a b
b
Вихід
a b
f
Входи
Матриця
інверторів
a
1
a
b
b
1
1-ий ступінь
a
a
1
2-ий ступінь
( a b)
b
a
b
b
1
&
Вихід
f
( a b)
a b a b a b
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
265

266. Порівняння варіантів синтезу комбінаційних логічних схем

c
0
1
1
0
1
5
1
7
a b d
6
1
F
1
9
1
B
5
8
C
a b d
A
1
D
8
1
7
6
F
E
1
9
1
2
a b c d
1
1
a
3
1
1
b
E
1
8
4
c
D
1
1
1
8
C
a
2
1
4
c
3
c
b
1
B
A
a b c d
1
d
d
f a b c d a b c d c
f a b d a b d c
( 1 a )( 1 b )c( 1 d ) a b c ( 1 d ) ( 1 c )
.
c
0
1
3
2
0
4
c d
5
7
0
8
C
D
a b c
6
F
0
b
E
f c d a b c a b c (c d ) (a b c) (a b c)
0
a
8
9
B
a b c
A
0
0
d
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
266

267. ДНФ

Входи
Матриця
інверторів
a
1
1-ий ступінь
1
2-ий ступінь
Входи
a
a
b
f a b d a b d c
b
b
a
&
a b d
b
1
a
Вихід
d
&
b
a b c
b
&
1-ий ступінь
a
a
f
a
Матриця
інверторів
&
b
b
d
1
c
d
&
a b d
b
d
1
Вихід
f
a
&
a b c
b
d
c
a
2-ий ступінь
d
c
d
d
&
d
c
c
d
Матриця
інверторів
Входи c
1
1-ий ступінь
c
a
d
b
c
1
d
a
&
b
2-ий ступінь
a b d
d
d
Вихід
1
a b d a b d c
a
b
3-ий ступінь
1
&
f
a b d
b
d
c
d
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
267

268. КНФ

Матриця
інверторів
Входи a
&
1-ий ступінь
a
a
b
&
b
b
c
&
c
c
d
&
d
d
c
1
c d
d
a
1
b
2-ий ступінь
&
Матриця
інверторів
Вихід
a b c
Входи a
f
b
c
a
1
b
c
a b c
d
&
1-ий ступінь
a
a
b
НУЛП 20192020 н.р.
1
b
&
b
c
1
d
a
1
c
c
c
Входи a
d
a
b
Матриця
інверторів
c
1
1-ий ступінь
a
d
b
f ( c d ) ( a b c ) ( a b c )
2-ий ступінь
c d
1
a b c
1
a b c
b
1
d
c
1
c d
d
a
2-ий ступінь
1
a b c
1
a b c
b
&
Вихід
f
c
a
b
c
3-ий ступінь
Вихід
&
(c d )(a b c)(a b c)
1
f
c
a
b
c
Глухов В.С. Комп'ютерна логіка
268

269. Поліном Жегалкіна

Суматори за
модулем 2 як
Матриця
інвертори
кон'юнкторів
a
&
a b c d
"1"
b
Входи
a
b
c
d
=1
a
=1
b
=1
c
=1
d
c
d
a
a
b
b
c
d
c
c
Суматори за
модулем 2
=1
=1
&
Вихід
a b c d
f
d
f ( 1 a )( 1 b )c( 1 d ) a b c ( 1 d ) ( 1 c )
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
269

270. Поліном Жегалкіна

Трикутник Паскаля
f x2 x3 x1 x3 x1 x2
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
270

271. Синтез логічних схем з одним виходом у базисі Буля на елементах з довільною кількістю входів

Матриця
Диз'юнктор
кон'юнкторів
a
&
1
a b c
b
c
Входи
a
Матриця
інверторів
a
1
a
b
b
1
b
c
c
1
c
a
b
c
&
a
&
a b c
&
a b c
a b c
Вихід
f
b
c
a
b
c
f a b c a b c a b c a b c
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
271

272. Використання базису з 2-х ФАЛ: (І, НЕ)

Диз'юнктор
a b a b
Матриця
Матриця
кон'юнкторів
інверторів
a
1
&
a b c
b
кон'юнктор
&
c
Входи
a
Матриця
інверторів
a
1
b
b
1
c
1
c
НУЛП 20192020 н.р.
a
b
c
&
a
b
b
c
a
c
b
c
&
a b c
1
&
a b c
1
a
a b c
1
інвертор
Вихід
1
Глухов В.С. Комп'ютерна логіка
f
272

273. Використання базису з 2-х ФАЛ: (І, НЕ)

Диз' юнктор
a b a b
Матриця
кон' юнкторів
a
& a b c
b
Матриця
інверторів
b
b
c
c
НУЛП 20192020 н.р.
a
b
c
=1
a
Матриця
інверторів
=1 кон' юнктор
&
c
“1”
Входи
a
“1”
a
=1
b
=1
c
a
b
c
a
b
c
& a b c
& a b c
& a b c
=1
і нвертор
=1
1
Вих ід
f
=1
Глухов В.С. Комп'ютерна логіка
273

274. Небулеві базиси

Монобазис І-НЕ
Монобазис АБО-НЕ
Базис Жегалкіна (1, І, XOR)
Мажоритарний базис
• Пороговий базис, wi, T -
• Штучний інтелект, wi, T
• Багато інших
НУЛП 20192020 н.р.
2n 1
1, якщо xi n
i 1
f ( x1 , x 2 ,..., x 2 n 1 )
2n 1
0 , якщо xi n
i 1
const
n
1, якщо xi wi T
i 1
f ( x1 , x 2 ,..., x n )
n
0 , якщо xi wi T
i 1
– var
Глухов В.С. Комп'ютерна логіка
274

275. Порогові функції

(>0)
(=n)
(=2)
a
b
avb
ab
0
0
0
0
0
1
1
0
1
0
1
0
1
1
1
1
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
275

276. Форми представлення ФАЛ

• Табличні
– Таблиці істинності
– Сингулярні таблиці
Геометричні
Числові
Часові діаграми
Схеми
Аналітичні (формули)
інші
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
276

277. Геометричний спосіб представлення ФАЛ

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
277

278. Аналітичні форми представлення ФАЛ

• Нормальні
– Досконалі
• ДДНФ
• ДКНФ
• інші
– Скорочені (ДНФ, КНФ)
• Глухого кута – з найменшою кількістю термів
• Мінімальні – форма глухого кута з найменшою кількістю літер
• Абсолютно мінімальні – мінімальна у базисі Буля
• Анормальні
– Дужкові
– Із запереченням більше ніж над однією змінною
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
278

279. Терм

• Терм - це група літерал і констант, об'єднаних тим самим знаком
логічного зв'язування: логічного додавання або ж логічного
множення. У термі кожен літерал і кожна константа зустрічається
тільки один раз, тобто в терм може входити або змінна, або її
заперечення.
• Диз'юнктивний терм (макстерм, елементарна диз’юнкція) - це
логічна функція, що зв'язує всі літерали знаком диз'юнкції.
• Наприклад:
• f1 = a b c d;
f2 = a b.
• Макстерм називають також конституентою нуля, тому що ця логічна
функція дорівнює 0 тільки тоді, коли всі її літерали рівні 0 одночасно.
• Кон'юнктивний терм (мінтерм, елементарна кон’юнкція) - це
логічна функція, що зв'язує літерали знаком кон'юнкції.
• Наприклад:
• f1 = a & b & c & d;
f2 = a b c.
• Мінтерм називають також конституентою одиниці, тому що ця
функція дорівнює 1 тільки тоді, коли всі її літерали одночасно
дорівнюють одиниці.
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
279

280. Нормальні форми з мінтермами

• Будь-яка таблично задана ФАЛ може бути
представлена аналітично у вигляді
– диз'юнкції скінченого числа мінтермів, на кожнім з яких
функція дорівнює одиниці (диз’юнктивна нормальна
форма, ДНФ):
f(a, b,..., z) = F1 F2 ... F n,
– суми за модулем 2 скінченого числа мінтермів, на
кожнім з яких функція дорівнює одиниці (поліном
Жегалкіна):
f ( a ,b ,..., z ) F 1 F 2 ... Fn ,
де i - номери наборів, на яких функція дорівнює 1.
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
280

281. Нормальні форми з макстермами

• Будь-яка таблично задана ФАЛ може бути
представлена аналітично у вигляді
– кон'юнкції скінченого числа макстермів, на кожнім з
яких функція дорівнює нулю (кон’юнктивна нормальна
форма, КНФ):
f(a, b,..., z) = Ф1 & Ф2 & ... & Фm,
– результату порівняння скінченого числа макстермів, на
кожнім з яких функція дорівнює нулю (поліном
рівнозначності):
f ( a ,b ,..., z ) 1 2 , , , m ,
де i - номери наборів, на яких функція дорівнює 1.
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
281

282. Досконалі нормальні форми

• Кількість термів дорівнює кількості одиничних
(нульових) значень ФАЛ у її таблиці істиності
• У кожному термі присутні усі змінні
• Немає однакових термів
Кожна ФАЛ має тільки одну досконалу нормальну
форму і одну таблицю істинності – на цьому
побудовано доведення тотожності двох ФАЛ.
Також можна спробувати одну ФАЛ звести до
другої шляхом її еквівалентних перетворень.
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
282

283. Анормальні форми

Дужкова
f ab ab ( a b )ab
Із запереченням більше ніж над
однією літерою
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
283

284. Критерії синтезу схем ФАЛ

• Правильна робота
• Швидкодія (продуктивність)
• Апаратні витрати
Споживана потужність
Надійність
Складність
Однорідність структури
Ціна
інші
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
284

285. Методи визначення ціни реалізації ФАЛ

• Грошові одиниці
• Негрошові одиниці
– Кількість операцій
• І, АБО, НЕ
• І, АБО
• І (АБО)
– Кількість термів
• В ДНФ
• В КНФ
– Кількість літер
• В нормальних формах
• В анормальних формах
– Кількість входів
• І, АБО, НЕ
• І, АБО
• І (АБО)
– інші
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
285

286. Мінімізація ФАЛ

• Канонічна задача мінімізації
– У базисі Буля
– Над нормальними формами
– Мета – зменшення кількості літер
• Загальна задача мінімізації
– Усі інші методи
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
286

287. Методи розв’язання канонічної задачі мінімізації

• Аналітичні
– Квайна-МакКласскі-Петрика
– Інші
• Табличні
• Геометричні
• Графо-аналітичні
– Карти Карно
– Діаграми Вейча
• Алгебро-топологічні
• інші
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
287

288. Методи розв’язання загальної задачі мінімізації – не гарантують знаходження найкращого рішення

• Еврістичний (Метод спроб і помилок)
• Винесення за дужки
• Внесення надлишковості і глобального
винесення за дужки
• Перехід до небулевого базису
• Метод функціональної декомпозиції
• інші
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
288

289. Швидкодія комбінаційних схем

Швидкодія комбінаційної схеми оцінюється максимальною затримкою сигналу при проходженні його від
входу схеми до виходу, тобто визначається проміжком часу від моменту надходження вхідних сигналів до
моменту встановлення відповідних вихідних значень. Затримка сигналу кратна числу елементів, через які
проходить сигнал від входу до виходу схеми. Тому швидкодія схеми характеризується часом проходження
сигналів найдовшим шляхом від входу до виходу:
r
T ti
i 0
де ti - затримка сигналу на елементі i-того рівня. Значення r визначається кількістю рівнів комбінаційної схеми,
яка розраховується наступним чином. Входам схеми приписується рівень 0. Логічні елементи, пов'язані тільки
з входами схеми відносяться до рівня 1. Елемент відноситься до рівня k, якщо він пов'язаний входами з
елементами рівнів k-1, k-2, і т.д. Максимальний рівень елементів r визначає кількість рівнів комбінаційної
схеми - ранг схеми.
Будь-яку ФАЛ можна представити у ДНФ, якій відповідає дворівнева комбінаційна схема. Отже, швидкодія
будь-якої комбінаційної схеми в принципі можна довести до 2t, якщо затримки t всіх елементів однакові.
Мінімізація ФАЛ з метою зменшення апаратної складності схем зазвичай призводить до необхідності подання
функцій у дужковій формі, якій відповідають схеми з r>2. Тобто, зменшення витрат обладнання в загальному
випадку призводить до зниження швидкодії схем.
Рівень 0
a
b
c
НУЛП 20192020 н.р.
&
&
&
Рівень 1
a
b
1
a b
Рівень 2
&
a b
Рівень 3
1
a b c
c
Глухов В.С. Комп'ютерна логіка
289

290. Еврістичний

f ab ab ( a b )ab
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
290

291. Винесення за дужки

f abc acde abdg deg
ac( b de ) dg( ab e )
Внесення надлишковості і
глобального винесення за дужки
f abc acde abdg deg
aabc acde abdg d deg
ab( ac dg ) de( ac dg )
( ab de )( ac dg )
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
291

292. Метод функціональної декомпозиції проста розділова і загальний випадок

X1
f a bd bc ac
Ф1
Ф2
X2
f(X1,X2)
2 1 d 1 c
X1
Ф1
f(X1,X2,X3 )
X3
X2
1 a b
Ф2
f ab ade bc d be
1 b de
2 1 a 1 ( c e )
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
292

293. Багаторозрядний суматор

n
n
НУЛП 20192020 н.р.
A
B
Ci
S
Co
n
n
n
SUM
A
B
Ci
Глухов В.С. Комп'ютерна логіка
S
n
Co
293

294. 4-розрядні суматори (у прямому, оберненому і доповняльному кодах)

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
294

295. Повний однорозрядний двійковий суматор

Co ABCi ABCi ABCi ABCi BCi ACi AB
S A BCi ABCi AB Ci ABCi
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
295

296. Функціональна схема повного однорозрядного двійкового суматора

НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
296

297. Повний однорозрядний двійковий суматор (матрична схема)

SUM
A
B
CI
S
CO
Входи
Матриця
інверторів
(елементі
в НЕ)
Матриця кон'юнкторів
(елементів І)
І 0 І1 І 2 І 3 І 4 І 5 І 6
A
A
A
B
- точки, де є
з'єднання
B
B
CI
CI
CI
Co ABCi ABCi AB Ci ABC i BCi AC i AB
S A BCi ABCi AB Ci ABCi
Виходи
АБО0
S
CO
АБО1
A B CI
BC I
AB
A B C I ABC I AC I
A B CI
Матриця диз'юнкторів
(елементів АБО)
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
297

298. Двійкові однорозрядні напівсуматор (а) та повний суматор (б)

a
c0 = ab;
s
b
s ab ab ( a b )co
a
b
ci
co
co
Ci
&
a
s
1
a
b
НУЛП 20192020 н.р.
s
б
а
1
A
a
s
.
&
ab
co
B
b
b
S
s
co
1
Ci
co
Глухов В.С. Комп'ютерна логіка
298

299. Мінімізація сукупності (системи, набору) ФАЛ – метод функціональної декомпозиції

• Сукупність 3-х ФАЛ
– Ціна - 12
• f0 = abc V d;
• f1 = abc V e;
• f2 = abc V g;
• Сукупність 4-х ФАЛ
– Ціна – 9
• Ф = abc;
• f0 = Ф V d;
• f1 = Ф V e;
• f2 = Ф V g;
• Сукупність 3-х ФАЛ?
– Ціна - 12
• f0 = (/a)bc V d;
• f1 = a(/b)c V e;
• f2 = abc V g;
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
299

300. Багатозначні логіки. Нечітка логіка

• Тризначна логіка Лукасевича {0,1/2,1}
(ні, може бути, так)
• N-значна логіка Лукасевича {0/n-1,1/n-1, …,n-1/n-1}
a 1 a; a & b min( a ,b ); a b max( a ,b )
• Тризначна логіка Поста {0,1,2}
• N-значна логіка Поста {0,1,2, …,n-1}
a ( a 1 ) mod N ; a & b min( a ,b ); a b max( a ,b )
НУЛП 20192020 н.р.
Глухов В.С. Комп'ютерна логіка
300