Алгоритмы и языки программирования

Алгоритмы

Алгоритмы

Название курса	Источник / Организация	Источник	Длина курса
Алгоритмы: теория и практика. Методы Введение Простые алгоритмы(числа Фибоначчи, НОД) , О-символика Реализация простых алгоритмов на C++, Python и Java Жадные алгоритмы Коды Хаффмана, очереди с приоритетом и непрерывный рюкзак Реализация жадных алгоритмов на C++, Python и Java Разделяй и властвуй Принцип ""Разделяй и властвуй"": бинпоиск, умножение, сортировки Реализация алгоритмов ""разделяй и властвуй"" на C++, Python и Java Динамическое программирование Наибольшая возрастающая подпоследовательность, расстояние редактирования, рюкзак Перемножение последовательности матриц Независимые множества во взвешенных деревьях Реализация алгоритма ""расстояние редактирования"" на C++, Python и Java	Stepik / CSC	Любой	14 часов видео
Алгоритмы: теория и практика. Структуры данных Базовые структуры данных Базовые структуры данных Очереди с приоритетом и системы непересекающихся множеств Очереди с приоритетом Системы непересекающихся множеств Хеш-таблицы Хеш-таблицы Деревья поиска АВЛ-деревья Дополнительные операции Сплей-деревья	Stepik / CSC	Любой	6 часов видео, 20 задач
Математическая логика и теория алгоритмов Математическая логика Начало математической логики, софизмы и парадоксы Основы теории множеств Интуитивная теория множеств, jперации над множествами Отношения, эквивалентность и порядок Функции (отображения) Пропозициональная логика Высказывания и высказывательные формы Пропозициональные логические связки Тавтологии, Равносильности Языки первого порядка Предикаты, кванторы, термы и формулы Формулы общезначимые, выполнимые, логически эквивалентные Перевод с естественного языка на логический и обратно Аксиоматический метод Аксиоматическое построение математических теорий Формальные аксиоматические теории Исчисление высказываний Теории первого порядка Математическое доказательство Математическая индукция Различные виды доказательств в математике Компьютерные доказательства Теория алгоритмов Неформальная вычислимость и машины Тьюринга Частично-рекурсивные функции Тезис Черча Некоторые алгоритмически неразрешимые проблемы Асимптотические обозначения Алгоритмы и их сложность Сложность задач	Stepik / ТУСУР	Любой	8 часов видео, 250 тестов
Введение в теоретическую информатику Разрешающие деревья Схемы из функциональных элементов Пропозициональная логика Вычислимость Программы и универсальные функции Машины Тьюринга Ассоциативные исчисления Переборные задачи и их сложность, ускорение перебора Конечные автоматы Контекстно-свободные языки Игры, стратегии, теорема Цермело Код с исправлением ошибок, код Хемминга Коммуникационная сложность Криптография, код Диффи–Хеллмана, RSA Интерактивные доказательства Правила Хоара	Stepik / CSC	Старшая школа и студенты	14 часов видео
Теоретическая информатика: сложность вычислений Разрешающие деревья Отгадывание числа: верхние и нижние оценки Отгадывание с ошибками Поиск максимума Сортировка: примеры, верхние и нижние оценки для n Ещё несколько задач Схемы из функциональных элементов Связки, функциональные элементы, ДНФ и КНФ, полнота Оценки сложности. Сумма, сравнение Оценки сложности произвольных функций Пропозиционная логика Формулы. Следование. Тавтологии. Выполнимость Следование и выводимость Исчисление резолюции? и его полнота Ещё о принципе Дирихле (приглашённый лектор --- Всеволод Опарин) Логика линейного программирования Переборные задачи и их сложность Переборные задачи Полиномиальные задачи Неразрешимые задачи Сравнение сложности: сведение Переборные задачи вокруг нас NP-полные задачи Задача 3-CNF NP-полна Задача о независимом множестве NP-полна Задача о 3-раскраске NP-полна Задачи поиска сводятся к задачам проверки Класс PSPACE Определение класса Игры, стратегии, кванторы Выигрышные и проигрышные позиции. Доказательство теоремы Цермело PSPACE и игры Ускорение перебора Чего мы хотим Задача о раскраске графа Задачи 2-SAT и 3-SAT	Stepik / CSC	Старшая школа и студенты	13 часов видео, 100 тестов