Федеральное государственное бюджетное образовательное
учреждение высшего образования 
Московский государственный университет имени М.В. Ломоносова
Факультет вычислительной математики и кибернетики

УТВЕРЖДАЮ
декан факультета вычислительной математики и кибернетики
______________/И.А. Соколов /
«___» ________________20___г.

РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ
Наименование дисциплины:
Алгоритмы и алгоритмические языки
Уровень высшего образования:
бакалавриат
Направление подготовки / специальность:
01.03.02 «Прикладная математика и информатика» (3++)
Направленность (профиль):
Математические и компьютерные методы решения задач естествознания
Математические методы обработки информации и принятия решений
Системное программирование и компьютерные науки
Форма обучения:
очная

Москва 2023

Рабочая программа дисциплины (модуля) разработана в соответствии с самостоятельно установленным МГУ образовательным стандартом (ОС МГУ) для реализуемых основных профессиональных образовательных программ высшего образования по направлению подготовки 01.03.02, 01.04.02 "Прикладная математика и информатика" программы бакалавриата  Утвержден приказом МГУ от 30 августа 2019 года № 1041 (в редакции приказов МГУ от 11 сентября 2019 года № 1109, от 10 июня 2021 года № 609, от 7 октября 2021 года № 1048, от 21 декабря 2021 года № 1404, от 2 ноября 2022 года № 1299)

1. Дисциплина относится к базовой части ОПОП ВО.

2. Входные требования для освоения дисциплины (модуля): отсутствуют.

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

Компетенции выпускников, частично формируемые при реализации дисциплины (модуля):

•	ОПК-1.Б Способность применять и адаптировать существующие математические и компьютерные методы для разработки и реализации алгоритмов решения актуальных задач в области фундаментальной и прикладной математики
•	ОПК-2.Б Способность применять и модифицировать математические модели, а также интерпретировать полученные математические результаты при решения задач в области профессиональной деятельности 
•	ПК-2.Б Способность понимать и применять в научно-исследовательской деятельности современный математический аппарат
•	ПК-4.Б Способность применять в профессиональной деятельности современные средства разработки программного обеспечения и методы параллельной обработки данных, реализовывать отдельные этапы разработки системного и прикладного программного обеспечения, систем обработки и анализа данных, сетевых технологий

Планируемые результаты обучения по дисциплине (модулю):

Знать:
1.	неформальное и формальные определения понятия «алгоритм»
2.	основные способы конструирования алгоритмов
3.	определения эквивалентности машин Тьюринга
4.	существование универсальной машины Тьюринга
5.	существование алгоритмически неразрешимых проблем
6.	методы доказательства алгоритмической неразрешимости
7.	язык программирования Си, его системные библиотеки, структуру Си-программы.
8.	базовые алгоритмы решения задач сортировки, поиска, топологической сортировки, работы с текстами.
9.	основные структуры данных: стек, очередь, список, дерево и т.п.

Уметь: 
1.	строить алгоритмы для решения простых задач в алгоритмических системах Тьюринга и Маркова
2.	строить универсальную машину Тьюринга
3.	доказывать алгоритмическую неразрешимость конкретных проблем
4.	составлять и отлаживать программы на языке Си
5.	использовать системные библиотеки языка Си
6.	применять базовые алгоритмы и основные структуры данных, изучаемые в курсе, при разработке программ.
7.	оценивать сложность алгоритмов при их выборе.

Владеть:  
1.	современной технологией разработки и отладки программ на языке Си.

4. Формат обучения: лекции проводятся с использованием компьютера и мультимедийного проектора.

5. Объем дисциплины (модуля) составляет 3 з.е., в том числе 54 академических часов, отведенных на контактную работу обучающихся с преподавателем, 54 академических часа на самостоятельную работу обучающихся. 

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

Форма промежуточной аттестации по дисциплине (модулю)	Всего
(часы)	В том числе	
		Контактная работа 
