Функциональное программирование: когда программа — это математика

Функциональная парадигма основана на идее, что вычисления — это применение функций, которые не изменяют состояние.

Главное правило:
Функция при одинаковых входных данных всегда возвращает один и тот же результат и не имеет побочных эффектов.

Основные признаки:
• отсутствие изменяемых переменных;
• функции как «граждане первого класса»;
• рекурсия вместо циклов;
• map, filter, reduce;
• композиция функций.

Пример (Python, функциональный стиль):

Посчитаем сумму чисел от 1 до n без циклов и изменяемых переменных.

from functools import reduce

n = 5
result = reduce(lambda a, b: a + b, range(1, n + 1))
print(result) # 15

Или ещё более функционально — через встроенную функцию:
sum(range(1, n + 1))
Никакого изменения состояния — просто применяем функции к данным.

Примеры языков:
• Haskell
• F#
• Lisp, Clojure
• JavaScript (частично)
• Python (частично)

Когда применять:
• Много параллельных вычислений — отсутствие модификации состояния делает код потокобезопасным.
• Нужна ясная математическая логика.
• Хотите писать компактный и легко тестируемый код.

Объектно-ориентированное программирование: когда всё — это объекты

Объектно-ориентированное программирование (ООП) моделирует программу как набор объектов, которые представляют сущности мира и взаимодействуют между собой.

Основные принципы ООП:
• Инкапсуляция — скрываем внутреннее устройство объекта.
• Наследование — один класс может расширять другой.
• Полиморфизм — общий интерфейс, разные реализации.
• Абстракция — выделение значимых свойств сущности.

Пример на Python

Создадим простую иерархию животных.
class Animal:
def speak(self):
pass

class Dog(Animal):
def speak(self):
return "Гав!"

class Cat(Animal):
def speak(self):
return "Мяу!"

animals = [Dog(), Cat()]

for a in animals:
print(a.speak())

Вывод:
Гав!
Мяу!

Здесь работает полиморфизм: метод speak() вызывается одинаково, но ведёт себя по-разному.

Примеры языков:
• Java
• C#
• Python (полностью поддерживает ООП)
• C++
• Swift

Когда применять:
• Когда нужно моделировать сложные сущности и отношения.
• Для больших проектов.
• В бизнес-логике, где есть объекты: пользователи, документы, счета.

Логическое программирование: когда программа — это набор фактов и правил

Логическое программирование основано на идее, что программа — это знание, а выполнение — это логический вывод.
То есть вместо того, чтобы объяснять компьютеру как найти ответ, вы описываете что является истинным, а система сама выводит результат.

Главный представитель — язык Prolog.

Основные концепции:
• Факты — утверждения об объекте или отношении.
• Правила — логические зависимости между фактами.
• Запросы (queries) — вопросы к программе.
• Унификация — сопоставление шаблонов.
• Поиск решения — Prolog сам перебирает варианты и находит подходящие.

Пример: семейные отношения (Prolog)

Факты:
parent(anna, ivan).
parent(sergey, ivan).
parent(ivan, dima).


Это означает:
Анна — родитель Ивана
Сергей — родитель Ивана
Иван — родитель Димы

Правило:
grandparent(X, Y) :- parent(X, Z), parent(Z, Y).

Значение:
X — дед/бабушка Y, если X — родитель Z, а Z — родитель Y.

Запрос:
?- grandparent(X, dima).

Ответ Prolog:
X = anna ;
X = sergey ;
false.

Компьютер сам делает логический вывод. Нам не нужно описывать алгоритм — только знания.

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

Декларативное программирование: когда важен результат, а не путь к нему

Декларативное программирование — это общий подход, в котором программист описывает, что нужно получить, а не как именно.

Фактически логическое, функциональное и SQL — это разновидности декларативного подхода.

Главная идея:
Программа описывает правила и свойства результата, а не последовательность шагов.

Особенности декларативной парадигмы:
• минимум изменяемого состояния,
• код ближе к описанию задачи, чем к алгоритму,
• возможность оптимизаций со стороны интерпретатора/движка,
• часто используются выражения, а не команды.

Примеры декларативных подходов:

1) SQL (чисто декларативный язык)

В SQL мы описываем, какие данные хотим получить.
SELECT name FROM users WHERE age > 18;

