mayton2019

Коробочным решенеим задачи может быть префиксное дерево (Trie) с лимитом в 100Мб
которое в листовых узлах должно хранить списки искомых записей.

Учитывая объемы, списки не влезают. Поэтому можно хранить ссылки на файлы или
на offsets внутри большого файла. Тут уже не теория а эксперимент больше покажут
что подойдет.

Мы также исходим из некого оптимистичного предположения что данные - это все таки
не рандомный шум а какие-то тексты, что позволит делать дерево максимально компактным.
(Чтоб каждый узел не содержал 1 байт а хотя-б цепочку букв).

Так-же как и в индексировании документов. Строится некое векторное представление документа.
И потом похожие векторы - указывают на одинаковые (99.9%) документы. Методик векторизации
много. В основном это токенизация слов и свертывание их к хешу.

Зачем делать безсмысленный makeStep? Пускай он возвращает булево значение.

boolean makeStep(Graph &graph, ValuesTable &table) { .... }

Не было отрицательных свойств среди вершин - значит пускай вернет true.
Тогда будет стоп алгоритма. И не надо будет
делать дополнительных пере-расчетов.

Фильтр Гаусса ничего не знает о цвете. Он просто применяется к матрице вещесвтенных чисел.
Поэтому обычно картинку в формате RGB переводят в трех-слойную вещественную матрицу { double, double, double }
и фильтр Гаусса применяют трижды для каждого слоя. И результат потом снова сводят в RGB.

Есть миллиард хитростей как делать это в целых или в вещественных числах или как использовать SIMD, Parallel
computing e.t.c. но ты сделай сначала самый простой и работающий вариант а потом уже оптимизация.

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

На регулярной основе - я-бы загружал этот файл в базу данных. И там через update обновлял бы поле 90 на 100.
А потом сохранял-бы обратно в CSV файл.

Если задача одноразовая ... ну есть масса утилит типа sed/awk/perl они это делают за 2 минуты.

Самый простой путь - рисовать эту картинку внутри матрицы (растр).
А потом перевести элементы этой матрицы в псевдографику https://en.wikipedia.org/wiki/Box-drawing_character

Но я тебе это не советую, потому что выглядит как сильно грубое разрешение.

Рисование слешами или зведочками возможно. Но это ASCII art. Иногда выглядит красиво
а иногда вообще нечитабельно.

Насколько инфантилен стал программист. Чтоб заставить его думать - нужно показывать спецэффекты.

Я не уверен что стоит вообще искать идеальное решение. Особенно для 800 точек. Задача
пахнет комбинаторной со всеми вытекающими.

Я-бы предложил дать программе время (секунд) или количество итераций через которые
она должна выдать почти-минимальный параллелепипед. Но мы при этом понимаем что это не самый идеальный.

Для малого числа точек (8) можно построить выпуклую оболочку. И попробовать прикладывать
первую грань параллелепипеда к каждой грани выпуклой оболочки. А оставшиеся грани мы можем
получить вращением параллелепипеда до тех пор пока bounding volume не будет минимален.
Учитывая дискретность выпуклой оболочки, поворот тоже может быть дискретным. Например там
проверить штук 20 углов. Вот как-то так.

Мне кажется что дешевле игру запрограммировать чем обучать ей бота.

Просто в случае обучения - ты должен показать все возможные сочетания "стритов", "флешей" и прочего.
И не один а несколько раз. И обеспечить учителя или подкреплять удачные ходы.

Я пока студент, перешёл на второй курс.

Тебя в любом случае градуируют как junior/trainee на первой работе.
И дело даже не в том сколько олимпиад ты прошел и сколько ты книжек прочитал.
Просто звездочки в погонах надо заслужить. Если ты талантлив - то наверное
за год перепрыгнешь уровнеь junior но я советую вообще с этим не спешить.

Нет ничего хуже самозванца. Согласен?

Это - тяжелая книга для новичка. Начните с Вирта или Седжвика.

В ВУЗах такой программы обычно нет. Мы учили лет 20 назад ОА и СД (оснонвы алгоритмов и структур данных).

Ваш список - чудовищно длинный. Если по нему расписать все - то примерно хватит на 5 лет учебы.
Я сомневаюсь что вы будете планировать с таким горизонотом. Я предложу выкинуть следующее.

- Алгебра
- Геометрия

