Практика ИВТ — 2017

Практика успешно окончена. Оценки в зачётные книжки можно будет поставить в сентябре. Неаттестованным студентам (у которых в поле «Допуск» указано «нет») нужно получить задание у старост.

Задание на практику

Обязательная часть:

• Заполнить дневник практики;
• Решить предложенные задачи по программированию на языке C++;
• Измерить быстродействие решения одной задачи (по варианту);
• Составить отчёт по практике.

Для аттестации по практике должны быть выполнены все пункты обязательной части (тем не менее, можно решить не все задачи: см. критерии оценки ниже).

Дополнительная часть:

• Провести тестирование корректности решения одной задачи (по варианту).

Заполнение дневника практики

Титульный лист

• Кафедра «Вычислительная техника»
• Дневник учебной практики
• Студент Иванов Иван Иванович (ваши фамилия, имя и отчество)
• Факультет ФИСТ курс 1
• Группа ИВТАПбд-11 или ИВТВМбд-11 (ваша группа)
• Специальность 09.03.01 Информатика и вычислительная техника (умещайте, можно в 2 строки)
• Ульяновск 2017 г.

Страница 2

• Приказ о назначении на практику №1177 (для ВМ) или 1178 (для АП) от «31» 05 2017 г.
• — вводный от УлГТУ ассистент Фолунин В. А. (оставить место для подписи) «19» 06 2017 г.
• — вводный на предприятии ассистент Фолунин В. А. (оставить место для подписи) «19» 06 2017 г.
• — на рабочем месте ассистент Фолунин В. А. (оставить место для подписи) «19» 06 2017 г.
• Студент Иванов Иван Иванович (ваши фамилия, имя и отчество)
• направлен на учебную практику в
• гор. Ульяновск на УлГТУ
• Срок практики с 19.06.17 по 02.07.17
• Руководитель практики от университета ассистент Фолунин Владимир Александрович
• Прибыл на предприятие "19" 06 2017 г.
• Убыл из предприятия "02" 07 2017 г.

Страница 4

• 19.06.2017 | Инструктаж, УлГТУ
• 20.06.2017 | Решение задач, vtcloud9.ulstu.ru
• 26.06.2017 | Анализ быстродействия решений, vtcloud9.ulstu.ru
• 30.06.2017 | Подготовка отчёта, УлГТУ

Страница 5

• 1) Разработка решений учебных задач по программированию на языке C++
• 2) Проверка корректности решений при помощи автоматизированной тестирующей системы
• 3) Экспериментальное исследование быстродействия решения задачи
• (если вы делаете дополнительную часть) 4) Разработка тестов для анализа корректности решения задачи

Страница 7

• (внизу, под словом Руководитель) 02.07.2017 г.

Страница 8

• (внизу, после места для подписи) 02.07.2017 г.

Решение задач

Дневник успеваемости

Откройте сайт тестирующей системы. Слева выберите своё имя из выпадающего списка и введите пароль, выданный преподавателем.

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

В нижней части страницы задачи находится форма отправки решений. В эту форму следует скопировать весь исходный код программы, после чего выбрать компилятор C++ и нажать кнопку «Отправить». Решение будет проверено на большом наборе тестов, результат будет показан сразу после проверки. Программа должна выдавать корректные результаты на всех тестах.

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

Настоятельно рекомендуется прочитать руководство для начинающих перед началом работы.

Измерение быстродействия решений

Пример выполнения

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

Допустим, что было составлено и сдано следующее решение (хотя оно далеко не единственное и не самое эффективное из возможных):

#include <stdio.h>
#include <vector>
using namespace std;

vector<int> readArray() {
    int aSize;
    scanf("%d", &aSize);
    vector<int> a(aSize);
    for (int i = 0; i < aSize; i++)
        scanf("%d", &a[i]);
    return a;
}

int lisLength(vector<int> &a) {
    vector<int> length(a.size());
    int maxLength = 0;
    for (int i = 0; i < a.size(); i++) {
        length[i] = 1;
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i] && length[i] < length[j] + 1)
                length[i] = length[j] + 1;
        }
        if (maxLength < length[i])
            maxLength = length[i];
    }
    return maxLength;
}

int main() {
    vector<int> a = readArray();
    printf("%d", lisLength(a));
}

Чтобы проанализировать эффективность программы, необходимо сделать несколько измерений времени её работы, увеличивая размер обрабатываемых входных данных.

Для тестирования прежде всего понадобится генератор случайных входных данных заданного размера. Для рассматриваемой задачи входными данными является целочисленный массив:

#include <stdlib.h> int random(int l, int r) { return l + rand() % (r - l + 1); }

#include <random> //более надёжная современная версия int random(int l, int r) { static minstd_rand generator; return l + generator() % (r - l + 1); }

vector<int> generateArray(int size) {
    vector<int> a(size);
    for (int i = 0; i < size; i++)
        a[i] = random(-100, 100);
    return a;
}

Теперь можно составить функцию, измеряющую время работы (обратите внимание, что заголовочный файл <chrono> появился только в стандарте C++11 — вам понадобится относительно современная версия компилятора):