Это что нам нужно.
Но мы не указываем:
• как искать,
• по какому индексу,
• какой алгоритм сравнения использовать.
База данных сама выбирает оптимальный путь.

2) HTML — описание структуры, а не алгоритма
<p class="text">Привет!</p>
Мы описываем структуру документа, но не "рисуем" текст по пикселям.

3) Функциональное программирование (частный случай декларативного, Python)
result = sum([x * x for x in range(1, 6)])
Мы описываем что: сумму квадратов.
А не как: перебрать список, вести счётчики и т. д.

4) Конфигурационные языки (Terraform)
resource "aws_s3_bucket" "my_bucket" {
bucket = "example"
}

Мы описываем желаемое состояние: «должен быть bucket с именем example».
Terraform сам вычисляет шаги: создать, удалить, обновить.

Где применяется декларативное программирование:
• запросы к данным (SQL, GraphQL),
• инфраструктура (Terraform, Ansible),
• UI-разработка (React — декларативный),
• аналитические и научные вычисления,
• шаблонизация, конфигурация.

Основные битовые операции

1. AND (&) — Побитовое И

• Правило: Результат равен 1, только если оба соответствующих бита равны 1.

• Таблица истинности:
0 & 0 = 0,
0 & 1 = 0,
1 & 0 = 0,
1 & 1 = 1.

• Пример: 5 & 3
5 = 00000101
3 = 00000011
Результат: 00000001 (что равно 1)

• Применение:
- Маскирование: Выделение конкретных битов. Например, x & 1 проверяет чётность (младший бит).
- Очистка битов: x & ~(1 << n) сбрасывает бит в позиции n в 0.

2. OR (|) — Побитовое ИЛИ

• Правило: Результат равен 1, если хотя бы один из соответствующих битов равен 1.

• Таблица истинности:
0 | 0 = 0,
0 | 1 = 1,
1 | 0 = 1,
1 | 1 = 1.

• Пример: 5 | 3
5 = 00000101
3 = 00000011

• Результат: 00000111 (что равно 7)

• Применение:
- Установка битов: x | (1 << n) устанавливает бит в позиции n в 1.

3. XOR (^) — Побитовое исключающее ИЛИ

• Правило: Результат равен 1, если соответствующие биты разные.

• Таблица истинности:
0 ^ 0 = 0,
0 ^ 1 = 1,
1 ^ 0 = 1,
1 ^ 1 = 0.

• Пример: 5 ^ 3
5 = 00000101
3 = 00000011

• Результат: 00000110 (что равно 6)

• Ключевые свойства:
x ^ x = 0
x ^ 0 = x
x ^ y = y ^ x (коммутативность)
(x ^ y) ^ z = x ^ (y ^ z) (ассоциативность)

• Применение:
- Обмен значений без временной переменной: a ^= b; b ^= a; a ^= b;
- Шифрование: Базовый шифр, так как дважды применённый XOR с одним ключом возвращает исходное число.
- Поиск уникального элемента: В массиве, где все элементы парные, кроме одного, XOR всех чисел найдёт уникальный.

4. NOT (~) — Побитовое НЕ (инверсия)

• Правило: Инвертирует каждый бит (0 становится 1, 1 становится 0).

• Важно: Результат зависит от разрядности числа (количества бит).

• Пример (8-битное): ~5
5 = 00000101
~5 = 11111010 (что равно -6 в дополнительном коде для знаковых чисел)

• Применение: Часто используется в комбинации с другими операциями для создания масок.

5. Сдвиги влево (<<) и вправо (>>)

• x << n — Сдвигает биты числа x на n позиций влево. Освободившиеся справа биты заполняются нулями.
- Эффект: Умножение на 2^n. 5 << 1 = 10 (52), 5 << 3 = 40 (58).
- Применение: Быстрое умножение на степень двойки, установка битов.

• x >> n — Сдвигает биты числа x на n позиций вправо.
- Логический сдвиг (>>>): Освободившиеся слева биты всегда заполняются нулями. Для беззнаковых чисел.
- Арифметический сдвиг (>> для знаковых): Освободившиеся слева биты заполняются значением старшего (знакового) бита. Сохраняет знак для отрицательных чисел.
- Эффект: Целочисленное деление на 2^n (с округлением в меньшую сторону). 13 >> 1 = 6 (13/2=6.5 -> 6), -8 >> 2 = -2.
- Применение: Быстрое деление на степень двойки.