И я объясню почему. Когда вы идете в ВУЗ - вы уже знаете алгебру и геометрию. Это курс школьной
программы и я не вижу смысла его подмешивать к компьютерным науками. Если вы по каким-то причинам
алгебру не знаете. То я вообще не вижу смысла вам дальше двигаться. Вы не будете понимать доказательтв
и выводов формул в других науках поэтому выкидываем.

Далее выкидываем.

- Теория игр
- Динамика
- Расписания

Теория игр - это факультатив. Почитаете книжки на досуге. Не включают обычно в базовые программы.
Не знаю зачем выделять отдельно расписания? Это может быть просто подраздел какой-то другой
оптимизации. Динамика ... хм... Что за динамика? Упругого тела? Непонятно. Разверните опредление.

- Строки

Выкидываем строки. Это первое занятие по Turbo Pascal. За 15 минут вы узнаете что такое строки.
Никаких особых знаний там нет. Алгоритм КМП и Боуер Мур - пойдет в ОЯ и СД.

Графы - я не буду выкидывать. Но они идут как подраздел дискретной математики.
Теория множеств. Дискретка. Графы. Это обычно один предмет.

Далее.

- Алгоритмы на последовательностях

Я не знаю что это такое. Приведите пример. Возможно это имеет другие названия? Автоматы? Сети? Цепи?

- Комбинаторика

Тоже идет как подраздел дискретной математики.

Итого в сухом остатке у нас остается 4 предмета.

- ОЯ и СД из программы любого ВУЗа
- Дискретная математика из ВУЗа
- Линейная алгебра
- Численные методы (да это реально настоящий предмет ВУЗа и притом достаточно плотный). Семестр как минимум.

Структуры данных - поглощаются ОЯ и СД. Вот. Остается Линейная Алгебра. Я ее не знаю куда положить.
Я не изучал ее отдельно как предмет. Возможно это и где-то выделяется в науку. Говоря о последовательности
изучения этих 4 предметов - я могу просто сослаться на методички ВУЗов. Ищите их. Ищите учебные планы.
Некоторые из этих наук я думаю можно учить параллельно.

Поскольку топик тегирован алгоритмами - то мы должны обсуждать именно алгоритмы.

Алгоритм называется DFS (Deep First Search). Это поиск в дереве в глубину.
Поиск выдает нам листовые вершины. И путь от корня до листовой вершины будет
кандидатом на ответ.

Значит наша задача - перебрать всех кандидатов на предмет совпадения с шаблоном.

"C:\***\\AppData\***\Adobe"

Здесь можно рассмотреть разные оптимизации. Например узел 1 и 3 и 5 уровней у нас - константа.
Это можно было бы рассматривать но мне без конкретного языка программирования это уже
неудобно и не интересно. Поэтому было-бы хорошо чтобы автор указал язык разработки.

Я сразу попробую ответить на главный вопрос.

написать хэш-таблицу без коллизий

Написать такую таблицу можно если мы заранее знаем весь набор данных (в случае автора это
множество ключей (K). Здесь для простоты предполагаем что ключи - это целые числа int32 (DWORD).

Алгоритм примерно такой:
1) Берем размер хеш-таблицы в n = size(K). Метод открытой адресации.
2) Берем любую хеш-функцию (по области определения больше чем n
SHA1, MD5, xxhash, mur-mur-hash)
3) Начинаем наполнять таблицу.
4) Как только детектирована коллизия - удаляем старую таблицу и создаем новую
с размером например 120% от исходного n.
5) Повторяем алгортм до тех пор пока не будут расставлены все ключи.

Profit.

Если мы не знаем наши данные изначально (у нас их нет и мы не знаем количество и тип данных)
то мы не можем гарантировать отсустствие коллизий хотя-бы потому что у нас
нету такой хеш функции которая бы гарантировала отсутствие коллизий на вариативном
типе данных.

Изучать хеширование на базе целых чисел - вобщем-то не интересно. Более общий случай - это
строки (String) и я-бы делал эксперименты со строками и с реальными данными (мобильные
телефоны емейлы налоговые номера и прочее). Целые числа - это .... слишком синтетические
тесты и их результаты потом никуда натянуть нельзя.

UPD: Алгоритм в таком виде не работает. По крайней мере от коллизий мы не избавились.
Не голосуйте здесь пока.

Дружище тебе не надо портить дерево. Оно и так хорошо.
Просто заведи отдельную хеш-таблицу и трекай две структуры
одновременно.

LRU например так и делает. Цепной список + Hashtable.

Парадокс Зенона?