#include <chrono>
using namespace std::chrono;

double singleTimeTest(int size) {
    vector<int> a = generateArray(size);
    high_resolution_clock::time_point startTime = high_resolution_clock::now();
    lisLength(a);
    high_resolution_clock::time_point finishTime = high_resolution_clock::now();
    duration<double> elapsedTime = duration_cast< duration<double> >(finishTime - startTime);
    return elapsedTime.count();
}

Чтобы исключить влияние вырожденных входных данных на результаты измерений, составим функцию, запускающую тест множество раз и возвращающую среднее время выполнения:

double multipleTimeTests(int size, int testsCount) {
    double totalTime = 0;
    for (int i = 0; i < testsCount; i++)
        totalTime += singleTimeTest(size);
    return totalTime / testsCount;
}

Теперь можно составить функцию, выводящую результаты тестирования:

void timeTestingTable() {
    printf("N\tT(N)\n");
    for (int n = 16; n <= 8192; n *= 2)
        printf("%d\t%.2lf\n", n, multipleTimeTests(n, 100));
}

Полный код рассматриваемого примера

Обратите внимание: если в вашем варианте задача не предусматривает работу с массивами, и быстродействие зависит от одного параметра, то вы можете выбрать одну из следующих возможностей:

• отказаться от функции multipleTimeTests() и вместо этого вызывать из цикла в timeTestingTable() функцию singleTimeTest() (т. к. нет смысла многократно вычислять одно и то же);
• при заданном size генерировать некоторое случайное число, близкое к size, и уже это число передавать в качестве параметра тестируемой функции (чтобы она при повторных вызовах не повторяла одни и те же действия).

Интерпретация результатов

Пусть после вызова функции timeTestingTable() получился следующий вывод (запускать программу следует в конфигурации Release):

N	T(N)
16	0.000001
32	0.000004
64	0.000015
128	0.000051
256	0.000168
512	0.000667
1024	0.002793
2048	0.011155
4096	0.044568
8192	0.177109

Отметим показанные точки на графике при помощи Excel (не забывайте подписывать оси!). Также можно использовать WolframAlpha

В данном случае видно, что с увеличением размера входных данных в 2 раза время работы программы возрастает примерно в 4 раза. Это позволяет сделать предположение о том, что время работы пропорционально квадрату размера входных данных (T(N) ~ N²).

Добавим на график соответствующую линию тренда (тип — полиномиальная степени 2, показывать уравнение на графике). Вновь можно использовать WolframAlpha.

Если в вашем варианте зависимость имеет другой вид (логарифмическая, линейная, кубическая и т. д.), то и линия тренда должна быть соответствующего типа.

Видно, что линия действительно хорошо приближает полученные результаты:

Составим таблицу оценки погрешностей, чтобы обосновать адекватность приближения:

N	Tэксп(N)	Tтеор(N)	Δ	δ
16	0.000001	-0.000028	0.000029	28.632000
32	0.000004	-0.000024	0.000028	6.932000
64	0.000015	-0.000011	0.000026	1.754133
128	0.000051	0.000032	0.000019	0.373490
256	0.000168	0.000192	0.000024	0.144095
512	0.000667	0.000808	0.000141	0.210843
1024	0.002793	0.003218	0.000425	0.152212
2048	0.011155	0.012758	0.001603	0.143677
4096	0.044568	0.050711	0.006143	0.137840
8192	0.177109	0.202116	0.025007	0.141194

Продолжите таблицу для бóльших N, если ваша программа позволяет получить результаты за приемлемое время.

T_теор(N) вычисляется путём подстановки N в уравнение линии тренда.

Δ — абсолютная погрешность, вычисляется как |T_эксп(N) - T_теор(N)|.

δ — относительная погрешность, вычисляется как Δ / T_эксп(N). Ожидается, что относительная погрешность окажется достаточно малой (для больших N).

Важно: в вашем варианте может оказаться другая закономерность:

• T(N) ~ 1 (точки принадлежат горизонтальной прямой)
• T(N) ~ logN
• T(N) ~ √N (стройте линию тренда для T²(N))
• T(N) ~ N
• T(N) ~ NlogN (стройте линию тренда для T(N) / logN)
• T(N) ~ N³

Варианты

Студент	Студент	Задача
Абулханов	Мартынов	3C
Аввакумова	Маслов	3D
Аглиуллин	Миронов	3E
Андреев	Мостафа	3F
Артюхин	Мубинов	3G
Беляков	Николенко	3H
Богатырёва	Ометов	3I
Былинин	Пахомов	3J
Верховцев	Пономарев	4D
Вершинин	Поташова	4E
Гаврилов	Решетникова	4F
Герасимов	Руссков	4G
Глебов	Савельев	5A
Гнусарев	Семин	5B
Громкова	Скрипин	5C
Закамсков	Танченко	5E
Зубарева	Танькин	5F
Казаков	Тырыкин	5G
Караков	Тюгашев	5H
Колесников	Чукмарёв	5I
Кондратьев	Шиленков	6C
Круглов	Юнусов	6D