Практические примеры и трюки
• Проверка чётности: if ((x & 1) == 0) — чётное.
• Умножение/деление на 2: x << 1 (умножить на 2), x >> 1 (разделить на 2).
• Включение n-го бита: x |= (1 << n)
• Выключение n-го бита: x &= ~(1 << n)
• Переключение n-го бита (0→1, 1→0): x ^= (1 << n)
• Проверка, включён ли n-й бит: if (x & (1 << n))
• Извлечение младших k бит: x & ((1 << k) - 1)
• Округление до степени двойки (для положительных): 1 << (int)(log2(x) + 1)
• Быстрая проверка, является ли число степенью двойки: (x & (x - 1)) == 0 (и x > 0).
• Подсчёт количества единичных битов (вес Хэмминга): Есть эффективные алгоритмы с использованием битовых операций.

«Почему в Minecraft можно собрать настоящий рабочий компьютер»

Turing complete — значит, система может выполнять любые вычисления, как обычный процессор.

Практические примеры, которые реально существуют:
• В Minecraft на redstone-схемах собрали процессор, который запускает Doom и даже Tetris.
• Шаблоны в C++ (до C++11) были Turing complete — на этапе компиляции можно было вычислять числа, запускать циклы и даже решать задачки. Программисты писали на этом «код до кода».
• Теоретически в PowerPoint с анимациями и гиперссылками можно закодить простую программу.

Зачем это знать? Понимаешь, что ограничение — не в языке, а в твоей фантазии. И что даже в «игрушках» можно строить настоящие вычислительные машины.

«Почему антивирус никогда не поймает 100% вирусов»

Теорема Райса (1953): нельзя написать программу, которая для любого кода точно скажет, делает ли он что-то «плохое» (вирус, бесконечный цикл, вывод определённой строки и т.д.).
Практические последствия:

• Антивирусы работают по сигнатурам (ищут известные вирусы) и эвристикам (подозрительное поведение) → всегда будут ложные срабатывания и пропуски.
• Статический анализ кода никогда не будет идеальным — всегда либо пропустит баг, либо поднимет ложную тревогу.
• Автоматическое доказательство корректности программы возможно только для очень простых случаев.

Пишите тесты, код-ревью и не надейтесь, что инструмент найдёт всё за вас. Это фундаментальная граница.

«Почему ваш сервер может думать, что сейчас 1970 год (и сломать всё)»

В распределённых системах время — это проблема. NTP синхронизирует часы, но даже 100 мс расхождения могут сломать логику.

Реальные кейсы:
• Токены JWT истекают «раньше времени» на одном сервере.
• Логи в ELK/Kibana идут не по порядку — ищешь баг часами.
• В 2024 году у одной крупной биржи был сбой: один сервер отстал на 2 секунды → ордера исполнялись в неправильном порядке.

Практика:
• Используйте monotonic clock для измерения интервалов.
• Для распределённых транзакций — logical clocks (Lamport timestamps) или Google TrueTime/Spanner-подход.
• В Kubernetes включайте NTP + chrony.

Вывод: никогда не полагайтесь на System.currentTimeMillis() для критичной логики.

«False sharing: почему ваш многопоточный код тормозит в 10 раз»

На современных CPU данные в памяти кэшируются по линиям кэша (обычно 64 байта).

Если два потока пишут в разные переменные, но они лежат в одной линии кэша — CPU вынужден инвалидировать кэш у обоих потоков при каждой записи.

Это false sharing — производительность падает в десятки раз, хотя гонок данных нет.

Практика:
• В Java: объявляйте счётчики как volatile long отдельно и паддите до 64 байт (или используйте @Contended).
• В Go/Rust: следите за выравниванием структур.
• В 2025 году это всё ещё актуально на серверах с 128+ ядрами.

Как найти: perf c2c, Intel VTune или просто подумайте, когда многопоточка не даёт speedup.

Вывод: профилируйте не только логику, но и железо.

«Feature flags: как выкатывать фичи без страха сломать прод»

Feature flag — переключатель в коде/конфиге, который включает/выключает новую фичу.

Практика:
• Выкатываете код с новой оплатой Apple Pay, но flag = off.
• Включаете для 1% пользователей → мониторите → для всех.
• Если баг — выключаете за секунду, без отката.

Инструменты 2025: LaunchDarkly, Unleash, Flagsmith, даже простая таблица в БД.

