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

==О курсе==
[https://groups.google.com/forum/?hl=ru#!forum/amcs105-1 Форум.]

=== Алгоритм подсчёта итоговой оценки по курсу ===
В курсе предусмотрены следующие виды работ: четыре домашние работы, контрольная и экзамен. За каждую из шести работ выставляется оценка от 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++ check|C++ styleguide.]]

===Среда разработки===
Лучше всего использовать Eclipse. [http://hightech.in.ua/content/art-eclipse-c-cpp-ide Инструкция по созданию проекта Eclipse.]

Если не получится установить или запустить, то можно:
# Использовать Visual Studio (только для тех, кто в ней уже работал).
# Использовать онлайн компилятор: [http://www.compileonline.com/compile_cpp11_online.php compileonline] или [http://ideone.com/ ideone]. В ideone требуется поменять язык с Java на C++11. В обоих компиляторах требуется в поле ввода stdin вписать значения, которые подаются программе на вход. Например, для первой программы из примера ниже, можно написать "24" (без кавычек), для второй "0.2 1.1".

===Примеры программ===
Требуется спросить у пользователя его возраст, а затем вывести возраст и 1, если он больше 20, и 0, если меньше или равен.
<source lang="cpp">
#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;
}
</source>

Пользователь вводит два вещественных числа step и bound. Требуется вывести вещественные все числа через пробел, начиная с 0 с шагом step и не превосходящие bound.
<source lang="cpp">
#include <iostream>
using namespace std;

int main() {
    double step;
    double bound;
    cin >> step >> bound;
    for (double d=0; d < bound; d += step) {
        cout << d << " ";
    }
}
</source>