(работа во взаимодействии с преподавателем)
Виды контактной работы, часы	Самостоятельная работа обучающегося,
 часы 
	
		Занятия лекционного типа*	Занятия семинарского типа*	Всего		
1.	Вводная лекция. Цели и задачи курса. Характеристика разделов курса. Алгоритмы. Формализация понятия алгоритма. Машина Тьюринга (МТ).	4	2	0	2	2	
2.	Машина Тьюринга (продолжение). Нормальные МТ. Диаграммы Тьюринга: диаграммы элементарных МТ, правила композиции диаграмм, примеры диаграмм, построение таблицы МТ по диаграмме.	4	4	0	4	2	
3.	Моделирование МТ. Универсальная МТ. Построение универсальной МТ. Проблемы останова и самоприменимости. Нормальные алгоритмы Маркова.	4	2	0	2	2	
4.	Примеры других алгоритмических систем. Тезис Тьюринга-Черча. Стандарты и роль стандартизации. Первая программа на Си. Структура программного файла. Системные библиотеки и их использование.  	4	2	0	2	2	
5.	Описание Си-машины: процессор, классы памяти (регистровые, автоматические и статические переменные). Типы данных языка Си: целые, логические, символьные, с плавающей точкой. Представление в памяти переменных целочисленных типов. Переменные: класс памяти, область действия.	4	4	0	4	2	
6.	Инициализация переменных. Арифметические и логические выражения. Ленивое вычисление логических выражений.	4	2	0	2	2	
7.	Операции присваивания. Точки следования. Форматный ввод-вывод. Приведение типов при вычислении выражений (явное и неявное). 	4	2	0	2	2	
8.	Операторы. Символьный тип и обработка символьных данных. 	4	2	0	2	2	
9.	Массивы. Инициализация массивов.  Строки. Обработка строк. Операция sizeof.	4	2	0	2	2	
10.	Указатели. Адресная арифметика. Массивы и указатели. Преобразования типа указателей. 	4	2	0	2	2	
11.	Функции. Определение и объявление функции. Организация автоматической памяти. Передача параметров. Рекурсия. Хвостовая рекурсия.	4	2	0	2	2	
12.	Встраивание функций. Указатели на функцию. Побитовая обработка данных. Структуры. Указатели на структуры. Составные инициализаторы структур. 	4	2	0	2	2	
13.	Объединения. Анонимные объединения и структуры. Битовые поля. Перечисления. Схема компиляции программ на языке Си. Препроцессор. Директивы препроцессора.	4	2	0	2	2	
14.	Директивы препроцессора (окончание). Компоновка. Классы памяти и компоновки. Динамическое выделение и освобождение памяти.	4	2	0	2	2	
15.	VLA-массивы и их выделение в динамической памяти. Массив переменного размера в составе структуры. Отладка программ. Инструменты поиска ошибок с динамической памятью. Представление данных с плавающей точкой. Стандарт IEEE 754.	4	2	0	2	2	
16.	Вычисление сумм и произведений данных с плавающей точкой. Потеря точности при сложении и вычитании. Выбор правильной последовательности вычислений. Опции компилятора gcc для вычислений с плавающей точкой. Понятие о сложности алгоритмов. Поиск подстроки по образцу. Простейший алгоритм.	4	2	0	2	2	
17.	Текущий контроль успеваемости: коллоквиум №1	4	0	0	0	2	
18.	Алгоритм Кнута – Морриса – Пратта (КМП). Префикс-функция и ее вычисление. Сложность вычисления префикс-функции и алгоритма КМП. Организация типа данных «стек» на динамической памяти.	4	2	0	2	2	
19.	Реализация стека как библиотеки. Использование стека для построения обратной польской записи. Очередь. Списки. Добавление нового элемента в начало и в конец списка. Поиск элемента в списке. Удаление заданного элемента из списка: через возврат указателя на новый список, через передачу двойного указателя. Алгоритм топологической сортировки Вирта (начало).	4	2	0	2	2	
20.	Алгоритм топологической сортировки Вирта (окончание). Простейшие алгоритмы сортировки (выбором, вставками, обменами).  Оценка сложности алгоритмов сортировки.	4	2	0	2	2	
21.	Быстрая сортировка. Двоичные деревья и его обходы (сначала в глубину, сначала в ширину). Нерекурсивный симметричный обход двоичного дерева. «Прошитое» двоичное дерево и его обход.	4	2	0	2	2	
22.	Двоичные деревья поиска и операции над ними (поиск элемента, минимальный и максимальный элементы, следующий элемент, вставка и удаление элемента).	4	2	0	2	2	
23.	Деревья Фибоначчи. Оценка высоты дерева Фибоначчи. АВЛ-деревья. Базовые операции над АВЛ-деревьями. Балансировка АВЛ-дерева. Вставка и удаление элемента в/из АВЛ-дерева. Оценка высоты АВЛ-дерева по дереву Фибоначчи.	4	2	0	2	2	
24.	Красно-черные деревья, их высота и вставка в красно-черное дерево. Самоперестраивающиеся деревья (splay trees). Операция splay (перестраивание). Реализация словарных операций через операцию splay. Реализация операции splay. Сложность словарных операций в splay-деревьях. Обобщение сбалансированных деревьев поиска: ранговые деревья, понятие ранга и ранговой разницы. Ранговые правила для АВЛ-деревьев и красно-черных деревьев.	4	2	0	2	2	
25.	Структура данных «двоичная куча» (binary heap) и сортировка heapsort (пирамидальная сортировка). Сложность пирамидальной сортировки. Хеш-таблицы. Хеширование. Хеширование цепочками. Хеширование с открытой адресацией. Сложность словарных операций для хеш-таблиц.  Методы построения хеш-функций: деление с остатком, умножение.	4	2	0	2	2	
26.	Методы построения хеш-функций: линейная/квадратичная последовательность проб, двойное хеширование. Цифровой поиск. Задача цифрового поиска. Деревья цифрового поиска. Вставка в дерево цифрового поиска.	4	2	0	2	2	
27.	Текущий контроль успеваемости: коллоквиум №2	4	0	0	0	2	
Промежуточная аттестация: письменный экзамен	36	0	0	0	4	
Итого	108	54	0	54	54	

