Алгоритмы и структуры данных III. Основной поток 2026 - История изменений

Spirina.es в 08:17, 30 октября 2026

2026-10-30T08:17:33Z

← Предыдущая версия		Версия от 08:17, 30 октября 2026
Строка 83:		Строка 83:

	Экзамен же рассчитан оценить уровень теоретической подготовки студента. На нём от студента ожидается знание доказательств изученных в течение курса алгоритмов, а также умение решать теоретические задачи. Обычно такие задачи более сложные, чем практические, что компенсируется отсутствием необходимости реализовывать их (имплементировать).		Экзамен же рассчитан оценить уровень теоретической подготовки студента. На нём от студента ожидается знание доказательств изученных в течение курса алгоритмов, а также умение решать теоретические задачи. Обычно такие задачи более сложные, чем практические, что компенсируется отсутствием необходимости реализовывать их (имплементировать).

			== Правила курса ==
			Подробнее о правилах курса [https://docs.google.com/document/d/1TNoAMWFGZHsEigH9BlM_lGI4jdHxxR66Y3jHGtntQME/edit здесь]

	== Материалы курса ==		== Материалы курса ==

Spirina.es: /* Критерии оценивания и формы контроля успеваемости */

2026-10-30T08:14:38Z

Критерии оценивания и формы контроля успеваемости

← Предыдущая версия		Версия от 08:14, 30 октября 2026
Строка 69:		Строка 69:
	За курс предусмотрены две оценки: за зачёт и за экзамен. Оценки независимы и никак не влияют друг на друга. Оценка за зачёт ставится за работу в семестре: за сдачу теоретических и практических домашних задач, а также за активность на семинарах и помощь в развитии курса (исправление опечаток в условиях, подготовка более сильных тестов к задачам, разработка собственных задач и пр.). Оценка за экзамен ставится исключительно исходя из качества устного ответа на экзамене.		За курс предусмотрены две оценки: за зачёт и за экзамен. Оценки независимы и никак не влияют друг на друга. Оценка за зачёт ставится за работу в семестре: за сдачу теоретических и практических домашних задач, а также за активность на семинарах и помощь в развитии курса (исправление опечаток в условиях, подготовка более сильных тестов к задачам, разработка собственных задач и пр.). Оценка за экзамен ставится исключительно исходя из качества устного ответа на экзамене.

	В течение семестра планируются 5 домашних заданий, разбитых по темам: 1) базовые строковые алгоритмы [7–28 сентября]; 2) суффиксные строковые структуры [28 сентября – 24 октября]; 3) алгоритмы в теории чисел [21 октября – 15 ноября]; 4) базовые алгоритмы в геометрии [1 ноября – 21 ноября]; 5) продвинутые алгоритмы в геометрии [28 ноября – 15 декабря]. В каждой теме планируется большой контест и небольшое теоретическое задание. Чтобы заработать минимальную положительную оценку (уд. 3), нужно набрать примерно 50% баллов от максимума. Чтобы заработать наивысшую оценку (отл. 10), нужно приблизиться к идеальному студенту, решившему почти все задачи. Ожидаемый максимальный балл — 120. Оценка за семестр стремится зафиксировать уровень навыков студента в решении и реализации практических задач по алгоритмам.		В течение семестра планируются 5 домашних заданий, разбитых по темам:
			# базовые строковые алгоритмы [7–28 сентября];
			# суффиксные строковые структуры [28 сентября – 24 октября];
			# алгоритмы в теории чисел [21 октября – 15 ноября];
			# базовые алгоритмы в геометрии [1 ноября – 21 ноября];
			# продвинутые алгоритмы в геометрии [28 ноября – 15 декабря].

			В каждой теме планируется большой контест и небольшое теоретическое задание. Чтобы заработать минимальную положительную оценку (уд. 3), нужно набрать примерно 50% баллов от максимума.

			Чтобы заработать наивысшую оценку (отл. 10), нужно приблизиться к идеальному студенту, решившему почти все задачи.

			Ожидаемый максимальный балл — 120. Оценка за семестр стремится зафиксировать уровень навыков студента в решении и реализации практических задач по алгоритмам.

	Экзамен же рассчитан оценить уровень теоретической подготовки студента. На нём от студента ожидается знание доказательств изученных в течение курса алгоритмов, а также умение решать теоретические задачи. Обычно такие задачи более сложные, чем практические, что компенсируется отсутствием необходимости реализовывать их (имплементировать).		Экзамен же рассчитан оценить уровень теоретической подготовки студента. На нём от студента ожидается знание доказательств изученных в течение курса алгоритмов, а также умение решать теоретические задачи. Обычно такие задачи более сложные, чем практические, что компенсируется отсутствием необходимости реализовывать их (имплементировать).

