Информатика

Обзор курса

Курс состоит из лекций и семинаров. Форма итоговой аттестации – экзамен.

Темы лекций:

  1. Введение. Предмет информатики. Системы счисления.
  2. Арифметические операции в традиционных системах счисления. Правила преобразования чисел между системами счисления.
  3. Особенности представления информации в компьютере. Представление целых чисел. Особенности реализации арифметических операций в конечном числе разрядов.
  4. Представление вещественных чисел. Формат с плавающей запятой. Особенности арифметических операций.
  5. Представление текстовой информации. Кодировки.
  6. Алгебра логики. Основные логические операции и их таблицы истинности. Основные законы алгебры логики. Формальное решение логических задач.
  7. Булевы функции. Канонические формы логических функций. Полные системы булевых функций.
  8. Минимизация булевых функций. Минимизирующие карты Карно. Метод Куайна-МакКласки.
  9. Алгебра переключательных схем. Логические схемы. Сумматор. RS-триггер.
  10. Алгоритмы. Машина Тьюринга. Альтернативные определения алгоритма. Теория вычислимости и проблема останова.
  11. Алгоритмическая сложность. Алгоритмы поиска. Алгоритмы сортировки.
  12. Основы теории информации. Формула Хартли. Формула Шеннона.
  13. Структуры данных
  14. Аппаратное обеспечение

Темы семинарских занятий:

  1. Преобразование чисел между системами счисления.
  2. Арифметические операции с целыми числами в конечном числе разрядов.
  3. Арифметические операции с вещественными числами.
  4. Алгебра логики. Логические задачи.
  5. Минимизация булевых функций.
  6. Машина Тьюринга. Машина Поста.

Упражнения (pdf):

  1. Системы счисления
  2. Алгебра логики
  3. Машина Тьюринга

Вопросы к экзамену

Рекомендованная литература

  1. Е.В. Андреева, Л.Л. Босова, И.Н. Фалина. Математические основы информатики.
  2. А.С. Грошев, П.В. Закляков. Информатика, 3-е изд, М.: ДМК Пресс, 2015 – 588 с. ISBN: 978-5-97060-304-8. Главы 1-4, 7.
  3. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ, 3-е издание — М.: «Вильямс», 2013. — 1328 с.
  4. А.Я. Савельев. Основы информатики [есть в библиотеке]
  5. В.А. Острейковский. Информатика. Главы 2, 3 [есть в библиотеке]