7. Фонд оценочных средств (ФОС) для оценивания результатов обучения по дисциплине (модулю)

7.1. Типовые контрольные задания или иные материалы для проведения текущего контроля успеваемости.

Коллоквиум №1

1. Пусть определены следующие переменные:
int x = 2, y = 4, z = 6;
short n = 0x7FFF; unsigned short m = 0x7FFFU;
struct S { struct P { int x, y; } p; struct S *n; } s = { { -10, -20 }, 
&s };
unsigned int a[10] = { 2, 4, 6, 8, 10, 12, 14, 16, 18, 20 };
unsigned int *p, **pp;
Для каждого из  8 отдельных независимых выражений указать его значение и побочные эффекты (если они есть) либо “ошибка”, если выражение ошибочно.     
1) x | y ^ z
2) n + 4
3) m <<= 1
4) s.p.x = x + s.n->p.y
5) *(a + 4 * x)
6) p = a + 1, **(pp = &p)
7) *pp = &a[2], *(*pp + y + a[2])
8) p = a + a[3], s.p.y = ++p - a

УКАЗАНИЕ.
 В задачах 2-4 определите все необходимые переменные и типы.
Считайте, что вызовы функций выделения памяти всегда заканчиваются успешно.

2. Напишите функцию, принимающую единственный параметр – массив строк (указателей типа char *). Последний элемент массива содержит нулевой указатель. Функция должна возвратить указатель на размещенный в динамической памяти массив структур, в которых первое поле есть указатель на копию одной из входных строк, а второе поле – количество раз, которое данная строка встречалась во входном массиве (с учетом регистра символов). Одинаковые строки (с учетом регистра символов) должны содержаться в выходном массиве только в одном экземпляре, поле с указателем может указывать на любую из них. Выходной массив должен быть отсортирован сначала по убыванию по второму полю, а затем в лексикографическом порядке по первому полю. 