Spirina.es: /* Критерии оценивания и формы контроля успеваемости */

2026-10-30T08:13:08Z

Критерии оценивания и формы контроля успеваемости

← Предыдущая версия		Версия от 08:13, 30 октября 2026
Строка 67:		Строка 67:
	== Критерии оценивания и формы контроля успеваемости ==		== Критерии оценивания и формы контроля успеваемости ==

	~~В конце семестра~~ экзамен.		За курс предусмотрены две оценки: за зачёт и за экзамен. Оценки независимы и никак не влияют друг на друга. Оценка за зачёт ставится за работу в семестре: за сдачу теоретических и практических домашних задач, а также за активность на семинарах и помощь в развитии курса (исправление опечаток в условиях, подготовка более сильных тестов к задачам, разработка собственных задач и пр.). Оценка за экзамен ставится исключительно исходя из качества устного ответа на экзамене.

	В течение семестра планируются 5 домашних заданий, разбитых по темам: 1) базовые строковые алгоритмы [7–28 сентября]; 2) суффиксные строковые структуры [28 сентября – 24 октября]; 3) алгоритмы в теории чисел [21 октября – 15 ноября]; 4) базовые алгоритмы в геометрии [1 ноября – 21 ноября]; 5) продвинутые алгоритмы в геометрии [28 ноября – 15 декабря]. В каждой теме планируется большой контест и небольшое теоретическое задание. Чтобы заработать минимальную положительную оценку (уд. 3), нужно набрать примерно 50% баллов от максимума. Чтобы заработать наивысшую оценку (отл. 10), нужно приблизиться к идеальному студенту, решившему почти все задачи. Ожидаемый максимальный балл — 120. Оценка за семестр стремится зафиксировать уровень навыков студента в решении и реализации практических задач по алгоритмам.		В течение семестра планируются 5 домашних заданий, разбитых по темам: 1) базовые строковые алгоритмы [7–28 сентября]; 2) суффиксные строковые структуры [28 сентября – 24 октября]; 3) алгоритмы в теории чисел [21 октября – 15 ноября]; 4) базовые алгоритмы в геометрии [1 ноября – 21 ноября]; 5) продвинутые алгоритмы в геометрии [28 ноября – 15 декабря]. В каждой теме планируется большой контест и небольшое теоретическое задание. Чтобы заработать минимальную положительную оценку (уд. 3), нужно набрать примерно 50% баллов от максимума. Чтобы заработать наивысшую оценку (отл. 10), нужно приблизиться к идеальному студенту, решившему почти все задачи. Ожидаемый максимальный балл — 120. Оценка за семестр стремится зафиксировать уровень навыков студента в решении и реализации практических задач по алгоритмам.

Spirina.es: /* Критерии оценивания и формы контроля успеваемости */

2026-10-29T15:38:41Z

Критерии оценивания и формы контроля успеваемости

← Предыдущая версия		Версия от 15:38, 29 октября 2026
Строка 68:		Строка 68:

	В конце семестра экзамен.		В конце семестра экзамен.

			В течение семестра планируются 5 домашних заданий, разбитых по темам: 1) базовые строковые алгоритмы [7–28 сентября]; 2) суффиксные строковые структуры [28 сентября – 24 октября]; 3) алгоритмы в теории чисел [21 октября – 15 ноября]; 4) базовые алгоритмы в геометрии [1 ноября – 21 ноября]; 5) продвинутые алгоритмы в геометрии [28 ноября – 15 декабря]. В каждой теме планируется большой контест и небольшое теоретическое задание. Чтобы заработать минимальную положительную оценку (уд. 3), нужно набрать примерно 50% баллов от максимума. Чтобы заработать наивысшую оценку (отл. 10), нужно приблизиться к идеальному студенту, решившему почти все задачи. Ожидаемый максимальный балл — 120. Оценка за семестр стремится зафиксировать уровень навыков студента в решении и реализации практических задач по алгоритмам.

			Экзамен же рассчитан оценить уровень теоретической подготовки студента. На нём от студента ожидается знание доказательств изученных в течение курса алгоритмов, а также умение решать теоретические задачи. Обычно такие задачи более сложные, чем практические, что компенсируется отсутствием необходимости реализовывать их (имплементировать).

	== Материалы курса ==		== Материалы курса ==

