|
|
| Строка 1: |
Строка 1: |
| − | =Правила жизни=
| |
| − | За успешную сдачу практической работы на паре, на которой она была задана студент получает 2 балла рейтинга.
| |
| − | За успешную сдачу на следующей паре - один балл.
| |
| − | На следующей паре первоначальное задание разбирается. И сдача такого задания оценивается уже в пол балла.
| |
| | | | |
| − | Проверка работ по электронной почте осуществляется только в экстренных случаях. (Болезнь, например).
| |
| − |
| |
| − | Для получения зачета необходимо набрать некоторе количествоо баллов. Точное значение будет определено позже.
| |
| − | Те, кто их не набрал - будут выполнять дополнительные задания.
| |
| − |
| |
| − | =Общее=
| |
| − | [https://docs.google.com/spreadsheet/ccc?key=0AhBJfSfjgJfGdEw1RlNXeWhlY1M0MGJacXQ1WXM0d2c&pli=1#gid=0 Результаты]
| |
| − |
| |
| − | =Интересные ссылки=
| |
| − | [http://pages.cs.wisc.edu/~driscoll/typename.html O typename]
| |
| − |
| |
| − | [http://habrahabr.ru/post/112953/ Об арифметике с плавающей запятой]
| |
| − |
| |
| − | [http://herbsutter.com/2013/01/01/video-you-dont-know-const-and-mutable/ You don't know const and mutable]
| |
| − |
| |
| − | [http://msdn.microsoft.com/en-us/library/e5ewb1h3(v=vs.80).aspx Memory leaks detection in Visual Studio]
| |
| − |
| |
| − | =Осенний семестр=
| |
| − | ==Компиляция==
| |
| − |
| |
| − | Напишите псевдо код на основе ассемблерного кода в который разворачивается инструкция for:
| |
| − | for (int i = 0; i < N; ++i) {
| |
| − | //body
| |
| − | }
| |
| − |
| |
| − | Пример псевдокода:
| |
| − | if (a == 5) goto mark1
| |
| − | something
| |
| − | mark1:
| |
| − | Чем плоха конструкция
| |
| − | #define MAX(a, b) a > b ? a : b
| |
| − | Приведите пример ее некорректного использования. (Возврат не максимального значения, побочные эффекты)
| |
| − | Как можно ее улучшить?
| |
| − |
| |
| − | Как работает линковка? Какую роль в ней играет relocation table
| |
| − |
| |
| − | ==Сортировка слиянием==
| |
| − | Реализуйте алгоритм merge sort
| |
| − |
| |
| − | ==Выделение памяти==
| |
| − | Создайте двумерный массив двумя способами.
| |
| − | 1) Используя N + 1 аллокацию
| |
| − | 2) Используя 2 аллокации
| |
| − | Замерьте, при каких значениях размера массива происходит экстерминатус? (Компилируйте 32 разрядную версию. 64 может и не упасть)
| |
| − | Какой вариант работает быстрее?
| |
| − | Подумайте, почему это происходит.
| |
| − | Обращаю внимание, что оба варианта созданных матриц должны иметь тип int**
| |
| − |
| |
| − | Усложненное задание - сделать матрицы трегольными и написать процедуру, сливающие 2 такие матрицы в прямоугольную
| |
| − |
| |
| − | ==Расширяющийся массив==
| |
| − | Реализуйте класс расширяющегося массива.
| |
| − | Size - количество элементов в массиве.
| |
| − | Capacity - вместимость массива.
| |
| − | Size <= Capacity
| |
| − | Если при добавлении очередного элемента Size превышает Capacity, то Capacity следует увеличить вдвое
| |
| − | struct Array {
| |
| − | Array(size_t capacity = 3);
| |
| − | Array(Array & array);
| |
| − | ~Array();
| |
| − | Array & operator=(Array & array);
| |
| − | size_t Size();
| |
| − | size_t Capacity();
| |
| − | void Add(int value);
| |
| − | int Get(size_t index);
| |
| − | void Set(size_t index, int value);
| |
| − | void Swap(Array & array);
| |
| − | private:
| |
| − | int* myData;
| |
| − | size_t mySize;
| |
| − | size_t myCapacity;
| |
| − | };
| |
| − | ==Обертка над FILE==
| |
| − | ==String==
| |
| − | Реализовать класс String со следующими методами/требованиями
| |
| − | String()
| |
| − | String(String &)
| |
| − | String(char *)
| |
| − | operator=(String &)
| |
| − | operator=(char *) //реализовывать не нужно. Объясните, почему?
| |
| − | append(String &)
| |
| − | char ? at(size_t) // реализовать в двух версиях. Константную и не константную
| |
| − | char * c_str() - возвращает обычную нуль-терминированную строку
| |
| − |
| |
| − | Данные хранить как буффер для строки и ее размер. Строку хранить НЕ как нуль-терминированную.
| |
| − | В приведенном выше ключевое слово const не используется умышленно.
| |
| − |
| |
| − | Дополнительное задание - реализовать строку с таким же интерфейсом, но реализующую стратегию Copy On Write (COW)
| |
| − |
| |
| − | ==Smart FILE==
| |
| − | ==Rational==
| |
| − | Напишите класс работающий с рациональными числами и определите следующие операторы:
| |
| − | * ostream <<
| |
| − | * istream >>
| |
| − | * +=
| |
| − | * -=
| |
| − | * *=
| |
| − | * /=
| |
| − | * +
| |
| − | * - бинарный
| |
| − | * - унарный
| |
| − | * *
| |
| − | * /
| |
| − | * ++ префиксный
| |
| − | * ++ постфиксный
| |
| − | * -- префиксный
| |
| − | * -- постфиксный
| |
| − | * ==
| |
| − | * !=
| |
| − | * <
| |
| − | * >
| |
| − | * <=
| |
| − | * >=
| |
| − |
| |
| − | ==Smart pointers==
| |
| − | Реализовать шаблонный scoped_ptr
| |
| − | [http://www.boost.org/doc/libs/1_52_0/libs/smart_ptr/scoped_ptr.htm]
| |
| − |
| |
| − |
| |
| − | =Весенний семестр=
| |
| − | ==Задание 1==
| |
| − | Реализовать алгоритм merge sort для сортировки произвольных контейнеров.
| |
| − | Специализировать алгоритм так, чтобы для некоторых контейнеров он работал эффективнее.
| |
| − | Например: list vs vector
| |
| − |
| |
| − | ==HashMap==
| |
| − | # HashMap<TKey, TValue, TTraits = SomeDefaultTraits<TKey>>, TKey - тип ключа, TValue - тип значения
| |
| − | # TTraits - некоторый тип, определяющий как именно будет вычисляться хеш-значение для ключа, а также сравнение с другими ключами. Реализация по-умолчанию должна уметь работать со всеми встроенными типами
| |
| − | # Для упрощения реализации количество ячеек в массиве можно считать константным
| |
| − | # Обязательные для реализации функции
| |
| − | ## begin()/end() - функции, возвращающие итераторы начала/конца таблицы. Тип итерируемых элементов - std::pair<TKey, TValue>
| |
| − | ## TValue & operator[](TKey) - оператор, возращающий значение по ключу. Если такого ключа в коллекции нет - он создается вместе со значением TValue по-умолчанию.
| |
| − | ## iterator lower_bound(TKey) - возвращает итератор на искомый элемент. Если такого нет - возвращает итератор, равный end()
| |
| − | ## iterator insert(std::pair<TKey, TValue>) - помещает пару ключ-значение в таблицу. Возвращает итератор на место, в которое элемент был вставлен. Если в таблице уже существует пара с таким же ключем - сгенерировать ошибку. Например, поделив на ноль =)
| |
| − | ## void remove(TKey) - угадайте с трех раз
| |
| − | # Дополнительно
| |
| − | ## Представляемая реализация должна работать с любыми примитивными типами "из коробки" т.е. без явного указания traits.
| |
| − | ## Помимо примитивных типов, реализовать поддержку std::string и любого своего поля, хеш для когорого считается из более чем двух полей.
| |
| − | ## Для вычисления хеша запрещается использовать готовые функции из std. (std::hash_value)
| |
| − | ## Протестировать как минимум на следующем коде:
| |
| − | HashMap<int, int> hm;
| |
| − | for (int i = 0; i < N; ++i) hm[i] = i;
| |
| − | for (int i = 0; i < N; ++i) if (i != hm[i]) std::cout << ...;
| |
| − | Где N в несколько (>=4) раз больше числа "бакетов".
| |
| − | ==Iterator==
| |
| − | Реализовать итератор, "ходящий" по строке, пропуская цифры.
| |
| − | В частности код:
| |
| − | std::string s = "aa44a";
| |
| − | std::copy(magic1, magic2, std::ostreambuf_iterator<char>(std::cout));
| |
| − | Должен вывести на экран "aaa". (magic1&2 - это собственно способ задания итератора. Он остается на ваше усмотрение)
| |
| − |
| |
| − | ==Algorithms==
| |
| − | Реализовать на выбор любые 2 алгоритма из списка
| |
| − | std::random_shuffle
| |
| − | std::rotate
| |
| − | std::reverse
| |
| − |
| |
| − | ==Указатели на функции==
| |
| − | Используя libexpat распарсить http://img.lenta.ru/r/EX/yandexfull.rss
| |
| − | Сгруппировать новости по категориям и вывести заголовки.
| |
| − |
| |
| − | Дополнительное задание (1 балл максимум):
| |
| − | Реализовать std::ptr_fun и std::bind
| |
| − |
| |
| − | ==Исключения==
| |
| − | Реализовать класс квадратной матрицы. Уделить особое внимание обработке исключений (bad_alloc, out of range)
| |
| − | Методы
| |
| − | # Конструктор от одного аргумента - размер матрицы
| |
| − | # copy ctor/operator=/dtor
| |
| − | # operator[] реализованный так, чтобы было возможно использовать его как m[9][10]
| |
| − | При возникновении каких-либо проблем при конструировании объекта Matrix необходимо обработать эти проблемы и не допустить утечки памяти.
| |
| − | Используйте ручное управление памятью (new/delete)
| |
| − | Память под матрицу выделять "построчно"
| |
| − |
| |
| − | ==Гарантии безопасности исключений==
| |
| − | Реализовать ini-парсер. Пример работы с таким классом
| |
| − | ini_parser parser("settings.ini");
| |
| − | std::string key1 = parser.get_string("General", "Key1");
| |
| − | int n = parser.get_int("General", "Key2"); // Если значение Key2 не может быть преобразовано к Int - сгенерировать исключение
| |
| − | parser.set_int("NewSection", "Key1", n);
| |
| − | parser.write("settings2.ini");
| |
| − |
| |
| − | ==RTTI==
| |
| − | Реализовать парадигму multiple dispatch
| |
| − | Asteroid ra1, ra2;
| |
| − | Spaceship rs1, rs2;
| |
| − | Object &a1 = ra1;
| |
| − | Object &a2 = ra2;
| |
| − | Object &s1 = rs1;
| |
| − | Object &s2 = rs2;
| |
| − | a1.CollideWith(a2);
| |
| − | a1.CollideWith(s1);
| |
| − | s1.CollideWith(s2);
| |
| − | s1.CollideWith(a1);
| |
| − | Доп. задание: реализовать то же самое тремя различными способами.
| |
| − |
| |
| − | ==C++11==
| |
| − | Реализовать вектор, используя (осмысленно) как можно больше новых механизмов C++11 (делегирующие конструкторы, список инициализации, foreach, move semantics, auto и прочие)
| |
