Конспект: математика и логика для курса

Понятия

Степень 2^k - произведение k двоек. Логарифм по основанию два log₂ n - сколько раз делить n пополам до единицы. ⌊x⌋ - округление вниз, ⌈x⌉ - вверх.

Порядок роста - как число шагов растёт вместе с размером данных.

Остаток r = a % b: a = b · q + r, 0 ≤ r < b. Двоичная запись - разложение по степеням двойки.

Факториал n! = 1 · 2 · ... · n, 0! = 1. Перестановки - порядки n вещей, их n!. Сочетания C(n, k) - выборы k из n без порядка. Правило произведения - независимые выборы перемножаются.

Высказывание - истинно или ложно. Импликация A → B ложна только при истинном A и ложном B. Квантор - «для всех» или «существует». Контрпример - вход, на котором утверждение «для всех» ложно.

Что унести

2^10 ≈ 10^3      log₂ тысячи ≈ 10   миллиона ≈ 20   миллиарда ≈ 30
двоичных цифр у n:   ⌊log₂ n⌋ + 1        остаток от 2^k = последние k бит

1 + 2 + ... + n       = n(n + 1)/2    цикл с растущим проходом
1 + 2 + 4 + ... + 2^k = 2^(k+1) - 1   последнее больше прежних вместе
пары из n             = n(n - 1)/2    = C(n, 2)
подмножеств           = 2ⁿ            порядков = n!

Остаток суммы и произведения можно брать по ходу счёта. В Python a % b при b > 0 всегда в 0..b-1, и для отрицательных a.

Быстрый Евклид: a, b = b, a % b, пока b не ноль. Остаток меньше делителя - цикл кончается.

not (A and B)  =  (not A) or (not B)
not (A or B)   =  (not A) and (not B)
A → B          =  (not A) or B
не «для всех x: P»  =  «существует x: не P»

Цикл while условие выходит, когда истинно отрицание условия, - часто по одной из двух причин.

Ловушки джокера

int(math.log(1000, 10)) равно 2. Дробный логарифм неточен; для целых - bit_length или деление.

⌈log₂ n⌉ вместо ⌊log₂ n⌋ + 1. На степенях двойки разница в единицу.

Экспонента «просто большая». Вдвое быстрая машина даёт 2ⁿ один лишний элемент.

Упорядоченные пары вместо неупорядоченных. Ответ ровно вдвое больше.

Перебор порядков на двадцати элементах. 20! - два с половиной квинтиллиона.

Остаток отрицательного числа в C. -3 % 2 там -1, признак нечётности ломается.

Двоичные цифры не в том порядке. Первый остаток - младшая цифра.

Отрицание без смены связки. Выход «и», которого не бывает, вместо «или».

«Если B, то A» вместо «если A, то B». Обратное утверждение доказывают отдельно.

Проверка «для всех» примерами. Десять подтверждений ничего не доказывают, один контрпример опровергает.

Проверь себя

Почему в оценке двоичного поиска стоит логарифм, а не корень или деление на два?

Что напечатает print(-17 % 8, 37 % 8) и как увидеть второе в двоичной записи?

Сколько сравнений делает поиск дубликатов «каждый с каждым» на тысяче элементов?

Что верно после выхода из while levo < pravo and a[s] != x?

Чему равно all(x == 7 for x in []) и почему?