556
правок
Изменения
Перейти к навигации
Перейти к поиску
Алгоритмы и языки программирования (просмотреть исходный код)
Версия 23:11, 23 марта 2020
, 23:11, 23 марта 2020→Алгоритмы
==Алгоритмы==
<!-- ****************************** -->
<!-- Table Format - do not touch -->
{| class="a" style="width:100%;" border="1" style="width:100%; border-collapse:collapse"|+
<!-- Table name -->
'''Алгоритмы'''
<!-- Table headers - do not touch -->
! style="background: #EAECF0;"| Название курса||style="background: #EAECF0;"|Источник / Организация||style="background: #EAECF0;"|Источник||style="background: #EAECF0;"|Длина курса
<!-- ****************************** -->
<!-- Course 1 -->
|-
|
<!-- Course format do not touch -->
{| role="presentation" class="a mw-collapsible mw-collapsed" style="border:1px solid white;"
| style="border:1px solid white;"|<strong>[https://stepik.org/course/217/promo Алгоритмы: теория и практика. Методы]</strong>
|-
<!-- Course content format do not touch -->
| style="border:1px solid white;"|
<!-- Course content -->
'''Введение'''
* Простые алгоритмы(числа Фибоначчи, НОД) , О-символика
* Реализация простых алгоритмов на C++, Python и Java
'''Жадные алгоритмы'''
* Коды Хаффмана, очереди с приоритетом и непрерывный рюкзак
* Реализация жадных алгоритмов на C++, Python и Java
'''Разделяй и властвуй'''
* Принцип ""Разделяй и властвуй"": бинпоиск, умножение, сортировки
* Реализация алгоритмов ""разделяй и властвуй"" на C++, Python и Java
'''Динамическое программирование'''
* Наибольшая возрастающая подпоследовательность, расстояние редактирования, рюкзак
* Перемножение последовательности матриц
* Независимые множества во взвешенных деревьях
* Реализация алгоритма ""расстояние редактирования"" на C++, Python и Java
|}
<!-- Formating do not touch -->
|style="text-align:center;"|
[[Stepik]] / [[CSC]]
|style="text-align:center;"|
[[Материалы для любого возраста|Любой]]
|style="text-align:center;"|
14 часов видео
<!-- ****************************** -->
<!-- Course 2 -->
|-
|
<!-- Course format do not touch -->
{| role="presentation" class="a mw-collapsible mw-collapsed" style="border:1px solid white;"
| style="border:1px solid white;"|<strong>[https://stepik.org/course/1547/promo Алгоритмы: теория и практика. Структуры данных]</strong>
|-
<!-- Course content format do not touch -->
| style="border:1px solid white;"|
<!-- Course content -->
'''Базовые структуры данных'''
* Базовые структуры данных
'''Очереди с приоритетом и системы непересекающихся множеств'''
* Очереди с приоритетом
* Системы непересекающихся множеств
'''Хеш-таблицы'''
* Хеш-таблицы
'''Деревья поиска'''
* АВЛ-деревья
* Дополнительные операции
* Сплей-деревья
|}
<!-- Formating do not touch -->
|style="text-align:center;"|
[[Stepik]] / [[CSC]]
|style="text-align:center;"|
[[Материалы для любого возраста|Любой]]
|style="text-align:center;"|
6 часов видео, 20 задач
<!-- ****************************** -->
<!-- Course 3 -->
|-
|
<!-- Course format do not touch -->
{| role="presentation" class="a mw-collapsible mw-collapsed" style="border:1px solid white;"
| style="border:1px solid white;"|<strong>[https://stepik.org/course/48679/promo Математическая логика и теория алгоритмов]</strong>
|-
<!-- Course content format do not touch -->
| style="border:1px solid white;"|
<!-- Course content -->
'''Математическая логика'''
* Начало математической логики, софизмы и парадоксы
'''Основы теории множеств'''
* Интуитивная теория множеств, jперации над множествами
* Отношения, эквивалентность и порядок
* Функции (отображения)
'''Пропозициональная логика'''
* Высказывания и высказывательные формы
* Пропозициональные логические связки
* Тавтологии, Равносильности
'''Языки первого порядка'''
* Предикаты, кванторы, термы и формулы
* Формулы общезначимые, выполнимые, логически эквивалентные
* Перевод с естественного языка на логический и обратно
'''Аксиоматический метод'''
* Аксиоматическое построение математических теорий
* Формальные аксиоматические теории
* Исчисление высказываний
* Теории первого порядка
'''Математическое доказательство'''
* Математическая индукция
* Различные виды доказательств в математике
* Компьютерные доказательства
'''Теория алгоритмов'''
* Неформальная вычислимость и машины Тьюринга
* Частично-рекурсивные функции
* Тезис Черча
* Некоторые алгоритмически неразрешимые проблемы
* Асимптотические обозначения
* Алгоритмы и их сложность
* Сложность задач
|}
<!-- Formating do not touch -->
|style="text-align:center;"|
[[Stepik]] / [[ТУСУР]]
|style="text-align:center;"|
[[Материалы для любого возраста|Любой]]
|style="text-align:center;"|
8 часов видео, 250 тестов
<!-- ****************************** -->
<!-- Course 4 -->
|-
|
<!-- Course format do not touch -->
{| role="presentation" class="a mw-collapsible mw-collapsed" style="border:1px solid white;"
| style="border:1px solid white;"|<strong>[https://stepik.org/course/104/promo Введение в теоретическую информатику]</strong>
|-
<!-- Course content format do not touch -->
| style="border:1px solid white;"|
<!-- Course content -->
* Разрешающие деревья
* Схемы из функциональных элементов
* Пропозициональная логика
* Вычислимость
* Программы и универсальные функции
* Машины Тьюринга
* Ассоциативные исчисления
* Переборные задачи и их сложность, ускорение перебора
* Конечные автоматы
* Контекстно-свободные языки
* Игры, стратегии, теорема Цермело
* Код с исправлением ошибок, код Хемминга
* Коммуникационная сложность
* Криптография, код Диффи–Хеллмана, RSA
* Интерактивные доказательства
* Правила Хоара
|}
<!-- Formating do not touch -->
|style="text-align:center;"|
[[Stepik]] / [[CSC]]
|style="text-align:center;"|
[[Материалы для старшей школы и студентов| Старшая школа и студенты]]
|style="text-align:center;"|
14 часов видео
<!-- ****************************** -->
<!-- Course 5 -->
|-
|
<!-- Course format do not touch -->
{| role="presentation" class="a mw-collapsible mw-collapsed" style="border:1px solid white;"
| style="border:1px solid white;"|<strong>[https://stepik.org/course/1613/promo Теоретическая информатика: сложность вычислений]</strong>
|-
<!-- Course content format do not touch -->
| style="border:1px solid white;"|
<!-- Course content -->
'''Разрешающие деревья'''
* Отгадывание числа: верхние и нижние оценки
* Отгадывание с ошибками
* Поиск максимума
* Сортировка: примеры, верхние и нижние оценки для n
* Ещё несколько задач
'''Схемы из функциональных элементов'''
* Связки, функциональные элементы, ДНФ и КНФ, полнота
* Оценки сложности. Сумма, сравнение
* Оценки сложности произвольных функций
'''Пропозиционная логика'''
* Формулы. Следование. Тавтологии. Выполнимость
* Следование и выводимость
* Исчисление резолюции? и его полнота
* Ещё о принципе Дирихле (приглашённый лектор --- Всеволод Опарин)
* Логика линейного программирования
'''Переборные задачи и их сложность'''
* Переборные задачи
* Полиномиальные задачи
* Неразрешимые задачи
* Сравнение сложности: сведение
* Переборные задачи вокруг нас
* NP-полные задачи
* Задача 3-CNF NP-полна
* Задача о независимом множестве NP-полна
* Задача о 3-раскраске NP-полна
* Задачи поиска сводятся к задачам проверки
'''Класс PSPACE'''
* Определение класса
* Игры, стратегии, кванторы
* Выигрышные и проигрышные позиции. Доказательство теоремы Цермело
* PSPACE и игры
'''Ускорение перебора'''
* Чего мы хотим
* Задача о раскраске графа
* Задачи 2-SAT и 3-SAT
|}
<!-- Formating do not touch -->
|style="text-align:center;"|
[[Stepik]] / [[CSC]]
|style="text-align:center;"|
[[Материалы для старшей школы и студентов| Старшая школа и студенты]]
|style="text-align:center;"|
13 часов видео, 100 тестов
<!-- ****************************** -->
<!-- Table ending - do not touch -->
|}
<!-- ****************************** -->
==Python==
