09.03 Введение. Понятие алгоритма. Системы счисления

Представление преподавателей, рассказ об организации семинаров и практикума. Дисциплина в обучении как мера ответственности, а не мера послушания. ИИ и «правило 1000 задач».

Легенда:

• Разбор задачи у доски или быстрый ответ аудитории, если она готова ответить

• ✍️ письменная работа на листочке

TODO ЧСХ, нет активности «выйти к доске», Это правильно или нет?

Понятие алгоритма

• Определение алгоритма

  • Не существует. ∃ только операциональное определение aka «это когда»

• Алгоритм — «это когда»
  1. формализована задача (класс задач)
  2. формализованы однозначно интерпретируемые действия (правила, инструкции и т. п.) при решении задач
  3. формализован исполнитель этих действий:
     1. порядок (не обязательно «последовательность») исполнения, // FIXME: термин "порядок" (действий) слишком намекает на то, что задается в программе.
     2. представление объектов из предметной области задачи
     3. (возможно, иные свойства исполнителя)
  4. есть конечная запись действий (программа),
     1. приводящая к решению задачи за конечное число действий исполнителя
     2. для одной и той же задачи (одного набора входных данных) решение всегда одинаковое
• Собственно, операциональное определение из лекции:
  • Алгоритм — это точно сформулированная совокупность правил для исполнителя, указывающая, как решать задачу, причем такая совокупность должна удовлетворять свойствам
  • полноты,
  • выполнимости,
  • однозначности
  • и конечности 🦾🦿

• Что означают эти термины?

• Задача про Чугунку:

  • Хозяин дал роботу Чугунке следующее задание:
    — Сходи в продуктовый, купи батон колбасы, а если есть яйца — купи десяток.
    Чугунка приходит в магазин.
    — У вас яйца есть? Тогда десять батонов колбасы, пожалуйста!

  • Отсутствие какого свойства алгоритма в этом задании помешало Чугунке?

  • ✍️ Модифицировать задание роботу Чугунке таким образом, чтобы он мог с ним справиться.

Системы счисления

TODO расписать примеры

Принцип формирования целых чисел в позиционных системах счисления: $$\sum_{i=0}"цифра"_i×"основание"^i$$.

• Примеры.

  • перевести $$12345_6$$ в 10-чную форму; степени 6: 6 36 216 1296

• Достоинства двоично и шестнадцатеричной систем счисления

• Перевод из n-ричной в десятичную и обратно (TODO всех задолбали в ЕГЭ, надо ли повторять?)

• Таблица сложения в шестеричной системе счисления в виде квадрата

  • +	1	2	3	4	5
    1	2	3	4	5	10
    2	3	4	5	10	11
    3	4	5	10	11	12
    4	5	10	11	12	13
    5	10	11	12	13	14

• Таблица умножения в троичной системе счисления, начиная с 2-х, в виде одноклеточного квадрата

  • ×	2	3	4	5
    2	4	10	12	14
    3	10	13	20	23
    4	12	20	24	32
    5	14	23	32	41

• Умножение в столбик. $$513_6 * 24_6 = 2200_6$$

  •        5 1 3
         ×   2 4
         -------
         3 3 0 0  ← (513 · 4) = 20₆ (0), 4₆ + перенос 2 = 10₆ (0), 32₆ + перенос 1i = 33₆ (33)
     + 1 4 3 0    ← (513 · 2) = 10₆ (0), 2₆ + перенос 1 = 3₆ (3), 14₆ (14)
         --------
       2 2 0 0 0

• ✍️ Таблицы сложения и умножения в системе с основанием 4, 5 и умножение двух чисел (по вариантам)

  1. $$320132_4 * 23_4$$

  2. $$34201_5 * 42_5$$

• деление в столбик с помощью таблиц

  •   5 1 3 | 2 4           24₆ · 5 = 212₆
    - 2 4   +----
      ---   | 1 5
      2 3 3
    - 2 1 2
      -----
        2 1

• ✍️ Деление 6,5-значного на 2-значное число в той же системе счисления

  1. $$320132_4 : 23_4$$

  2. $$34201_5 : 42_5$$

Принцип формирования дробной части в позиционных системах счисления: $$\sum_{i=1}"цифра"_i×"основание"^-i$$

• Это тот же самый принцип!

• Написать общую формулу для числа с фиксированной точкой

• Правила умножения и деления чисел с фикс. точкой и конечной дробной частью:

  • переводим оба числа в вид $$"целое"×"основание"^k"$$; основание всегда $$10_"основание"$$

  • умножаем или делим два целых
  • вычисляем степень основания (сумма или разность степеней)
  • двигаем точку с учетом степени основания, получаем число с точкой

• $$5.13_6 * 2.4_6 = 513_6 * 10_6^"-2" * 24_6 * 10_6^"-1" = 22000_6 * 10_6^"-2 + -1" = 22_6$$

• ✍️ добыть два знака после точки из примеров на деление (они оба не нацело)
• Перевод числа с фиксированной точкой из n-ричной в десятичную и обратно: просто продолжаем процесс по этой формуле, пока не надоест

  • => Лайфхак: точку можно игнорировать вплоть до последнего момента, а потом поставить куда надо!

• Перевод конечной дроби с фикс. точкой в другую с/с: может получиться бесконечная дробь

  • $$0.1_3$$ -> 10-чную

• Интересные с/с:
  • двоичная - минимум уровней, простейшие операции
  • троичная - максимальная плотность информации, т.к. основание близко к е≈2.718
    • вариант: симметричная -1,0,1 (тоже легко в электрике представлять, но арифметика небанальна)
  • 16-ричная: хорошо переводится в 2-чную и обратно, возникла в связи с кратностью 8 размера ячейки памяти
  • двоично-десятичная: два уровня, но по сути записаны 10-чные числа

• TODO ////// тут закончили //////

• Пример: деление в шестеричной системе с 3 знаками поле запятой

• ✍️ Поделить перевести 2026 в свою систему, в ней поделить на $$"основание"+1$$, перевести обратно