Практические занятия по курсу ОиМП

О курсе

Форум.

Алгоритм подсчёта итоговой оценки по курсу

В курсе предусмотрены следующие виды работ: четыре домашние работы, контрольная и экзамен. За каждую из шести работ выставляется оценка от 0 до 10 включительно. При этом 20% от оценки за домашнюю работу составляет оценка за текущие работы:

<оценка за текущую работу> = 10*(<количество выполненных обязательных заданий> + 0.3 * <количество выполненных необязательных заданий>) / <количество обязательных заданий>

<итоговая оценка за текущую работу> = min(<оценка за текущую работу>, 10)

<итоговая оценка за домашнюю работу (ИОДР)> = 0.8 * <оценка за домашнюю работу> + 0.2 * <итоговая оценка за текущие работы>

<итоговая оценка по курсу> = 0.6 * (<ИОДР 1> + <ИОДР 2> + <ИОДР 3> + <ИОДР 4>)/4 + 0.15 * <оценка по контрольной работе> + 0.25 * <оценка за экзамен>

C++

C++ styleguide.

Среда разработки

Лучше всего использовать Eclipse. Инструкция по созданию проекта Eclipse.

Если не получится установить или запустить, то можно:

1. Использовать Visual Studio (только для тех, кто в ней уже работал).
2. Использовать онлайн компилятор: compileonline или ideone. В ideone требуется поменять язык с Java на C++11. В обоих компиляторах требуется в поле ввода stdin вписать значения, которые подаются программе на вход. Например, для первой программы из примера ниже, можно написать "24" (без кавычек), для второй "0.2 1.1".

Примеры программ

Требуется спросить у пользователя его возраст, а затем вывести возраст и 1, если он больше 20, и 0, если меньше или равен.

#include <iostream>
using namespace std;
 
int main() {
    cout << "How old are you?" << endl;
    int age; // объявление целочисленной переменной в которой будет храниться возраст
    cin >> age; // чтение с консоли
    cout << "Your age: " << age << ", it's more than 20: " << (age > 20) << endl;
}

Пользователь вводит два вещественных числа step и bound. Требуется вывести вещественные все числа через пробел, начиная с 0 с шагом step и не превосходящие bound.

#include <iostream>
using namespace std;
 
int main() {
    double step;
    double bound;
    cin >> step >> bound;
    for (double d=0; d < bound; d += step) {
        cout << d << " ";
    }
}

Задание 1 Основные конструкции С++ (08.10 - 22.10)

Введение в C++. Нужно сделать 9 любых задач из 10.

Задание 2. Функции (11.10 - 21.10)

Функции в C++. Нужно сделать 7 любых задач из 8.

Задание 3. Контейнеры. vector и list (18.10 - 1.11)

Обработка последовательностей. Нужно решить 15 (из 18) любых задач. Перед выполнением обязательно прочитайте требования к решениям:

1. Важно! В каждой задаче используйте vector или list даже если задачу можно решить без использования контейнера. Половину задач решите, используя список, половину используя вектор.
2. Давайте функциям и переменным понятные имена. Такие, чтобы по имени можно было понять что они делают.
3. Не используйте однобуквенных имён переменных, кроме имён для счётчиков цикла (i, j, k, ...).
4. Не используйте транслит при именовании переменных.
5. Старайтесь вынести логические блоки в отдельные функции. Подсказка: чтение вектора (списка) должно быть оформлено как отдельная функция.
6. Решение каждого задания должно быть оформлено в отдельной функции.
7. Для каждой функции пишите комментарий с пояснением что делает эта функция. В комментарии можно описать входные и выходные значения.
8. При передаче параметров в функции пишите const везде, где это возможно; передавайте по ссылке везде, где это уместно.
9. Везде, где это уместно, пишите шаблоны функций.

Требования обязательны, но проверяться они не будут. То есть, за программу не удовлетворяющую требованиям выше, я не снижу оценку. Этот контест --- это возможность попрактиковаться в написании красивого кода (и поспрашивать что красиво, а что нет) перед второй домашней работой в которой, скорее всего, оценки за некрасоту кода будут снижаться. Я не буду прицельно смотреть сданные вами решения, ибо предполагаю, что когда вам что-то непонятно, вы сами покажите код и спросите какие есть замечания.

Полезные ссылки

1. Функции vector-a.
2. Функции list-a.

Необязательное задание

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