3. Напишите функцию, которая удаляет из односвязного списка все элементы с нечетными номерами. Порядок следования всех остальных элементов должен остаться неизменным. Память, занятая удаляемыми элементами списка, должна быть освобождена с помощью вызова функции free. Считайте, что заголовочного элемента в списке нет и элементы списка нумеруются с 1. Ваша функция должна соответствовать прототипу 
void remove_odd (struct list **);
где struct list описывает элемент списка с целочисленным ключом.

4. Напишите функцию, принимающую три параметра – массив целых чисел, его длину и указатель на целое число. Элементы массива образуют (возможно пустое) двоичное дерево (для элемента a[i] его детьми в двоичном дереве являются элементы a[2*i+1] и a[2*i+2], элемент a[0] – корень дерева). Функция должна возвратить указатель на построенное в динамической памяти (в виде рекурсивной ссылочной структуры) двоичное дерево, в котором  для каждого узла детьми являются те же числа, что и во входном массиве (или нулевой указатель для пустого дерева). По указателю, который является третьим параметром, необходимо записать 1, если построенное дерево является двоичным деревом поиска, и 0 в противном случае.
7.2. Типовые контрольные задания или иные материалы для проведения промежуточной аттестации.

Вариант письменного экзамена по курсу

1. Составьте диаграмму машины Тьюринга (МТ), которая в непустом входном слове над алфавитом А3={0, 1, 2} меняет местами символы в паре подряд стоящих символов (например, входное слово 02121 преобразуется в слово 20211). Пары символов отсчитываются от левого края (первого символа)  слова. Лента МТ  бесконечна только справа. В начальном состоянии головка МТ обозревает пустую ячейку сразу после входного слова, в конечном состоянии – пустую ячейку сразу после выходного слова. Можно предполагать, что слева от входного слова на ленте есть одна пустая ячейка. При построении можно использовать элементарные машины l, r, L, R, символ (сдвиг головки на одну ячейку влево/вправо, сдвиг головки на одно слово влево/вправо, запись символа в  ячейку, соответственно).

2. Дано описание: 
struct list {int key; struct list *next;}; 
Напишите функцию
void move_elts_keys (struct list **src, struct list **dst),
которая переносит из односвязного списка src в односвязный список dst все элементы с чётными ключами, удаляя их при этом  из исходного списка. Перенесенные элементы должны добавляться в начало списка dst в произвольном порядке. Относительный порядок изначальных элементов обоих списков должен остаться неизменным. Считайте, что заголовочного элемента в обоих списках нет, списки могут быть пустыми.

3. Пусть int x = 42; int y = -105;
Для каждого из  6 отдельных независимых выражений указать его значение и побочные эффекты (если они есть) либо “ошибка”, если выражение ошибочно.  
1)  y %= x / 5
2) x ^ ~y & 65
3) y <<= (--x || --y)
4) (y = 1) && (y = 2)
5) x++ + --y
6) x += y, y = x - y, x -= y

4. Что будет напечатано при выполнении программы:

#include <stdio.h>
int x = 2, y = 1;
int a[3] = { 1, 2 };
int f (int x, int **p) {
  static int c = 2;
  if (c--) 
    **p += x;
  else 
    ++x;
  return (*p)++ - a - x;
}

int main (void) {
  int x = y, c = 0;  int *p;
  p = &a[x];
  for (int y = 2; y >= c; --y, ++x) 
    c = f (y, &p);
  printf ("%d %d %d %d %d\n", a[0], a[1], a[2], x, y);
  return 0;
}    

