Алгоритмы и структуры данных, часть 1

Санкт-Петербург, осень 2020

Описание

О курсе

Этот курс поможет вам получить представление о фундаментальной составляющей программирования — алгоритмах, а также о том как хранить данные и обрабатывать их — структурах данных. Мы научимся понимать, какие алгоритмы и какие структуры данных подходят к данной вам задаче, какие более эффективные. Научимся понимать какого рода задача вам поставлена. Рассмотрим множество приемов, которые уже придумало человечество, поймем, как они это придумали, и сравним эти приемы.

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

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

Продолжим структурами данных, алгоритмами на графах и другими не менее интересными темами.

Домашние задания

Будут состоять из двух типов задач:

Задачи на программирование будут приниматься в автоматическом режиме на системе для контестов.

Задачи на доказательство будет приниматься через сайт центра.

Критерии выставления оценки

Оценка будет выставляться по результатам решения домашних заданий. Теоретические домашние задания составляют 50% от общей оценки, задачи на программирование — 50%.

За 85% решённых задач выставляется оценка отлично,

за 75% — хорошо,

за 60% — зачёт.

Оценка теоретических домашних заданий

Всего будет \(7\) домашних заданий. За каждое домашнее задание можно набрать 1 балл максимум. В каждом домашнем задании есть несколько задач. Решение каждой задачи вносит одинаковый вклад в оценку этого домашнего задания.

В каждом домашнем задании указано, сколько задач нужно решить, чтобы получить максимальный балл. Получить больше максимального балла нельзя. Например, если в одном домашнем задании есть 4 задачи, но для максимального балла нужно решить 3, то если вы полностью решаете любые 3 из 4, то получаете 1 балл. Либо если же вы решаете две задачи правильно, а две задачи наполовину, то тоже получите 1 балл за домашнее задание.

Оценка за все домашние задания:

  • Взять \(n - 1\) лучших домашних задания студента, \(S\) — это сумма баллов по этим домашним заданиям.

  • Оценка за теоретические домашние задания — это \(\frac{S}{n - 1}\).

Получается, что один ваш худший результат по домашнему заданию не учитываются в общей оценке. Это дает вам некоторый выбор не учитывать два домашних задания по разным причинам, например, если вы не успеваете к дедлайну. Но при этом, пожалуйста, не просите подвинуть дедлайн.

Оценка домашних заданий на программирование

Всего будет как минимум 25 задач суммарно, они будут разбиты на контесты на сайте Codeforces. Каждая задача вносит одинаковый вклад в общую оценку заданий по программированию. Пусть \(S\) — число решенных задач во всех контестах, а \(P\) — суммарное число задач во всех контестах, тогда ваша оценка за домашние задания на программирования — это \(\frac{S}{P}\)

Преподаватели