Кейс: Netflix, Facebook, GitLab — всё на флагах. В 2024 году одна компания откатила баг за 30 секунд благодаря флагу, а не за час деплоем.

Вывод: если проект больше «hello world» — внедряйте feature flags. Это стандарт современной разработки.

Сколько электричества жрёт ваш код

На больших масштабах разница ощутимая. Сортировка миллиона элементов пузырьком может съесть в разы больше энергии, чем Timsort. В дата-центрах уже давно оптимизируют под это — иногда простая смена структуры данных экономит 30–50%.

Простой способ замерить самому — библиотека codecarbon.

from codecarbon import EmissionsTracker
import random

tracker = EmissionsTracker()
tracker.start()

# Пример "прожорливого" кода
data = [random.randint(0, 1000) for _ in range(1_000_000)]
data.sort()  # Timsort — эффективно

# А вот пузырёк (не запускайте на миллионе, убьёт время)
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

# bubble_sort(data[:100_000])  # попробуйте на меньшем

emissions = tracker.stop()
print(f"Выбросы CO₂: {emissions:.6f} кг")

Попробуйте сравнить разные сортировки — разница удивит. В 2026 году это уже не прихоть, а реальная экономия.

Генеративное искусство через алгоритмы

Perlin noise, клеточные автоматы, L-системы — основа не только процедурной генерации в играх, но и современного цифрового искусства.

Простейший пример на p5.js (запустите в браузере на editor.p5js.org):

function setup() {
  createCanvas(800, 800);
  noiseDetail(4, 0.5);
}

function draw() {
  background(0);
  for (let x = 0; x < width; x += 10) {
    for (let y = 0; y < height; y += 10) {
      let n = noise(x * 0.01, y * 0.01, frameCount * 0.01);
      let brightness = map(n, 0, 1, 0, 255);
      fill(brightness, brightness * 0.8, 255);
      noStroke();
      ellipse(x, y, 15);
    }
  }
}

Получается плавно меняющийся облачный паттерн. Поиграйтесь с параметрами — баланс энтропии решает всё.

Подписи Лампорта — криптография без «магии»

RSA и ECDSA держатся на сложности факторизации. А подписи Лампорта — только на хэш-функциях (например, SHA-256). Они post-quantum по умолчанию.
Минимальная реализация на Python:

import os
import hashlib

def generate_key():
    private_key = [os.urandom(32) for _ in range(256 * 2)]
    public_key = [hashlib.sha256(x).digest() for x in private_key]
    return private_key, public_key