5. Перепишите приведенный фрагмент программы с использованием единственного оператора  switch (дополнительные условные операторы использовать запрещено):

if (i == -1)
  j = i;
else if (3 >= i && i >= 1)
  j = 10 - i;
else
  abort ();

6. С использованием единственного цикла for напишите фрагмент программы, который для массива int a[N] формирует в переменной pairs количество пар соседних элементов, имеющих разную четность. Другие операторы циклов и операторы перехода использовать запрещено.

7. Напишите функцию 
int scalar (void), 
которая считывает со стандартного потока ввода непустую последовательность целых чисел, заканчивающуюся нулем (нуль не входит в последовательность, количество ненулевых элементов четно, элементы нумеруются с 1). Функция возвращает значение скалярного произведения двух векторов, составленных из элементов последовательности: первый вектор – из элементов с нечетными номерами, второй вектор – из элементов с четными номерами. В решении можно использовать не более одного оператора цикла. Запрещается использовать операторы перехода.
8. Напишите функцию 
void erase (char *s, const char *w), 
на вход которой дается строка s и слово w. Слово – непустая строка из латинских букв. Строка s представляет собой последовательность слов, разделенных одним пробелом. Перед первым словом и после последнего пробелов нет. Функция должна удалить из строки s все слова, в которые слово w входит как подстрока. Относительный порядок всех остальных слов должен остаться неизменным. Измененная таким образом строка s должна удовлетворять всем тем же ограничениям, что и входная. Память под все временные массивы должна выделяться динамически и освобождаться в конце работы функции. 

9. Дано описание: 
struct avltree {int x; struct avltree *left, *right;};
Напишите функцию 
struct avltree *build (int h), 
которая строит АВЛ-дерево заданной высоты h, содержащее минимальное количество узлов n из всех АВЛ-деревьев с этой высотой. Значения ключей в элементах АВЛ-дерева должны быть от 1 до n.

10. Нарисуйте дерево цифрового поиска для алфавита {В, М, И, К}, которое содержит следующие ключи: КИМ, МИКИ, ВИМ, ИМ, ИК, ВК, МИМ, ВМК, В, МИ, ВМИК, МИМИ.

ШКАЛА И КРИТЕРИИ ОЦЕНИВАНИЯ результатов обучения (РО) по дисциплине (модулю)  
	
Оценка
РО и
соответствующие виды оценочных средств 	2	3	4	5	
Знания
Экзамен	Отсутствие знаний	Фрагментарные знания	Общие, но не структурированные знания	Сформированные систематические знания	
Умения
Коллоквиум №1, Коллоквиум №2 	Отсутствие умений	В целом успешное, но не систематическое умение	В целом успешное, но содержащее отдельные пробелы умение (допускает неточности непринципи-ального характера)	Успешное и систематическое умение	
Навыки 
(владения, опыт деятельности)
Экзамен 	Отсутствие навыков (владений, опыта)	Наличие отдельных навыков (наличие фрагментарного опыта)	В целом, сформированные навыки (владения), но используемые не в активной форме	Сформированные навыки (владения), применяемые при решении задач	
Соответствие результатов обучения и компетенций, в развитии которых участвует дисциплина (модуль)
	
Результаты обучения	Компетенция, с частичным формированием которой связано достижение результата обучения	
Знать:
1.	основные способы конструирования алгоритмов
2.	методы доказательства алгоритмической неразрешимости
3.	базовые алгоритмы решения задач сортировки, поиска, топологической сортировки, работы с текстами.	

ОПК-1.Б	
Знать:
1.	неформальное и формальные определения понятия «алгоритм»
2.	определения эквивалентности машин Тьюринга
3.	существование универсальной машины Тьюринга
4.	существование алгоритмически неразрешимых проблем
5.	основные структуры данных: стек, очередь, список, дерево и т.п.	

