Ещё от Виталика. Есть такая интересная структура данных: Merkle tree. В посте же речь пойдёт о Verkle tree. Схожая штука, но с гораздо более компактными доказательствами.

#datastructure #crypto #cs

Попался занимательный пример того, на что в целом способны современные компиляторы, но что не доходит до мейнстримных языков. Речь пойдёт про язык Dafny, который умеет доказывать или опровергать в compile time своего рода ассёрты, которые мы разбрасываем по своему коду.

#compiler #language #cs

Хороший разбор bloom filters. Структура данных, которая даёт за константное время и маленькую память проверить, входит ли значение в множество. Но есть один нюанс: если ответ "не входит", то точно не входит. А вот если ответ "входит", то может быть и false positive. Коллизии, мать их.

#cs #datastructure

Дай человекам что угодно, они пренепременно попытаются на этом вычислять. Допрыгались. FLAT ORIGAMI IS TURING COMPLETE. Пэйпер не пытайтесь понять, поберегите рассудок. Чисто отрывками и очень аккуратно, без перегибов.

#science #math #cs

Приятный интерактивный разбор того, как работает одна из простых версий CRDT.

#cs #network #datastructure

Хочется закрыть ту серию постов про CRDT. Про сам алгоритм уже по сути не будет. Будет про то, как его прикрутить к игрушечному pixel art редактору, и как разными странными способами сэкономить на размере перегоняемых данных.

#cs #network #datastructure

Здесь уже знакомый нам автор предлагает попробовать реализовать некоторые завораживающие алгоритмы и структуры данных.

#cs #algorithm #datastructure

Просто красиво. Кнут 3:16. Сборник 16-х (индексация с 0) предложений 3-их частей из книг дядьки Дональда.

#humor #cs

Тут, оказывается, биг дил случился. Доказали, что BB(5) = 47,176,870. Практического смысла в Busy Beaver не очень много, прямо скажем, но всё равно интересно.
- Тут можно почитать хорошую статью с деталями, историей и т.п.
- Тут само объявление об успехе
- А тут хорошие посты про это же, но кратко и прямо в телеге

#cs #math #science

Мы уже запускали Doom везде, где только можно, доказывали, что Java generics - Turing complete. Тут вот занимаются ещё более странным: доказывают, что комбинация find и mkdir - тоже полная по Тьюрингу.

#humor #cs #bash

Тут какая-то странная история. Как будто челу дали обычную задачку с LeetCode, но не совсем точно передали условия, существенно повысив сложность. А чел взял, да и решил. The problem is to deep copy a linked list where each node references a random list element in addition to usual linkage, короче.

#cs #algorithm #datastructure

Бывают такие шутки, которые в юности услышишь, и посмеёшься. А потом через несколько лет встретишь, и снова посмеёшься. Вот принёс вам, посмеяться:
- Sleep sort - всё достаточно линейно, но есть нюанс
- Stalin sort - всё, что не подчиняется правилу, должно уйти
- Permutation sort - полный перебор
- Bogosort - да, можно хуже, чем полный перебор

#cs #algorithm #sorting

Серия из двух постов про поиск коллизий объектов, начинаем наивно, постепенно оптимизируем. Все красиво, на пальцах, с интерактивом и плясками.

#gamedev #algorithm #cs

Чудесная лекция: Richard Feynman Computer Science Lecture - Hardware, Software and Heuristics.

#talk #cs

Оу вау. Машина Тьюринга из лего! Все эти звёзды смерти и соколы тысячелетия просто встали и вышли.

#cs #lego

Очень занимательный пост подвернулся. Почему криптографические конструкции опираются не на NP-полные задачи, а на задачи, случайная формулировка которых достаточно сложна.

#cryptography #math #cs

Тут прямо нормальный такой разбор XOR, как на него можно смотреть, и что с ним можно интересного делать. Я помню, как впервые понял, что XOR круче всяких AND и OR: препод дал задачку найти число, у которого нет двойника, в длинном массиве случайного порядка за линейное время и константную память ([3, 1, 2, 3, 4, 2, 1] => 4). Вот она, кстати, на LeetCode.

#math #cs #binary

Доказали, что любой алгоритм можно выполнить с тем же успехом, потратив больше времени, но использовав только sqrt(T logT) памяти, где T - время на изначальное выполнение. Прикольно!

#talk #cs #algorithm

Первая часть разбора устройства persistent Clojure vector. Как так получается, что любая манипуляция создаёт новый immutable вектор, но проблем с памятью / производительностью на деле это не создаёт. Разбирается устройство базовых операций: добавить, удалить, поменять элемент по индексу.

#clojure #cs #datastructure

И сразу вдогонку вторая часть: как на таких векторах-деревьях достаточно эффективно делать лукапы.

#clojure #cs #datastructure