О разделе
Раздел не входит в базовый маршрут "данные и SQL для новичка". Читайте выборочно, если интересны когнитивистика, дискретная математика или формальные автоматы — или когда упрётесь в теорию на курсах/олимпиадах. Краткий обзор по графам — раздел 22 «Базовой информатики» (этап 28).
Раздел объединяет как мы думаем (когнитивистика), какой математикой пользуется IT (логика, дискретка, вероятность, информация), формальные границы вычислений (ТАФЯ — автоматы, грамматики, Тьюринг) и смысл данных (семантика, представление знаний, онтологии). Материал можно читать выборочно; ниже — четыре типичных маршрута.
В ключевых статьях идеи сначала даются человеческим псевдокодом ("если … то", "для каждого", "множество A пересечь B"), затем — формулами и интерактивами. Так проще связать теорию с if, SQL и планированием задач.
Обзор таблиц и маршрутов: Математическая основа IT.
Карта дисциплин (старт): 341 — виды математических наук.
С нуля в ML: 341 → … → NumPy → Pandas → sklearn → Insurance → Diabetes → Titanic → перцептрон → Keras → spam.
Минимум для разработчика: 31 → 32 → 33.
Формальная дискретка (курс множества → таблицы → графы → логика): 31 → 314 (по желанию) → 321 → 322 → 32 → 323 → 324 → 33 → 325 (самопроверка).
Для аналитиков, архитекторов данных и тех, кто строит глоссарии, схемы и графы знаний. Желательно пройти логику и графы; реляционную алгебру — если идёте к БД.
Маршрут: 326 (семантика — хаб) → 327 (представление знаний) → 328 (онтология) → 329 (концептуальные схемы) → 330 (семантический веб, продвинуто). Термины маршрута — словарь 331.
Связанные разделы: метаданные, основы БД, NLP.
Когнитивистика - наука о мышлении
Когнитивистика для разработчиков — память, чанкинг, нагрузка при чтении кода и осознанное обучение новым технологиям.
Ментальные модели
История термина "ментальная модель" - Крейк о внутренних представлениях мира, которые строит когнитивная система.
Тектология
Единый процесс - согласованные по цели, времени и пространству действия участников ради одного результата.
Системы и модели
Что такое система и её элементы, как все это связано и зачем нужно.
Математическая основа IT
Краткое знакомство с науками, которые лежат в основе логики программ, данных и вычислений — от булевой алгебры до теории информации.
Логика
Булева и предикатная логика для разработки — операции, таблицы истинности, кванторы и законы де Моргана в условиях кода.
Алгебра логики — нормальные формы и схемы
Совершенные ДНФ и КНФ, минимизация, карты Карно и логические сети — от таблицы истинности до упрощения условий в коде.
Дискретная математика
Множества, отношения, графы и комбинаторика — язык описания структур данных, сетей, зависимостей и оценки сложности в IT.
Множества и отношения — формальный слой
Математическая индукция, мощность, биекции, матрицы и порядки — формальная база перед таблицами и графами в IT.
Реляционная алгебра и таблицы
Отношение как множество кортежей: объединение, пересечение, разность и произведение — мост к реляционной модели Кодда и SQL.
Графы — маршруты, остовы и раскраски
Представления графов, кратчайшие пути, остовы и разрезы, раскраска и планарность — формальная теория графов для сетей и алгоритмов.
Рекуррентные соотношения
Линейные рекуррентности, характеристическое уравнение и связь с рекурсией в коде — оценка сложности divide-and-conquer и роста последовательностей.
Дискретная математика — чек-лист самопроверки
Вопросы по множествам, логике, графам, рекуррентностям и таблицам с подсказками — после статей 31–324 формального маршрута.
Семантика — смысл знаков и данных
Синтаксис и семантика, три уровня слова "семантика" в IT, связь с метаданными и онтологиями.
Представление знаний
Фреймы, семантические сети, правила и логика — как записать знания о предметной области для программ.
Онтология в информатике
Формальное описание понятий предметной области — классы, свойства, отношения и таксономии.
Концептуальные схемы и информационные модели
От идеи на доске до таблиц SQL — ER, UML, три уровня схемы данных и связь с онтологией.
Теория чисел, псевдокод и анализ алгоритмов
Делимость и НОД, запись алгоритмов псевдокодом, худший случай и асимптотика O(n) — связь с криптографией и проектированием кода.
Семантический веб и графы знаний
RDF, триплеты, OWL, Linked Data, SPARQL и графы знаний — машиночитаемый смысл в сети и в ИИ.
Словарь терминов
Сводный словарь по семантике данных, представлению знаний, онтологиям, концептуальным схемам, семантическому вебу и основам теории алгоритмов.
Линейная алгебра
Обзор линейной алгебры для IT — векторы, матрицы, системы уравнений и связь с ML, графикой и оптимизацией.
Виды математических наук
Карта математических дисциплин — от арифметики и алгебры до линейной алгебры и теории вероятностей — с примерами из IT и ссылками на углубление.
Векторы
Математические векторы — представления, операции, длина, нормализация, скалярное и внешнее произведение; примеры и задачи для самопроверки.
Матрицы и операции
Матрицы — виды, индексация, сложение, умножение, транспонирование; пошаговые примеры и задачи для тренировки.
Вероятность и статистика
События, условная вероятность, независимость и закон больших чисел — язык неопределённости в мониторинге, ML и рисках.
Моделирование систем
Математические, имитационные и логические модели — от постановки задачи до валидации и рекомендаций для IT-инфраструктуры.
Численные методы
Приближённое решение уравнений, интерполяция и метод наименьших квадратов — когда точная формула недоступна или слишком дорога.
Формальные языки и автоматы
Иерархия Хомского, конечные и магазинные автоматы, машина Тьюринга и неразрешимость — обзор и маршрут по курсу ТАФЯ.
Теория информации
Энтропия Шеннона, избыточность, сжатие без потерь и пропускная способность канала — количественный взгляд на данные.
Мыслительная база — итоги
Итоги раздела «Мыслительная база» — FAQ и краткие ответы по теме.
Теория алгоритмов — формальные основы
Математическое понятие алгоритма, требования дискретности и массовости, алфавитные операторы и связь с машиной Тьюринга.
Рекурсивные и вычислимые функции
Примитивная и частичная рекурсия, базовые функции, связь с машиной Тьюринга и отличие от рекурсии в коде.
Машина Тьюринга
Формальное и неформальное определение, вычислимые функции, универсальная МТ, полулента и неразрешимые проблемы.
Формальные грамматики и разбор
Порождающие грамматики, иерархия Хомского, вывод и деревья, неоднозначность, преобразования КС-грамматик и связь с компилятором.
Конечные автоматы и регулярные языки
ДКА и НКА, регулярные операции, минимизация, автоматные грамматики, связь с regex и лексическим анализом.
Магазинные автоматы, Мили и Мура
МП-автоматы и КС-языки, преобразователи, автоматы Мили и Мура, эквивалентность и эксперимент по состояниям.
ТАФЯ — чек-лист самопроверки
Вопросы для закрепления курса теории автоматов и формальных языков с подсказками, маршрутом ответов и мини-разбором типичных ошибок.
Мыслительная база — чек-лист
Пятьдесят вопросов для самопроверки по когнитивной нагрузке, памяти, ментальным моделям и обучению в IT.
Мыслительная база — о разделе
Когнитивистика, математика для IT, теория автоматов и семантика данных — маршруты чтения раздела.