ОПК-2.Б	
Уметь:  
1.	строить алгоритмы для решения простых задач в алгоритмических системах Тьюринга и Маркова
2.	строить универсальную машину Тьюринга
3.	доказывать алгоритмическую неразрешимость конкретных проблем
4.	оценивать сложность алгоритмов при их выборе.	

ПК-2.Б	
Знать:
1.	язык программирования Си, его системные библиотеки, структуру Си-программы.
2.	базовые алгоритмы решения задач сортировки, поиска, топологической сортировки, работы с текстами.
3.	основные структуры данных: стек, очередь, список, дерево и т.п.

Уметь:  
1.	составлять и отлаживать программы на языке Си
2.	использовать системные библиотеки языка Си
3.	применять базовые алгоритмы и основные структуры данных, изучаемые в курсе, при разработке программ.

Владеть:  
1.	современной технологией разработки и отладки программ на языке Си.	

ПК-4.Б	
8. Ресурсное обеспечение:

Основная литература:
  
1.	Г. Эббинхауз, К. Якобс, Ф. Манн, Г. Хермес. Машины Тьюринга и рекурсивные функции «Мир», М. – 1972.
2.	Л.С. Корухова, М.Р. Шура-Бура. Введение в алгоритмы (учебное пособие для студентов I курса).
3.	Брайан Керниган, Деннис Ритчи. Язык программирования Си. Издание 2-е, «Вильямс» – 2010.
4.	А.А. Белеванцев, С.С. Гайсарян,  Л.С. Корухова, Е.А. Кузьменкова, В.С. Махнычев. Семинары по курсу “Алгоритмы и алгоритмические языки” (учебно-методическое пособие для студентов 1 курса). М., 2012: Издательский отдел факультета ВМК МГУ имени  М.В. Ломоносова.
5.	 А.А. Белеванцев, С.С. Гайсарян, В.П. Иванников, Л.С. Корухова, В.А. Падарян. Задачи экзаменов по вводному курсу программирования (учебно-методическое пособие). М.: Изд. отдел ф-та ВМК МГУ имени М.В. Ломоносова,  2012.
6.	К.А. Батузов, А.А. Белеванцев, Р.А. Жуйков, А.О. Кудрявцев, В.А. Падарян, М.А. Соловьев. Практические задачи по вводному курсу программирования (методическое пособие). М., 2012: Изд. отдел ф-та ВМК МГУ имени М.В. Ломоносова
7.	О.В. Сенюкова. Сбалансированные деревья поиска: учебно-методическое пособие. М.: Издательский отдел факультета ВМК МГУ имени М.В. Ломоносова; МАКС Пресс, 2014.

Дополнительная литература:

1.	Stephen Prata. C Primer Plus. Fifth Edition. Sams Publishing 2004. ISBN 0-672-32696-5.
2.	Стандарт языка Си С99 + TC{1,2,3}. http://www.open-std.org/JTC1/SC22/WG14/www/docs/n1256.pdf
3.	Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. Алгоритмы. Построение и анализ. Издание 2-е. «Вильямс» – 2011
4.	Н. Вирт. Алгоритмы + структуры данных = программы. - М., “Мир”, 1985.
5.	Д. Кнут. Искусство программирования для ЭВМ..
         Т.1. Основные  алгоритмы.
         Т.2. Сортировка  и поиск.- М., изд-во Вильямс, 2010, 2011, 2012

Информационные справочные системы:  https://algcourse.cs.msu.ru/

Материально-техническкое обеспечение:  аудитория с компьютером и мультимедийным проектором.

9. Язык преподавания - русский.

10. Преподаватели:  профессора факультета ВМК МГУ С.С. Гайсарян, А.А. Белеванцев.

11. Авторы программы:  профессора факультета ВМК МГУ С.С. Гайсарян, А.А. Белеванцев.