===Задание 1 Основные конструкции С++ (08.10 - 22.10)===
[http://official.contest.yandex.ru/contest/723/enter/ Введение в C++.] Нужно сделать 9 любых задач из 10.

===Задание 2. Функции (11.10 - 21.10)===
[http://official.contest.yandex.ru/contest/732/enter/ Функции в C++.] Нужно сделать 7 любых задач из 8.

===Задание 3. Контейнеры. vector и list (18.10 - 1.11)===
[http://official.contest.yandex.ru/contest/762/enter/ Обработка последовательностей.] Нужно решить 15 (из 18) любых задач. Перед выполнением обязательно прочитайте требования к решениям:
# '''Важно!''' В каждой задаче используйте vector или list даже если задачу можно решить без использования контейнера. Половину задач решите, используя список, половину используя вектор.
# Давайте функциям и переменным понятные имена. Такие, чтобы по имени можно было понять что они делают.
# Не используйте однобуквенных имён переменных, кроме имён для счётчиков цикла (i, j, k, ...).
# Не используйте транслит при именовании переменных.
# Старайтесь вынести логические блоки в отдельные функции. Подсказка: чтение вектора (списка) должно быть оформлено как отдельная функция.
# Решение каждого задания должно быть оформлено в отдельной функции.
# Для каждой функции пишите комментарий с пояснением что делает эта функция. В комментарии можно описать входные и выходные значения.
# При передаче параметров в функции пишите const везде, где это возможно; передавайте по ссылке везде, где это уместно.
# Везде, где это уместно, пишите ''шаблоны функций''.
Требования обязательны, но проверяться они не будут. То есть, за программу не удовлетворяющую требованиям выше, я не снижу оценку. Этот контест --- это возможность попрактиковаться в написании красивого кода (и поспрашивать что красиво, а что нет) перед второй домашней работой в которой, скорее всего, оценки за некрасоту кода будут снижаться. Я не буду прицельно смотреть сданные вами решения, ибо предполагаю, что когда вам что-то непонятно, вы сами покажите код и спросите какие есть замечания.

====Полезные ссылки====
# [http://ru.cppreference.com/w/cpp/container/vector Функции vector-a.]
# [http://ru.cppreference.com/w/cpp/container/list Функции list-a.]

====Необязательное задание====
Задачи можно решать в любом порядке и можно решить не все. Старайтесь использовать понятные имена функций и переменных. Избегайте транслит.
# Напишите функцию, которая заполняет вектор случайными элементами.
# Напишите функцию, которая принимает на вход два вектора и возвращает true, если они равны, и false в противном случае.
# Напишите функцию, которая принимает на вход вектор и сортирует его пузырьком.
# Напишите функцию, которая принимает на вход вектор и сортирует его поиском максимума.
# Напишите функцию, которая принимает на вход вектор и сортирует его слиянием.
# Напишите функцию, которая принимает на вход вектор и сортирует его быстрой сортировкой.
# Выведите время работы каждой из функций сортировки для векторов разной длины.

===Домашнее задание 2 (21.10 - 7.11)===
[http://official.contest.yandex.ru/contest/788/enter/ Второе большое домашнее задание.] Каждому студенту требуется сделать пять задач из 20. Список обязательных задач [https://docs.google.com/spreadsheets/d/1LqW4k7heilZ8i1B7NCMGcr41kd5Pz1gIyD5rrOyGZjI/edit#gid=2906427757 здесь] (не ошибитесь вкладкой!).

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

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

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

===Контрольная работа (8.11)===
[http://official.contest.yandex.ru/contest/827/enter/ Контрольная работа.]

===Задание 4. Шаблонные функции и классы (13.11)===
[http://official.contest.yandex.ru/contest/871/enter/ Шаблоны в C++.] Нужно сделать 5 задач из 5.

===Задание 6. Работа с классами (19.11)===
[http://edu.mmcs.sfedu.ru/mod/assign/view.php?id=5469 Проект Книжный магазин.] Каждый пункт считается отдельной задачей. Требуется запрограммировать всё, кроме дополнительных заданий. Работа каждой публичной функции должна быть продемонстрирована в main.

===Задание 7. Алгоритмы STL (27.11)===
[http://official.contest.yandex.ru/contest/940/enter/ Алгоритмы STL.] Обязательны 3 из 5.

===Домашние задания 3 и 4 (4.12 - 17.12)===
[http://official.contest.yandex.ru/contest/955/enter/ Домашнее задание] будет оцениваться по 20-бальной системе. [https://docs.google.com/spreadsheets/d/1LqW4k7heilZ8i1B7NCMGcr41kd5Pz1gIyD5rrOyGZjI/edit?usp=sharing Список обязательных задач] (не ошибитесь вкладкой!).

===Задание 8. Наследование (18.12 - 24.12)===
Реализуйте один из трёх проектов: [http://edu.mmcs.sfedu.ru/mod/assign/view.php?id=5641 Книги со скидкой], [http://edu.mmcs.sfedu.ru/mod/assign/view.php?id=5641 Иерархия многоугольников] или [http://edu.mmcs.sfedu.ru/mod/assign/view.php?id=8320 РостовЛифтМонтаж]. Каждый из проектов стоит 10 баллов. Задание является обязательным.

===Пробный вариант экзамена===
[http://official.contest.yandex.ru/contest/965/enter/ Пробный вариант экзамена.] За задание баллы начисляться не будут.

==Питон==

===Полезные ссылки===
Для выполнения заданий необходимо [https://www.python.org/download установить интерпретатор Python].

[http://legacy.python.org/dev/peps/pep-0008 Style guide].

[https://yadi.sk/i/FBgNvf4nbQ4Jq Задачи, которые точно нужно уметь решать.] 

===Рекомендации по выполнению===
# Не используйте wildcard imports (from <module> import *), см. [http://legacy.python.org/dev/peps/pep-0008/#imports PEP8].
# Знак присваивания обособляйте пробелами с двух сторон. Плохо: a=b. Хорошо: a = b.
# Если требуется сравнить два числа с плавающей точкой (float) на равенство, то сравнивайте модуль их разницы с некоторым eps: |d1 - d2| < 0.0000001.

===Задание 1. Ввод-вывод (4.09 - 20.09)===
[http://official.contest.yandex.ru/contest/642/ Задачи.]

[https://docs.google.com/spreadsheets/d/1LqW4k7heilZ8i1B7NCMGcr41kd5Pz1gIyD5rrOyGZjI/edit?usp=sharing Список обязательных задач для каждого студента.]

===Задание 2 (6.09 - 20.09)===
Перед выполнением задания нужно установить библиотеку [http://pillow.readthedocs.org/en/latest/ Pillow].

[https://yadi.sk/d/AS6_eEzyb7aHH Задачи.]

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

====Бонусные задачи====
# Реализуйте масштабирование.
# Реализуйте отражение.
# Реализуйте размытие.
# Напишите свой фильтр для обработки изображений.

===Задание 3 (13.09 - 27.09)===
Решите 20 любых задач из [http://official.contest.yandex.ru/contest/642/ контеста Ввод-вывод].

====Бонусное задание. Шифрование RSA====
# Реализуйте [https://ru.wikipedia.org/wiki/RSA#.D0.90.D0.BB.D0.B3.D0.BE.D1.80.D0.B8.D1.82.D0.BC_.D1.81.D0.BE.D0.B7.D0.B4.D0.B0.D0.BD.D0.B8.D1.8F_.D0.BE.D1.82.D0.BA.D1.80.D1.8B.D1.82.D0.BE.D0.B3.D0.BE_.D0.B8_.D1.81.D0.B5.D0.BA.D1.80.D0.B5.D1.82.D0.BD.D0.BE.D0.B3.D0.BE_.D0.BA.D0.BB.D1.8E.D1.87.D0.B5.D0.B9 алгоритм создания открытого и секретного ключей].
# Реализуйте [https://ru.wikipedia.org/wiki/RSA#.D0.A8.D0.B8.D1.84.D1.80.D0.BE.D0.B2.D0.B0.D0.BD.D0.B8.D0.B5_.D0.B8_.D1.80.D0.B0.D1.81.D1.88.D0.B8.D1.84.D1.80.D0.BE.D0.B2.D0.B0.D0.BD.D0.B8.D0.B5 алгоритмы шифрования и дешифрования]. Проверьте, что они работают.
# Реализуйте алгоритм взлома. Функция должна принимать аргументы c, n и m (см. обозначения в Википедии) и возвращать d, приватный ключ, такое что m == c^d mod n.
# Научитесь замерять время выполнения каждой из четырёх функций (функции генерации ключей, шифрования, дешифрования и взлома).
# Выберите некоторое значение m, например, m=100. Выведите таблицу:
{|border="1"
!
!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)===
Если в вашей фамилии чётное число букв, то решите все чётные задачи из [http://official.contest.yandex.ru/contest/672/ контеста Обработка текста], иначе все нечётные.

===Домашнее задание 1 (26.09 - 6.10)===
[http://official.contest.yandex.ru/contest/689/enter/ Первое большое домашнее задание.] Каждому студенту требуется сделать пять задач из 20. Список обязательных задач [https://docs.google.com/spreadsheets/d/1LqW4k7heilZ8i1B7NCMGcr41kd5Pz1gIyD5rrOyGZjI/edit#gid=1902700687 здесь].

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

[http://official.contest.yandex.ru/contest/716/enter/ Копия домашней работы.] Если вы что-то решили/нашли ошибку после окончания срока сдачи домашней работы, вы можете отправить решения туда, чтобы проверить их. Эти результаты не будут учтены при оценке домашней работы.

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