1. Напишите функцию, которая заполняет вектор случайными элементами.
2. Напишите функцию, которая принимает на вход два вектора и возвращает true, если они равны, и false в противном случае.
3. Напишите функцию, которая принимает на вход вектор и сортирует его пузырьком.
4. Напишите функцию, которая принимает на вход вектор и сортирует его поиском максимума.
5. Напишите функцию, которая принимает на вход вектор и сортирует его слиянием.
6. Напишите функцию, которая принимает на вход вектор и сортирует его быстрой сортировкой.
7. Выведите время работы каждой из функций сортировки для векторов разной длины.

Домашнее задание 2 (21.10 - 7.11)

Второе большое домашнее задание. Каждому студенту требуется сделать пять задач из 20. Список обязательных задач здесь (не ошибитесь вкладкой!).

При оценке домашнего задания будут учитываться оценки за задания 1-3.

Внимание! За некрасивый код и плохие неэффективные решения оценка будет снижаться!

Внимание! После 7.11 задания 1-3 и вторая домашняя работа не принимаются.

Контрольная работа (8.11)

Контрольная работа.

Задание 4. Шаблонные функции и классы (13.11)

Шаблоны в C++. Нужно сделать 5 задач из 5.

Задание 6. Работа с классами (19.11)

Проект Книжный магазин. Каждый пункт считается отдельной задачей. Требуется запрограммировать всё, кроме дополнительных заданий. Работа каждой публичной функции должна быть продемонстрирована в main.

Задание 7. Алгоритмы STL (27.11)

Алгоритмы STL. Обязательны 3 из 5.

Домашние задания 3 и 4 (4.12 - 17.12)

Домашнее задание будет оцениваться по 20-бальной системе. Список обязательных задач (не ошибитесь вкладкой!).

Задание 8. Наследование (18.12 - 24.12)

Реализуйте один из трёх проектов: Книги со скидкой, Иерархия многоугольников или РостовЛифтМонтаж. Каждый из проектов стоит 10 баллов. Задание является обязательным.

Пробный вариант экзамена

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

Питон

Полезные ссылки

Для выполнения заданий необходимо установить интерпретатор Python.

Style guide.

Задачи, которые точно нужно уметь решать.

Рекомендации по выполнению

1. Не используйте wildcard imports (from <module> import *), см. PEP8.
2. Знак присваивания обособляйте пробелами с двух сторон. Плохо: a=b. Хорошо: a = b.
3. Если требуется сравнить два числа с плавающей точкой (float) на равенство, то сравнивайте модуль их разницы с некоторым eps: |d1 - d2| < 0.0000001.

Задание 1. Ввод-вывод (4.09 - 20.09)

Задачи.

Список обязательных задач для каждого студента.

Задание 2 (6.09 - 20.09)

Перед выполнением задания нужно установить библиотеку Pillow.

Задачи.

Замечание. Доступ к элементам pixels осуществляется так: pixels[i,j].

Бонусные задачи

1. Реализуйте масштабирование.
2. Реализуйте отражение.
3. Реализуйте размытие.
4. Напишите свой фильтр для обработки изображений.

Задание 3 (13.09 - 27.09)

Решите 20 любых задач из контеста Ввод-вывод.

Бонусное задание. Шифрование RSA

1. Реализуйте алгоритм создания открытого и секретного ключей.
2. Реализуйте алгоритмы шифрования и дешифрования. Проверьте, что они работают.
3. Реализуйте алгоритм взлома. Функция должна принимать аргументы c, n и m (см. обозначения в Википедии) и возвращать d, приватный ключ, такое что m == c^d mod n.
4. Научитесь замерять время выполнения каждой из четырёх функций (функции генерации ключей, шифрования, дешифрования и взлома).
5. Выберите некоторое значение m, например, m=100. Выведите таблицу:

	n=11*13=143	n=17*31=527	n=109*157=17113	n=3557*2579=9173505	n=3533*3571=12616343
e=3
e=17
e=257
e=65537

На пересечении i-ой строки и j-ого столбца должно стоять четыре неотрицательных числа --- время работы каждого из четырёх алгоритмов при заданных e и n. Если данное e не взаимно просто с n, поставить прочерк.

Задание 4 (18.09 - 2.10)

Если в вашей фамилии чётное число букв, то решите все чётные задачи из контеста Обработка текста, иначе все нечётные.

Домашнее задание 1 (26.09 - 6.10)

Первое большое домашнее задание. Каждому студенту требуется сделать пять задач из 20. Список обязательных задач здесь.

При оценке домашнего задания будут учитываться оценки за задания 1-4.

Копия домашней работы. Если вы что-то решили/нашли ошибку после окончания срока сдачи домашней работы, вы можете отправить решения туда, чтобы проверить их. Эти результаты не будут учтены при оценке домашней работы.

Внимание! После 6.10 задания 1-4 и первая домашняя работа не принимаются.