• 7 выводов программиста самоучки за 1 год
    +12
    > Проведём маленький эксперимент, если Вы не против — мне любопытно чего такого я не знаю на фундаментальном уровне, из того, что преподают в ВУЗах в качестве базы.

    Ну я вот писал программу по нескольким курсам, один из основных — «Алгоритмы и структуры данных», вот база (не все, особенно и последнего семестра, нужно знать и доказывать, но основные свойства полезно знать).

    Вот примерный список, я надеюсь, он после обкатки скорректируется. Общий объем 225 часов (чисто лекции, практика Python-C-C++ идет отдельными часами).

    Поиск в массиве
    1.1 Линейный поиск
    1.2 Двоичный поиск
    1.3 Троичный поиск
    1.4 Интерполяционный поиск
    Структуры данных
    1.5 Массив
    1.6 Стек
    1.7 Очередь, двусторонняя очередь
    1.8 Словарь
    1.9 Хеш-таблица

    Сортировки, анализ алгоритмов
    2.1 Bubble sort (пузырьковая сортировка)
    2.2 Merge sort (сортировка слиянием)
    2.3 Quick sort (быстрая сортировка)
    2.4 Bucket sort (блочная сортировка)
    2.5 Heap sort (пирамидальная сортировка)
    2.6 Insertion sort (сортировка вставками)
    2.7 Counting sort (сортировка подсчетом)
    2.8 Radix sort (порязрядная сортировка)
    2.9 Timsort и другие гибридные алгоритмы сортировки

    Рекурсия, математическая индукция
    3.1 Хвостовая рекурсия
    3.2 Обратная польская запись
    3.3 Числа Каталана
    3.4 Вычисление биномиальных коэффициентов
    3.5 Метод градиентного спуска
    3.6 Метод сопряженных градиентов
    3.7 Принцип динамического программирования
    3.8 Метод ветвей и границ
    3.9 Методы Gradient boosting
    3.10 Алгоритм Кадана
    3.11 Поиск методом золотого сечения
    3.12 Производящие функции
    3.13 Запаздывающие генераторы Фибоначчи
    3.14 Memoization
    3.15 Корекурсия
    3.16 Задача 3-SAT
    3.17 Алгоритм фрактального сжатия
    Структуры данных (рекурсивные)
    3.18 Список
    3.19 Дерево
    3.20 Граф

    Строки
    4.1 Z-функция
    4.2 Алгоритм Кнута-Морриса-Пратта
    4.3 Алгоритм Ахо-Корасик
    4.4 Алгоритм Бойера-Мура
    4.5 Алгоритм Бойера-Мура-Хорспула
    4.6 Сходство Джаро-Винклера
    4.7 Расстояние Левенштейна, алгоритм Укконена
    4.8 Расстояние Дамерау-Левенштейна
    4.9 Алгоритм Карпа-Миллера-Розенберга
    4.10 Алгоритм Каркайнена-Сандерса
    4.11 Алгоритм Арикавы-Аримуты-Касаи-Ли-Парка
    4.12 Алгоритм Ву-Менбера
    4.13 Алгоритм Ландау-Вишкена
    4.14 Алгоритм Майерса
    Структуры
    4.15 Префиксное дерево
    4.16 Суффиксный массив
    4.17 Суффиксное дерево

    Порядковые статистики, потоковые алгоритмы
    5.1 Алгоритм BFPRT
    5.2 Алгоритм Манро-Патерсона
    5.3 Алгоритм Канна-Гринвальда
    5.4 Алгоритм большинства голосов Бойера-Мура
    5.5 Алгоритм Lossy Count

    Деревья
    6.1 Эйлеров обход дерева, DFS, BFS
    6.2 Двоичное дерево поиска
    6.3 Декартово дерево
    6.4 Красно-черное дерево
    6.5 АВЛ-дерево, дерево Фибоначчи
    6.6 Splay tree (расширяющееся дерево)
    6.7 B, B+, B* дерево, 2-3 дерево
    6.8 PQ-дерево
    6.9 Дерево отрезков
    6.10 Дерево Фенвика
    6.11 Алгоритм двоичного подъема (задача LCA)
    6.12 Алгоритм Фарах-Колтона и Бендера (RMQ, LCA)
    6.13 Sqrt-декомпозиция
    6.14 Центроидная декомпозиция
    6.15 Heavy-light декомпозиция
    6.16 Фибоначчиева куча
    6.17 Куча, 2-3 куча
    6.18 Очередь с приоритетами
    6.19 Множество
    6.20 Система непересекающихся множеств
    6.21 Лес непересекающихся множеств
    6.20 Ассоциативный массив

    Графы
    7.1 Обход в ширину (BFS)
    7.2 Обход в глубину (DFS)
    7.3 Топологическая сортировка
    7.4 Алгоритм Munagala-Ranade
    7.5 Алгоритм Mehlhorn-Meyer
    7.6 Задача о динамической связности
    7.7 Алгоритм поиска точек сочленения графа
    7.8 Алгоритм поиска мостов графа
    7.9 Алгоритм Косараю
    7.10 Алгоритм Тарьяна
    7.11 Задача 2-SAT
    7.11 Алгоритм Брона-Кербоша
    7.12 Конденсация графа
    7.13 Раскраска графа
    7.14 Задача о назначениях
    7.15 Венгерский алгоритм
    7.16 Алгоритм Ульмана
    Структуры
    7.17 Матрица смежности
    7.18 Матрица достижимости
    7.19 Матрица сильной связности
    7.20 Матрица Лапласа
    7.21 Матрица Инцидентности
    7.22 Список смежности
    7.23 Список ребер

    Графы: циклы
    8.1 Алгоритм поиска Эйлерова цикла
    8.2 Алгоритм поиска Эйлерова пути
    8.3 Алгоритм поиска Гамильтонова цикла
    8.3 Алгоритм поиска Гамильтонова пути
    8.4 Задача Коммивояжера

    Графы: остовное дерево
    9.1 Теорема Кирхгофа
    9.2 Теорема Кэли о числе деревьев, код Прюфера
    9.3 Лемма о безопасном (минимальном) ребре
    9.4 Алгоритм Краскала
    9.5 Алгоритм Примы
    9.6 Алгоритм Борувки
    9.7 Задача устранения петель в сети Ethernet (STP)
    9.8 Задача Штейнера

    Графы: кратчайший путь
    10.1 Алгоритм Дейкстры
    10.2 Алгоритм Best-First
    10.3 Алгоритм A*
    10.4 Алгоритм Левита
    10.5 Алгоритм Беллмана-Форда
    10.6 Алгоритм Флойда-Уоршелла
    10.7 Алгоритм ALT
    10.8 Алгоритм Reach-based pruning

    Графы: потоки в сетях
    11.1 Алгоритм Форда-Фалкерсона
    11.2 Алгоритм Эдмонса-Карпа (алгоритм Диница)
    11.3 Алгоритм поиска потока минимальной стоимости
    11.4 Сети Петри
    11.5 Алгоритм проверки графа на двудольность
    11.6 Алгоритм раскраски двудольного графа
    11.7 Алгоритм Хопкрофта-Карпа
    11.8 Венгерский алгоритм
    11.9 Blossom алгоритм (алгоритм Эдмондса)
    11.10 Алгоритм Штор-Вагнера

    Геометрия
    12.1 Метод Гаусса
    12.2 Поиск точек в прямоугольнике
    12.3 Алгоритм Бентли-Оттмана
    12.4 Алгоритм Грэхема
    12.5 Алгоритм Джарвиса
    12.6 Алгоритм Чана
    12.7 Алгоритм Киркпатрика
    12.8 Метод трассировки луча
    12.9 Метод суммирования углов
    12.10 Диаграмма Вороного и триангуляция Делоне
    12.11 Алгоритм Форчуна
    12.12 Рекурсивное построение диаграммы Вороного
    12.13 SLERP
    Структуры
    12.13 R, R+, R* дерево
    12.14 K-мерное дерево
    12.15 BSP, VP дерево
    12.16 Дерево покрытий

    Персистентные структуры
    13.1 Метод копирования пути
    13.2 Метод толстых узлов
    Структуры
    13.3 Персистентный стек
    13.4 Персистентная очередь
    13.5 Персистентное дерево

    Консенсус в сетях
    14.1 Алгоритм Paxos
    14.2 Задача Византийских генералов
    14.3 Кворум
    14.4 CAP-теорема
    14.5 PACELC-теорема
    14.6 Королевский алгоритм
    14.7 Алгоритм Zyzzyva
    Структуры
    14.8 Blockchain

    Целочисленное программирование
    15.1 Каноническая форма, сложность решения
    15.2 Алгоритмы полного перебора
    15.3 Алгоритм Нарайаны
    15.4 Задача о ранце
    15.5 Алгоритм Meet-in-the-Middle
    15.6 Задача раскроя
    15.7 Метод обратного поиска
    15.8 Задача планирования производства
    15.9 Задача оптимизации телекоммуникационных сетей
    15.10 Метод секущих плоскостей, алгоритм Гомори
    15.11 Алгоритм Альфа-Бета отсечений
    15.12 Жадные алгоритмы
    15.13 Матроиды, алгоритм Радо-Эдмонса

    Быстрые вычисления
    16.1 Умножение Карацубы
    16.2 Алгоритм Шенхаге-Штрассена
    16.3 Алгоритмы возведения числа в степень
    16.4 Алгоритмы возведения в степень числа по модулю
    16.5 Алгоритм Кули-Тьюки
    16.6 Алгоритм Штрассена

    Факторизация
    17.1 Алгоритм Евклида (НОД)
    17.2 Алгоритм факторизации Ферма
    17.3 Метод квадратичных форм Шенкса
    17.4 Ро-алгоритм Полларда
    17.5 Метод квадратичного решета
    17.6 Общий метод решета числового поля
    17.7 Факторизация с помощью эллиптических кривых
    17.8 Тест Агравала-Каяла-Саксены
    17.9 Алгоритм Берлекэмпа

    Дискретное логарифмирование
    18.1 Алгоритм Гельфонда-Шенкса
    18.2 Алгоритм COS

    Обработка очередей
    18.1 Семейство алгоритмов Round-robin
    18.2 Алгоритм EDF
    18.3 Алгоритм SRTF
    18.4 Алгоритм Fixed-priority pre-emptive scheduling
    18.5 Задача составления расписания (JSP, OSSP)
    18.6 CFS планировщик
    18.7 BFS планировщик

    Кеширование
    19.1 T-дерево
    19.2 Алгоритм Белади
    19.3 FIFO, LIFO кеширование
    19.4 LRU, PLRU кеширование
    19.5 MRU кеширование
    19.6 RR кеширование
    19.7 LFU кеширование
    19.8 MQ кеширование
    19.9 ARC кеширование

    Рандомизированные алгоритмы
    20.1 Метод Монте-Карло
    20.2 Поиск наименьшего набора ребер, разрезающего циклы
    20.3 Муравьиный алгоритм
    20.4 Алгоритм Каргера
    20.5 Изоморфизм графов (алгоритм Blum-Kanan)
    20.6 Rapidly exploring random tree
    20.7 Тасование Фишера-Йетса
    20.8 Алгоритм Karloff–Zwick

    Вероятностные тесты на простоту
    21.1 Тест Ферма
    21.2 Тест Миллера-Рабина
    21.1 Тест Бейли-Померанца-Селфриджа-Уогстаффа

    Вебграфы
    22.1 Модель Болобаша-Альберта
    22.2 Модель Болобаша-Риордана
    22.3 Модель Бакли-Остгус
    22.4 Модель копирования
    22.5 PageRank, Google matrix
    Структуры
    22.1 MapReduce
    22.2 Apache GiGraph
    22.3 Pregel

    Хеширование
    23.1 Двойное хеширование
    23.2 Фильтр Блума
    23.3 Count-min sketch
    23.4 Универсальное хеширование
    23.5 SWIFFT
    23.6 MD5
    23.7 SHA-2
    23.8 SHA-3 (Keccak)
    23.9 Дерево Меркла
    23.10 Подпись Меркла
    23.11 Хеш-функции, учитывающие близость (LSH)
    23.12 Хеширование на основе расстояния Хэмминга
    23.13 MinHash
    23.14 SimHash
    23.15 Поиск ближайшего соседа c помощью LSH

    ** При этом стоит учесть что запланированы еще курсы по Теории графов, Дискретной математике, Экстремальным задачам, Машинному обучению, Теории сложности и пр.пр.пр. Т.е. это просто фундаментальный курс по алгоритмам и структурам данных, который является точкой отсчета для всего остального (ну как курс по Математическому анализу).

    *** Это несколько больше чем я сам знаю, так что это еще и мой план для себя подтянуть неизвестные/забытые темы. Обсудив его с коллегами, на предмет кто будет читать мы пришли к выводу, что мы все были бы рады и сейчас прослушать такой курс.
  • Неотзывчивый дизайн
    0
    Совсем недавно разделил бы это мнение.

    Пока мне не попались в руки книги:
    — «Дизайн для недизайнеров», Робин Вильямс
    — «Как сделать красиво на бумаге», Роджер Паркер

    … они мое (программерское) видение на графический дизайн изменили.

    Обе книги опубликованы на русском.