Need help with lections_2020?
Click the “chat” button below for chat support from the developer who created it, or find similar developers for support.

About the developer

tkhirianov
149 Stars 49 Forks Other 65 Commits 2 Opened issues

Services available

!
?

Need anything else?

Contributors list

# 205,733
Python
C
63 commits

Алгоритмы и структуры данных (С++), 2020 г.

Программный код с лекций по информатике Хирьянова Т.Ф. на ФТШ ЛФИ МФТИ (ФОПФ) в 2020 году.

Лицензия на материалы курса: Attribution ShareAlike CC BY-SA 4.0

Сайт курса: http://cs.mipt.ru/cpp_algo

Рабочая программа дисциплины "Информатика":

по дисциплине: Информатика по направлению: 03.03.01 «Прикладные математика и физика» физтех-школа: ЛФИ кафедра: информатики и вычислительной математики курс: 1 семестр: 2

Трудоёмкость: - лекции – 30 часов - лабораторные занятия – 60 часов - самостоятельная работа – 90 часов

ВСЕГО АУДИТОРНЫХ ЧАСОВ – 90

Программу и задание составил: ст. преп. Т.Ф. Хирьянов

Тематический план семестра

  1. Ввод-вывод, ветвления и циклы. Однопроходные алгоритмы. Структура простой программы. Переменные С++: необходимость объявления, строгость типизации, присваивание. Ввод-вывод в std:: потоки cin, cout, cerr. Арифметические операции +, -, *, /. Операторы сравнения <, <=, ==, !=. Описание простых функций. Cинхронный вызов и возврат по стеку вызовов. Метки и goto. Доводы против оператора goto Эдсгера Дейкстры. Оператор for. Генерация арифметической и геометрической прогрессий. Оператор if. Фильтрация потока чисел. Оператор while. Алгоритм Евклида на С++. Вложенные и каскадные условные конструкции. Обработка последовательностей: подсчёт, сумма, произведение, поиск максимального. Инициализация переменной при поиске максимума и минимума.
  2. Целый и логический типы. Алгоритмы полного перебора. Двоичное представление данных. Двоичное кодирование. Двоичная СС и кольца вычетов. Знаковые целые: дополнительный код. Целочисленные типы С++11: intN_t. Явное приведение типа. Битовые операции с целыми: сдвиги, наложение маски. Обмен переменных значениями: универсальный и через XOR. Остаток при делении нацело: %. Разложение числа на цифры. Логический тип bool. Операции !, &&, ||, ^ и , not, and, or, xor. Индуктивные функции: поиск числа, проверка критерия. Алгоритмы полного перебора. Тест простоты числа с использованием переменной-флага. Разложение числа на множители. Управление циклом: break, continue. Определение типа struct. Функция sizeof().
  3. Плавающая точка. Математические методы. Представление вещественных чисел в памяти ПК. Cтандарт IEEE 754-2008. Типы чисел с плавающей точкой в С++ и их соответствие стандарту. Арифметика чисел с плавающей запятой (точкой). Ошибки вычислений. Машинная точность. Иерархия типов чисел в С++. Неявное приведение типа. «Грабли»: приоритет беззнаковых, деление целых. Список всех операций С++ с приоритетами. Модуль cmath. Математические функции С++: выражение аналитических функций. Суммирования ряда Тейлора. Численное интегрирование. Бисекция. Поиск корня уравнения методом двоичного поиска.
  4. Одномерные массивы. Адреса и указатели. Массивы в С++. Хранение в памяти. Фиксированный размер и однотипность элементов. Скорость доступа к элементам. Решето Эратосфена. Копирование массива. Копирование с реверсом. Реверс массива и циклический сдвиг. Добавление и удаление элемента в конце и в начале массива. Стек, очередь и дек на массиве. Адреса и указатели в С++. Размер ячейки для хранения адреса. Разыменование * и взятие адреса &. Адресная арифметика в С++. Преобразование типа указателя. Тип void*. Реинтерпретация данных. Массивы структур struct и структура struct, содержащая массив. Проверка корректности скобочной последовательности.
  5. Универсальные сортировки O(N2). Сортировка массива: постановка задачи. Сортировка обезьяны (без реализации). Проверка упорядоченности за O(N). Сортировка дурака. Сортировка методом пузырька. Сортировка вставками. Сортировка выбором. Устойчивость сортировок.
  6. Связные списки. Динамическая память. Выделение и освобождение динамической памяти: malloc(), calloc(), free(). Операторы new и delete. Ошибки работы с памятью. Контроль за динамической памятью. Некорректные адреса. Инициализация указателей: NULL и nullptr. Создание одномерного динамического массива. Реаллокация в памяти для динамического расширения массива. Списки: односвязный, двусвязный, кольцо. Асимптотика связных списков для разных задач. Стек на односвязном списке. Дек на двусвязном списке.
  7. Двумерные массивы. Обычные двумерные массивы в С++. Заполнение двумерного массива. Треугольник Паскаля. Транспонирование матрицы. Умножение матриц. Динамические двумерные массивы в С++. Линеаризация двумерного массива вручную. Функции. Синхронный вызов. Возврат по стеку вызовов. Сегмент STACK и передача параметров по значению. Модель памяти приложения. Локальные и глобальные переменные. Передача массива в функцию и возврат из функции в С++. Проблема ответственности за освобождение памяти.
  8. Бинпоиск и спецсортировки. Линейный поиск в массиве. Бинарный поиск в упорядоченном массиве. Сортировка подсчётом. Поразрядная сортировка.
  9. Рекурсия. Метод ветвей и границ. Прямой и обратный ход рекурсии. Факториал числа. Алгоритм Евклида. Быстрое возведение в степень. Вычисление чисел Фибоначчи. Ханойские башни. Рекурсивная генерация всех чисел длины M. Генерация всех перестановок в массиве. Перебор с возвратом: метод ветвей и границ.
  10. Быстрые сортировки. Принцип «Разделяй и властвуй». Умножение Карацубы. Быстрая сортировка Тони Хоара. Сортировка слиянием.
  11. Динамическое программирование. Количество траекторий на схеме дорог. Проблема повторных вычислений на примере чисел Фибоначчи. Динамическое программирование сверху и снизу. Кузнечик: количество траекторий, траектория минимальной стоимости.
  12. Двумерное динамическое программирование. Алгоритм укладки рюкзака (дискретный). Наибольшая общая подпоследовательность. Наибольшая возрастающая подпоследовательность.
  13. Строки и работа с файлами. Кодировки символов: ASCII, однобайтные и семейство Unicode. Строка как массив символов. Си-строки и ANSI-строки. Почему Си-строки не следует использовать для обработки текста. Проверка равенства строк. Простой и вероятностный алгоритмы. Вычисление расстояния Левенштейна. Поиск последовательности редакционных изменений. Работа с файлами в чистом Си. Два уровня API.
  14. Поиск подстрок. С++ строки std::string. Поиск подстроки: наивный алгоритм. Префикс-функция. Алгоритм Кнута-Морриса-Пратта. Z-функция и Z-алгоритм. Работа с потоками ifstream, ofstream, fstream. Форматирование ввода-вывода: iomanip.
  15. Параллелизм на системах с общей памятью. Ресурс параллельности. Потоки. Асинхронные вызовы.