Spirina.es: /* Материалы курса */

2026-10-29T15:36:25Z

Материалы курса

← Предыдущая версия		Версия от 15:36, 29 октября 2026
Строка 71:		Строка 71:
	== Материалы курса ==		== Материалы курса ==

			[https://www.youtube.com/playlist?list=PL4_hYwCyhAvYlrKIbN0Qgv9yjClbrIZyG лекции] потока осень 2024

	Примерная [https://drive.google.com/file/d/1EG31vtO4NSrRQgQgXwoHDv0YcSRM9R9m/view?usp=sharing программа] экзамена		Примерная [https://drive.google.com/file/d/1EG31vtO4NSrRQgQgXwoHDv0YcSRM9R9m/view?usp=sharing программа] экзамена

Spirina.es: /* Программа курса */

2026-10-29T15:35:20Z

Программа курса

← Предыдущая версия		Версия от 15:35, 29 октября 2026
Строка 22:		Строка 22:
	В семестре 15 лекций и 30 семинаров (практических занятий).		В семестре 15 лекций и 30 семинаров (практических занятий).

	'''Формы контроля:''' ~~Дифференцированный зачет и~~ экзамен		'''Формы контроля:''' экзамен

	{\|class="wikitable"		{\|class="wikitable"

Spirina.es: /* О курсе */

2026-10-29T15:35:09Z

О курсе

← Предыдущая версия		Версия от 15:35, 29 октября 2026
Строка 1:		Строка 1:
	== О курсе ==		== О курсе ==
	~~В семестре планируется 15 лекций и 30 семинаров (практических занятий).~~ На лекциях разбираются различные модельные задачи и алгоритмы их решения, на семинарах студентам предлагается решать теоретические задачи, обсуждать их решения, реализовывать код избранных алгоритмов, а также сдавать домашние задания.		На лекциях разбираются различные модельные задачи и алгоритмы их решения, на семинарах студентам предлагается решать теоретические задачи, обсуждать их решения, реализовывать код избранных алгоритмов, а также сдавать домашние задания.

	В третьем семестре рассматриваются три больших блока тем: строковые алгоритмы, вычислительные вопросы теории чисел, алгоритмы в геометрии. Предполагается, что слушатели курса знакомы с основными структурами данных: деревьями отрезков и деревьями поиска. Также необходимо базовое знакомство с понятиями теории графов и основными алгоритмами на графах.		В третьем семестре рассматриваются три больших блока тем: строковые алгоритмы, вычислительные вопросы теории чисел, алгоритмы в геометрии. Предполагается, что слушатели курса знакомы с основными структурами данных: деревьями отрезков и деревьями поиска. Также необходимо базовое знакомство с понятиями теории графов и основными алгоритмами на графах.

Spirina.es: /* О курсе */

2026-10-29T15:34:53Z

О курсе

← Предыдущая версия		Версия от 15:34, 29 октября 2026
Строка 1:		Строка 1:
	== О курсе ==		== О курсе ==
	~~Курс алгоритмов~~ и ~~структур данных — одна из ключевых дисциплин в области теоретической информатики на ФПМИ~~. ~~Он посвящён изучению методов эффективного~~ решения ~~вычислительных задач и принципов организации данных~~, ~~лежащих в основе современных программных систем.~~		В семестре планируется 15 лекций и 30 семинаров (практических занятий). На лекциях разбираются различные модельные задачи и алгоритмы их решения, на семинарах студентам предлагается решать теоретические задачи, обсуждать их решения, реализовывать код избранных алгоритмов, а также сдавать домашние задания.
	~~В рамках курса рассматриваются как фундаментальные~~ теоретические ~~вопросы~~, ~~так и практические аспекты применения алгоритмических подходов в реальных задачах~~, ~~возникающих в индустрии~~.

	В ~~первом (осеннем)~~ семестре ~~основное внимание будет сосредоточено на разнообразных структурах данных~~, ~~которые нужны будут~~ в ~~роли «чёрных ящиков» для более продвинутых алгоритмов~~.		В третьем семестре рассматриваются три больших блока тем: строковые алгоритмы, вычислительные вопросы теории чисел, алгоритмы в геометрии. Предполагается, что слушатели курса знакомы с основными структурами данных: деревьями отрезков и деревьями поиска. Также необходимо базовое знакомство с понятиями теории графов и основными алгоритмами на графах.
	~~Для формирования необходимой базы в начале~~ курса ~~разбираются~~:
	*классические линейные алгоритмы,
	*принцип бинарного поиска,
	*основные алгоритмы сортировки.

	~~Далее курс переходит к систематическому изучению структур данных~~, ~~включая:~~		В течение семестра студенты научатся эффективно искать вхождения слов в тексты, а также строить сложные суффиксные структуры для обработки различных запросов и изменений над большими текстами. Кульминацией этой части курса станет построение суффиксного автомата для строки, наиболее мощной структуры данных для представления текстовой информации (например, в биоинформатике).
	*линейные структуры,
	*кучи (~~приоритетные очереди~~),
	*деревья отрезков,
	*деревья поиска,
	*хеш-таблицы,
	*а также ряд менее стандартных, но практически значимых подходов к организации данных.

	~~Курс ориентирован как на студентов~~, ~~изучающих его~~ в ~~рамках обязательной программы~~, ~~так~~		В теоретико-числовом блоке будет рассмотрено несколько классических алгоритмов (извлечение корня, дискретное логарифмирование) в конечных полях, а также алгоритм факторизации. Здесь также даётся материал по быстрому преобразованию Фурье, которое предлагает изящный способ перемножать длинные числа и работать с многочленами и функциональными рядами.
	~~и на всех~~, ~~кто заинтересован в углублённом понимании алгоритмов~~ и ~~стремится научиться разрабатывать эффективные~~ и ~~масштабируемые программные решения~~.

	~~'''Пререквизиты:'''~~		В разделе о геометрии будут разобраны классические простые алгоритмы наподобие выпуклой оболочки и суммы Минковского. Все вопросы здесь критически важны для реализации собственных геометрических и физических движков (при разработке игр или моделировании систем). Из продвинутых алгоритмов разбираются техники пересечения полуплоскостей, построения диаграммы Вороного, триангуляции Делоне и выпуклой оболочки точек в трёхмерном пространстве.

	~~Студенты имеют первичное представление~~ о ~~языках программирования~~. ~~Например, студенты в прошлом сдавали ЕГЭ по информатике~~ или ~~участвовали в разработке ИТ-проектов~~.
	~~От желающих сдавать курс факультативно (по выбору) ожидается знакомство с одним из языков программирования~~ в ~~рамках любого университетского курса~~.

	== Команда курса ==		== Команда курса ==

Spirina.es: /* Материалы курса */

2026-10-29T15:34:08Z

Материалы курса

← Предыдущая версия		Версия от 15:34, 29 октября 2026
Строка 90:		Строка 90:

	Литература:		Литература:
	# ~~Абрамов~~ С. ~~А. Лекции о сложности алгоритмов. МЦНМО~~, ~~2020.~~		# Дасгупта С., Пападимитриу Х., Вазирани У. Алгоритмы. – МЦНМО, 2014
	~~# Рейнгольд Э~~., ~~Нивергельт Ю~~.~~, Део Н~~. ~~Комбинаторные алгоритмы. Теория и практика. «Мир»~~, ~~1980.~~		# Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов – «Мир», 1979
	# Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. «Мир», 1979.		# Препарата Ф., Шеймос М. Вычислительная геометрия: введение – «Мир», 1989
	# ~~Кнут Д. Э~~. ~~Искусство программирования~~, Т. ~~1. «ИД Вильямс», 2018.~~		# Gusfield D. Algorithms on Strings, Trees, and Sequences – Cambridge University Press, 1997
	~~# Кнут Д. Э. Искусство программирования~~, ~~Т. 3. «ИД Вильямс», 2018.~~		# De Berg M. et al. Computational Geometry. Algorithms and Applications – Springer, 2008
	# ~~Карацуба А. А~~., ~~Офман Ю. П. Умножение многозначных чисел на автоматах // Доклады АН СССР~~, ~~1962~~, ~~145(2).~~
	# ~~Strassen V~~. ~~Gaussian elimination is not optimal // Numerische Mathematik, 1969, 13(4).~~
	~~# Кормен Т. и др. Алгоритмы~~. ~~Построение и анализ~~. ~~«ИД Вильямс»~~, ~~2011.~~

Spirina.es: /* Прогресс студентов */

2026-10-29T15:33:22Z

Прогресс студентов

← Предыдущая версия		Версия от 15:33, 29 октября 2026
Строка 78:		Строка 78:

	== Прогресс студентов ==		== Прогресс студентов ==
	Таблица с оценками~~, доступная~~ студентам		Таблица с оценками доступна студентам в канале дисциплины

	== Критерии оценивания и формы контроля успеваемости ==		== Критерии оценивания и формы контроля успеваемости ==