Основы информатики: тренировочные задачи и экзаменационные вопросы

Системы счисления, алгоритмы и сложность, структуры данных, базы данных и 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 в каждой строке, а нейтральная формула (contingency) — ни то ни другое. Полезные законы: законы де Моргана, ¬(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. Без карты.