Методические указания обучающимся

Ваша цель — запомнить классические алгоритмы и структуры данных, знать их асимптотическую сложность, уметь их описывать устно, а также программировать их на языке C++. Курс содержит три вида учебной деятельности: 1) лекции, 2) лабораторные работы и 3) самостоятельная работа.

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

Описания лабораторных работ появляются по ходу семестра на сайте http://cs.mipt.ru/cpp_algo. Очное присутствие на лабораторных обязательно. Типичная работа представляет из себя: а) текст для изучения; б) упражнения; в) контест с автоматизированной системой проверки. Автоматически проверяемые задачи допускается доделывать дома в качестве самостоятельной работы. В самостоятельную работу включается также подготовка к сдаче устного зачёта. В течение семестра на лабораторных занятиях проводится 2 контрольные работы: промежуточная и итоговая.

Оценивание

Дифференцированный зачёт сдаётся устно. Рекомендуемая итоговая оценка студента по предмету — это среднее арифметическое взвешенное оценок по лабораторным работам и контрольным. Преподаватель, экзаменующий студента, видит все эти оценки по отдельности, а также рекомендуемую итоговую оценку. Исходя из ответа студента итоговая оценка в зачётку может быть отклонена от рекомендуемой на ±2 балла (по 10-балльной шкале). Если преподаватель хочет повысить или понизить оценку на большее число баллов, он советуется со старшим преподавателем курса. Студент при несогласии с итоговой оценкой может потребовать апелляции у старшего преподавателя (в конце зачётной недели).

We use cookies. If you continue to browse the site, you agree to the use of cookies. For more information on our use of cookies please see our Privacy Policy.