Computer Science

Таблица разделов Таблица разделов — часть главной загрузочной записи (MBR), состоящая из четырёх записей по 16 байт. Каждая запись описывает один из разделов жёсткого диска. Первая запись находится по смещению 1BEh от начала сектора, содержащего MBR, каждая последующая запись вплотную примыкает к предыдущей. Для создания на диске более 4 разделов используются расширенные разделы, позволяющие создать неограниченное количество логических дисков внутри себя. Адреса начала и конца раздела задаются в формате CHS, используемом традиционными функциями дискового сервиса BIOS, из-за чего номер цилиндра разорван на две части: старшие два бита хранятся в двух старших битах слова, отведённого под номера цилиндра и сектора; за ними следуют шесть бит номера сектора, а младшие восемь бит номера цилиндра занимают весь младший байт слова. Если задать корректный адрес с помощью формата CHS невозможно, все три байта полей начала и конца раздела должны содержать FFh

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

Стоимость операций: CPU, кэш и память Асимптотическая сложность не отражает реальную стоимость операций. Современный процессор выполняет инструкции за наносекунды, но доступ к: • L1 кэшу — ~1–4 такта • L3 — десятки тактов • RAM — сотни тактов Алгоритмы с линейным проходом по памяти часто выигрывают у «умных» алгоритмов со случайным доступом. Пример: Поиск минимума в массиве — O(n) — почти всегда быстрее бинарного поиска в несмежных структурах, несмотря на худшую формальную сложность. Причина — предвыборка и кэш-линейность.

Теория формальных языков изучает структуры и свойства языков, описанных формальными системами. Основные аспекты: 1, Грамматики: Формальные правила, которые определяют синтаксис языка. Основные типы: - Контекстно-свободные грамматики (КС-грамматики): Определяют синтаксис языков, которые можно описать с помощью синтаксических деревьев (например, язык программирования C). - Контекстно-зависимые грамматики: Более мощные и сложные, позволяют описывать языки с контекстуальными зависимостями (например, естественные языки). 2. Автоматы: Математические модели для описания и распознавания языков. - Конечные автоматы: Описание языков с помощью простых состояний и переходов (например, регулярные языки). - Стековые автоматы: Модели с использованием стека, применимые к контекстно-свободным языкам. 3. Языки: - Регулярные языки: Определяются регулярными выражениями и распознаются конечными автоматами. - Контекстно-свободные языки: Определяются контекстно-свободными грамматиками и распознаются стековыми автоматами. - Контекстно-зависимые языки: Определяются контекстно-зависимыми грамматиками и распознаются более мощными машинами. 4. Классы языков: Иерархия языков в зависимости от сложности грамматик и автоматов, таких как регулярные, контекстно-свободные, контекстно-зависимые и рекурсивно перечисляемые языки. 5. Операции над языками: Способы объединения, пересечения, дополнения и другие операции для работы с языками.

Обработка артефактов сканирований. Сканирование запустили — а что дальше Запустить security-сканер — лишь половина дела. Гораздо сложнее превратить результаты сканирования в рабочий процесс, который действительно приводит к исправлению уязвимостей, а не к накоплению отчётов «на складе». На открытом уроке разберём, как выстраивать работу с артефактами сканирований в GitLab CI/CD. Поговорим о хранении результатов, передаче их разработчикам и настройке security gates, которые автоматически влияют на сборку и релиз. Обсудим, как встроить безопасность в пайплайн так, чтобы она работала системно и не превращалась в формальность. Урок будет полезен DevSecOps и AppSec-специалистам, DevOps/SRE-инженерам и тимлидам, которые хотят наладить управляемый поток обработки результатов security-сканирований. → Вебинар проходит в формате открытого урока курса «Внедрение и работа в DevSecOps»: https://otus.pw/aZCg/ Реклама. ООО «Отус онлайн‑образование», ОГРН 1177746618576

Формальная верификация уже спасает миллиарды 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.

Хэш-функции везде, где не ждёшь Кроме таблиц, хэши используют: • 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-фильтров.

Hyper-V часто стоит рядом, но у многих остаётся туманом. В итоге виртуалки создаются наугад, сети работают странно, диски растут как попало, а тестовый контур превращается в лотерею. На открытом уроке вы разберёте базу Hyper-V. Установка и первичная настройка роли, создание виртуальной машины, работа с виртуальными дисками и виртуальными сетями, типовые сценарии применения в инфраструктуре. → Записаться на открытый урок курса «Администратор Windows»: https://otus.pw/mc7m/ Реклама. ООО «Отус онлайн‑образование», ОГРН 1177746618576

Нейронные сети и мозг: больше различий, чем сходства Многие думают, что нейросети копируют мозг. На деле: • биологические нейроны — аналоговые, асинхронные, с химическими сигналами • backpropagation в мозге не обнаружен • мозг использует крайне разреженное кодирование и тратит ~20 Вт Различия помогают: спайковые сети и neuromorphic чипы вроде Intel Loihi уже эффективнее обычных NN на edge-устройствах. ИИ не повторяет биологию, а идёт своим путём — и это хорошо.

Подписи Лампорта — криптография без «магии» 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+.