Преподавателю нужно продемонстрировать:

• текст задания;
• код тестирования;
• 2 графика;
• таблицу погрешностей.

Для получения баллов предварительный (электронный) вариант главы отчёта нужно отправить преподавателю по почте или показать на консультации.

Тестирование корректности решений

Пример выполнения

Предположим, что тестирование проводится для задачи 6F. C++ и Java, и имеется следующее её решение:

#include <iostream>
#include <string>
#include <cctype>
using namespace std;

string transformStyle(const string &name) {
    //...
}

int main() {
    string name;
    cin >> name;
    cout << transformStyle(name);
}

Для создания тестов будем использовать библиотеку Catch. Несмотря на то, что такой подход мало распространён, для простоты мы будем создавать тесты в том же проекте, что и решение.

Скачайте заголовочный файл с библиотекой, поместите его в папку с кодом проекта и добавьте в начало программы следующие строки:

#define CATCH_CONFIG_RUNNER
#include "catch.hpp"

Теперь добавим тесты. Каждый тест создаётся при помощи макроса TEST_CASE и может содержать несколько проверок. Например, мы создадим следующие группы тестов:

• пример из условия;
• строки в стиле C++;
• строки в стиле Java;
• строки в общем стиле;
• строки из 1 символа;
• строки из 100 символов.

TEST_CASE("Sample tests") { 
    REQUIRE(transformStyle("selection_sort") == "selectionSort");
    REQUIRE(transformStyle("keyValuePair") == "key_value_pair");
}

TEST_CASE("C++ tests") {
    REQUIRE(transformStyle("a_b_c") == "aBC");
    REQUIRE(transformStyle("aaa_bbb_ccc") == "aaaBbbCcc");
    REQUIRE(transformStyle("a_bb_c") == "aBbC");
}

TEST_CASE("Java tests") {
    REQUIRE(transformStyle("aBCD") == "a_b_c_d");
    REQUIRE(transformStyle("aaBbbCccDdd") == "aa_bbb_ccc_ddd");
    REQUIRE(transformStyle("aB") == "a_b");
}

TEST_CASE("Small letters tests") {
    REQUIRE(transformStyle("abcd") == "abcd");
    REQUIRE(transformStyle("x") == "x");
    REQUIRE(transformStyle("zzzzzzzzzzzz") == "zzzzzzzzzzzz");
}

TEST_CASE("One letter tests") {
    REQUIRE(transformStyle("a") == "a");
    REQUIRE(transformStyle("z") == "z");
}

TEST_CASE("Max tests") {
    REQUIRE(transformStyle("a_b_c_d_e_a_b_c_d_e_a_b_c_d_e_a_b_c_d_e_a_b_c_d_e_a_b_c_d_e_a_b_c_d_e_a_b_c_d_e_a_b_c_d_e_a_b_c_d_ef") == "aBCDEABCDEABCDEABCDEABCDEABCDEABCDEABCDEABCDEABCDEf");
    REQUIRE(transformStyle("aBCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ") == "a_b_c_d_e_f_g_h_i_j_a_b_c_d_e_f_g_h_i_j_a_b_c_d_e_f_g_h_i_j_a_b_c_d_e_f_g_h_i_j_a_b_c_d_e_f_g_h_i_j_a_b_c_d_e_f_g_h_i_j_a_b_c_d_e_f_g_h_i_j_a_b_c_d_e_f_g_h_i_j_a_b_c_d_e_f_g_h_i_j_a_b_c_d_e_f_g_h_i_j");
    REQUIRE(transformStyle("abcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghij") == "abcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghij");
}

Чтобы запустить тесты, замените код main() на следующий:

int main() {
    Catch::Session().run();
}

Если решение корректно, будет выведено сообщение:

All tests passed (16 assertions in 6 test cases)

Варианты

Выберите интересную задачу самостоятельно. Для проверки подойдёт любая задача, кроме самых простых. Будет особенно здорово, если вы при помощи тестов найдёте ошибку в незачтённом решении, исправите его и сдадите.

Преподавателю нужно продемонстрировать:

• текст задания;
• код тестирования;
• результаты тестирования.

Отчёт по практике

Экономим бумагу.

20 баллов выставляются автоматически, как только вы покажете результаты измерения быстродействия.

Критерии оценки

• Заполнение дневника — 20 баллов;
• Составление отчёта — 20 баллов;
• Решение задачи — 2 балла за каждую задачу;
• Отсутствие ошибок форматирования в решении — +1 балл за каждую задачу (эта часть будет проверяться дотошно — два пробела не на своём месте, и балл не добавляется);
• Наличие глобальных переменных в решении — -1 балл за каждую задачу;
• Плагиат — -15 баллов за каждую задачу (и у того, кто заимствовал решение, и у того, кто одолжил решение);
• Измерение быстродействия решения — 25 баллов;
• Тестирование корректности решения — 25 баллов.

100 баллов — оценка «Удовлетворительно»

160 баллов — оценка «Хорошо»

230 баллов — оценка «Отлично»

Дневник успеваемости