Минимальный уровень знаний для программиста

Без знания/опыта работы с этими понятиями почти не реально программировать

Базовые вопросы

• Алгоритм
  • набор инструкций, описывающих порядок действий исполнителя для решения некоторой задачи
  • формализации:
    • рекурсивные функции Геделя — Эрбрана — Клини 1930
    • λ-исчисление Алонзо Чёрча (1936)
    • машина Тьюринга (1936)
• Отличие данных от алгоритмов
  • алгоритмы работают над данными преобразуя их полезное данные или действие
  • данными могут являться алгоритмы - см компиляторы
• Представление чисел, байт, 2-ная система счисления
• Байтовое представление строк
  • есть различные системы представления строковых данных - например в языке C строки - последовательность байт заканчивающихся нулем, в других языках могут быть отличные способы представления - например массив байтов - где первые 2/4 байта определяют длину строки
• Понятие переменная
• Пример последовательности вычислений
• Условное исполнение
• Циклическое исполнение
• Функция
• Рекурсия
• Быть способным написать Сортировка за O(n^2)
• Быть способным написать Сортировка O(log n)
• Hash функция

Структуры данных

• Массив фиксированной длины
• Список переменной длины
• Список на основе массива
• Связанный список
• Двусвязанный список
• Поиск перебором
• Бинарный поиск
• Карта (Map) с ключем по хэшу
• Карта с бинарным деревом (BTree)
• Стек
• Очередь
• Дерево
• Граф

Начальный уровень

ООП

• Класс
• Интерфейс
• Уровни доступа
• Единичное наследование, Множественное наследование
• Инкапсуляция
• Полиморфизм
• Типаж (trait)
• Параметризованные типы данных
• Ко/Контр/Инвариантность

Функциональность

• Детерминированность
• Отсуствие побочных явлений
• Чистая функция
• Не изменяемые объекты
• Лямбда/Стрелочные функции
• Ленивые вычисления
• Итераторы

Средний уровень

Многопоточное программирование

• Отличие процесса от потока
• Запуск потока
• Синхронизации потоков
  • Блокировки
  • Симафоры
  • Файловые блокировки
  • Распределенные блокировки
• Типичные сценарии ошибок
  • Гонка
  • Фантомное чтение/запись
  • Прерывание потока

Логическая - Математическая теория

Логика

• булева алгебра
• законы
  • Закон тождества A = A
  • Закон непротиворечия
  • Закон достаточного основания
  • Закон исключённого третьего
• Классическая логика
  • субъект, предикат, связка
  • количество (кванторы)
  • качество (утвердительные/отрицательные)
  • родовые общие суждения
  • Категорический силлогизм
    • аксиомы
      • Средний термин должен быть распределен, по крайней мере, в одной из посылок
      • Термин, нераспределенный в посылке, не может быть распределенным в заключе- нии
      • Из двух отрицательных посылок нельзя сделать никакого заключения.
      • Если одна посылка является отрицательной, заключение должно быть отрицатель- ным
      • Если ни одна посылка не является отрицательной, заключение должно быть утвер- дительным
• Аксиоматика / Формальная система
  • Задано конечное или счётное множество произвольных символов. Конечные последовательности символов называются выражениями теории
  • Имеется подмножество выражений, называемых формулами.
  • Выделено подмножество формул, называемых аксиомами.
  • Имеется конечное множество отношений между формулами, называемых правилами вывода.
  • Искомые свойства:
    • Непротиворечивость
    • Полнота
    • Независимость аксиом
    • Разрешимость
• Логика высказываний
  • ! Знак отрицания
  • ^ или & Знак конъюнкции («И»)
  • v Знак дизъюнкции («включающее ИЛИ»)
  • ⩒ или ⨁ Знак строгой дизъюнкции («исключающее ИЛИ»)
  • ⟶ Знак импликации
  • ∼ или ≡ или ↔ Знак эквивалентности
• Логика предикатов / Логика первого порядка формальное исчисление, Расширяет логику высказываний
  • символы переменных
  • логические операции
  • кванторы
    • ∀ Квантор всеобщности
    • ∃ Квантор существования

Общее из математики

• Понятие Идемпотентность

Теория множеств

• Понятие множества
• Подмножество и надмножество
• Пустое множество / универсум
• Конечное / Бесконечное множество
• Счетное множество
• Операции над множествами
  • объединение, разность, дополнение, пересечение, симметрическая разность
  • Декартово произведение
  • Мощность множества

Теория алгоритмов

• Алгоритм / Конечные автоматы
• Понятие сложности алгоритма, нотация O(n)
• Конечный автомат
  • Детерминированный/Стохастический КА
• Машина Тьюринга
• Лямбда исчисления
• Цепи Маркова

Дискретная математика

Мат статистика

Мета программирование

• Аспектно ориентированное программирование
• Предметно ориентированное программирование
  • DSL
  • Написание интерпретатора / компилятора
• Генетическое программирование