Основи інформатики: тренувальні задачі й екзаменаційні питання

Системи числення, алгоритми й складність, структури даних, бази даних і SQL, а також комп’ютерні мережі: широка основа першого курсу інформатики.

Тренуйте цей курс безкоштовноТренувати цей курсСкласти пробний іспитБезкоштовних задач щодня: 5. Без картки.

Шпаргалка-підсумок (PDF)Аркуші з формулами, кроки методів і задачі для практики з повними розв’язками, готові до друку.

Теми цього курсу

  1. Системи численняз двійкової і шістнадцяткової в десяткову · додатковий код · біти, діапазони і пам'ятьрозрахунки
  2. Логіка висловлювань і доведеннятаблиці істинності · еквівалентності та методи доведення · квантори та міркуваннярозрахунки
  3. Цифрова логіка: вентилі, карти Карно та тригеривентилі, таблиці істинності та затримки · булева алгебра, карти Карно та мультиплексори · байдужі стани, тригери та лічильникирозрахунки
  4. Теорія чисел і арифметика за модулемНСД і залишки · обернені елементи та конгруенції · степені за модулем і RSAрозрахунки
  5. Алгоритми та складністьключові терміни й факти · застосування понять · кейси та аналізтест
  6. Структури данихключові терміни й факти · застосування понять · кейси та аналізтест
  7. Теорія графівстепені та ребра · ейлерові шляхи та дерева · найкоротші шляхи та остовні дереварозрахунки
  8. Бази даних і SQLключові терміни й факти · застосування понять · кейси та аналізтест
  9. Комп'ютерні мережіключові терміни й факти · застосування понять · кейси та аналізтест
  10. Підмережі IPv4хости в підмережі · поділ мережі · діапазони адресрозрахунки

Поради до іспиту: Основи інформатики

  • Переводьте між двійковою й шістнадцятковою системами групами по чотири біти.
  • У SQL WHERE фільтрує рядки до групування, а HAVING фільтрує групи після нього.
  • Указуйте складність у найгіршому випадку, якщо не питають про середній.

Розв’язані приклади

Системи численняЛегка
ваги розрядів2256B16E1

Переведіть шістнадцяткове число 0x2BE у десяткове. Знайдіть N.

0x2BEA = 10 … F = 15

Знайти: N

Показати підказки
  1. Шістнадцяткові розряди справа варті 1, 16, 256, 4096.
  2. Замініть літери їхніми значеннями (A = 10 … F = 15), помножте на вагу розряду і додайте.
  3. 2 = 2, B = 11, E = 14.
Показати відповідь і покроковий розв’язок

Позиційні системи числення: кожна цифра варта свого значення, помноженого на степінь основи. У двійковій системі розряди варті 1, 2, 4, 8, 16, …, у шістнадцятковій 1, 16, 256, …, де A–F означають 10–15. У 8-бітовому додатковому коді крайній лівий біт вартий −128 замість +128; так зберігаються від'ємні числа.

Помножте кожну цифру на вагу її розряду

2·256 + 11·16 + 14·1 = 702

Відповідь

0x2BE = 702
Логіка висловлювань і доведенняСередня
(b → a) ∧ (c → a)b → (c → a)b ∧ (c → a)(b → c) → a

Яка формула логічно еквівалентна (b ∧ c) → a? Клікніть її.

(b ∧ c) → a
  1. 1(b → a) ∧ (c → a)
  2. 2b → (c → a)
  3. 3b ∧ (c → a)
  4. 4(b → c) → a
Показати підказки
  1. Еквівалентні формули збігаються в кожному рядку таблиці істинності. Один рядок, де вони відрізняються, виключає варіант.
  2. Спробуйте рядок, що робить (b ∧ c) → a рівним 0, і перевірте, які варіанти там теж дорівнюють 0.
  3. Експортація: (a ∧ b) → c ≡ a → (b → c). Обидві дорівнюють 0 лише за a = 1, b = 1 і c = 0.
Показати відповідь і пояснення

Логічна еквівалентність: дві формули еквівалентні (≡), коли мають однакове значення в кожному рядку таблиці істинності. Тавтологія дорівнює 1 у кожному рядку, суперечність — 0 у кожному рядку, а випадкова формула — ні те, ні інше. Корисні закони: закони де Моргана, ¬(a ∧ b) ≡ ¬a ∨ ¬b і ¬(a ∨ b) ≡ ¬a ∧ ¬b; a → b ≡ ¬a ∨ b ≡ ¬b → ¬a (контрапозиція); ¬(a → b) ≡ a ∧ ¬b; а також закони дистрибутивності, a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c).

Закон

Експортація: (a ∧ b) → c ≡ a → (b → c). Обидві дорівнюють 0 лише за a = 1, b = 1 і c = 0.
(b ∧ c) → a ≡ b → (c → a)

Перевірте за таблицею істинності

a = 1, b = 1, c = 1: 1 | 1 1 1 1
a = 1, b = 1, c = 0: 1 | 1 1 1 1
a = 1, b = 0, c = 1: 1 | 1 1 0 1
a = 1, b = 0, c = 0: 1 | 1 1 0 1
a = 0, b = 1, c = 1: 0 | 0 0 0 0
a = 0, b = 1, c = 0: 1 | 0 1 1 1
a = 0, b = 0, c = 1: 1 | 0 1 0 0
a = 0, b = 0, c = 0: 1 | 1 1 0 0

Відповідь

b → (c → a)

Стовпці після риски — це варіанти в показаному порядку.

Як проходить тренування

  • «Тренувати цей курс» змішує задачі з усіх його тем, як на справжньому іспиті.
  • Кожна задача має нові значення, тож ви вивчаєте метод, а не відповідь.
  • Застрягли? Спершу відкрийте невелику підказку, а повне пояснення — лише коли воно знадобиться.
  • Пробні іспити обмежені в часі й не мають підказок, а наприкінці ви отримуєте результат і повний розбір.

Калькулятори для цього курсу

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

Пов’язані курси

Комп’ютерні мережіАлгоритми та структури данихДискретна математикаЦифрова електронікаПідготовка до іспиту FE Electrical and ComputerЕлектроніка 1
Тренуйте цей курс безкоштовноТренувати цей курсСкласти пробний іспитБезкоштовних задач щодня: 5. Без картки.