def sign(message, private_key):
    h = hashlib.sha256(message).digest()
    signature = []
    for i in range(256):
        bit = (h[i // 8] >> (i % 8)) & 1
        signature.append(private_key[i + bit * 256])
    return signature

def verify(message, signature, public_key):
    h = hashlib.sha256(message).digest()
    for i in range(256):
        bit = (h[i // 8] >> (i % 8)) & 1
        computed = hashlib.sha256(signature[i]).digest()
        if computed != public_key[i + bit * 256]:
            return False
    return True

# Пример использования
priv, pub = generate_key()
msg = b"Hello, Lamport!"
sig = sign(msg, priv)
print(verify(msg, sig, pub))  # True

Ключи огромные, но принцип работает. Для реального использования берите SPHINCS+.

Нейронные сети и мозг: больше различий, чем сходства

Многие думают, что нейросети копируют мозг. На деле:
• биологические нейроны — аналоговые, асинхронные, с химическими сигналами
• backpropagation в мозге не обнаружен
• мозг использует крайне разреженное кодирование и тратит ~20 Вт

Различия помогают: спайковые сети и neuromorphic чипы вроде Intel Loihi уже эффективнее обычных NN на edge-устройствах.

ИИ не повторяет биологию, а идёт своим путём — и это хорошо.

Хэш-функции везде, где не ждёшь

Кроме таблиц, хэши используют:
• LSH для поиска похожих векторов
• MinHash для сравнения геномов и документов
• Merkle trees в Git и блокчейнах
Быстрая не крипто хэш-функция — xxHash. Установка: pip install xxhash

import xxhash

data = b"очень длинная строка или большой файл"
hash_value = xxhash.xxh64(data).digest()
print(hash_value.hex())

# Для стриминга больших данных
h = xxhash.xxh64()
with open("big_file.bin", "rb") as f:
    for chunk in iter(lambda: f.read(4096), b""):
        h.update(chunk)
print(h.digest().hex())

Быстрее MurmurHash, коллизий почти нет. Отлично для кэшей и bloom-фильтров.

Формальная верификация уже спасает миллиарды

Amazon доказал корректность частей S3 и DynamoDB с помощью TLA+. Microsoft верифицирует гипервизор в Dafny.

Простейший пример в PlusCal (транслируется в TLA+):

(*--algorithm mutex
variables flag = [i \in {1,2} |-> FALSE];

process proc \in {1,2}
begin
  A: flag[self] := TRUE;
  B: await flag[3-self] = FALSE;
  C: skip;  (* critical section *)
  D: flag[self] := FALSE;
  E: goto A;
end process;
end algorithm;*)

Этот алгоритм НЕ корректный (возможен deadlock). TLC (model checker) найдёт ошибку за секунды.

Начать легко: установите Toolbox, попробуйте на простых примерах mutual exclusion.

Теория формальных языков изучает структуры и свойства языков, описанных формальными системами.

Основные аспекты:

1, Грамматики: Формальные правила, которые определяют синтаксис языка. Основные типы:
- Контекстно-свободные грамматики (КС-грамматики): Определяют синтаксис языков, которые можно описать с помощью синтаксических деревьев (например, язык программирования C).
- Контекстно-зависимые грамматики: Более мощные и сложные, позволяют описывать языки с контекстуальными зависимостями (например, естественные языки).

2. Автоматы: Математические модели для описания и распознавания языков.
- Конечные автоматы: Описание языков с помощью простых состояний и переходов (например, регулярные языки).
- Стековые автоматы: Модели с использованием стека, применимые к контекстно-свободным языкам.

3. Языки:
- Регулярные языки: Определяются регулярными выражениями и распознаются конечными автоматами.
- Контекстно-свободные языки: Определяются контекстно-свободными грамматиками и распознаются стековыми автоматами.
- Контекстно-зависимые языки: Определяются контекстно-зависимыми грамматиками и распознаются более мощными машинами.

4. Классы языков: Иерархия языков в зависимости от сложности грамматик и автоматов, таких как регулярные, контекстно-свободные, контекстно-зависимые и рекурсивно перечисляемые языки.

5. Операции над языками: Способы объединения, пересечения, дополнения и другие операции для работы с языками.

Стоимость операций: CPU, кэш и память

Асимптотическая сложность не отражает реальную стоимость операций.
Современный процессор выполняет инструкции за наносекунды, но доступ к:

• L1 кэшу — ~1–4 такта
• L3 — десятки тактов
• RAM — сотни тактов

Алгоритмы с линейным проходом по памяти часто выигрывают у «умных» алгоритмов со случайным доступом.

Пример:
Поиск минимума в массиве — O(n) — почти всегда быстрее бинарного поиска в несмежных структурах, несмотря на худшую формальную сложность.
Причина — предвыборка и кэш-линейность.

Хеширование, коллизии и деградация

Хеш-таблицы зависят от:
• качества хеш-функции
• стратегии разрешения коллизий
• коэффициента заполнения

Открытая адресация страдает от кластеризации, цепочки — от неравномерного распределения.

Пример:
При нагрузке > 0.75 среднее число проб резко растёт.
Рехеширование — операция O(n) и может стать латентным пиком в продакшене, если не контролировать рост.

Реальность: O(1) — это статистическое обещание, а не гарантия.

Таблица разделов

Таблица разделов — часть главной загрузочной записи (MBR), состоящая из четырёх записей по 16 байт. Каждая запись описывает один из разделов жёсткого диска. Первая запись находится по смещению 1BEh от начала сектора, содержащего MBR, каждая последующая запись вплотную примыкает к предыдущей.

Для создания на диске более 4 разделов используются расширенные разделы, позволяющие создать неограниченное количество логических дисков внутри себя.

Адреса начала и конца раздела задаются в формате CHS, используемом традиционными функциями дискового сервиса BIOS, из-за чего номер цилиндра разорван на две части: старшие два бита хранятся в двух старших битах слова, отведённого под номера цилиндра и сектора; за ними следуют шесть бит номера сектора, а младшие восемь бит номера цилиндра занимают весь младший байт слова. Если задать корректный адрес с помощью формата CHS невозможно, все три байта полей начала и конца раздела должны содержать FFh