SEWiki - Вклад участника [ru]

Группа Михайлова

2013-05-22T11:19:36Z

2013-03-27T05:40:24Z

AM5800: /* Весенний семестр */

Группа Михайлова

2013-03-13T11:27:10Z

AM5800: /* Исключения */

Группа Михайлова

2013-03-13T11:25:26Z

AM5800: /* Исключения */

Группа Михайлова

2013-03-13T11:24:49Z

AM5800: /* Весенний семестр */

=Правила жизни=
За успешную сдачу практической работы на паре, на которой она была задана студент получает 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 необходимо обработать эти проблемы и не допустить утечки памяти.

2013-02-20T10:50:52Z

AM5800: /* Правила жизни */

Группа Михайлова

2013-02-20T10:50:18Z

AM5800:

=Правила жизни=
За успешную сдачу практической работы на паре, на которой она была задана студент получает 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]

=Осенний семестр=
==Компиляция==

Напишите псевдо код на основе ассемблерного кода в который разворачивается инструкция 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==
==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) раз больше числа "бакетов".

CPP 2013

2013-02-20T10:30:29Z

AM5800: /* Практические задания */

Лектор - Смаль Александр Владимирович

== Лекции ==

== Практические задания ==

[[Третья группа]]

[[Группа Михайлова]]

== Программа курса ==

== Список литературы ==

== Ссылки ==

Группа Михайлова

2013-02-13T18:34:55Z

2012-11-03T18:37:04Z

AM5800:

Группа Михайлова

2012-11-03T18:28:47Z

AM5800:

==Компиляция==

Напишите псевдо код на основе ассемблерного кода в который разворачивается инструкция 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==

Группа Михайлова

2012-11-03T18:28:09Z

AM5800: /* 6. String */

==1. Компиляция==

Напишите псевдо код на основе ассемблерного кода в который разворачивается инструкция 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

==2. Сортировка слиянием==
Реализуйте алгоритм merge sort

==3. Выделение памяти==
Создайте двумерный массив двумя способами.
1) Используя N + 1 аллокацию
2) Используя 2 аллокации
Замерьте, при каких значениях размера массива происходит экстерминатус? (Компилируйте 32 разрядную версию. 64 может и не упасть)
Какой вариант работает быстрее?
Подумайте, почему это происходит.
Обращаю внимание, что оба варианта созданных матриц должны иметь тип int**

Усложненное задание - сделать матрицы трегольными и написать процедуру, сливающие 2 такие матрицы в прямоугольную

==4. Расширяющийся массив==
Реализуйте класс расширяющегося массива.
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;
};
==5. Обертка над FILE==
==6. 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)

==7. Smart FILE==

Группа Михайлова

2012-11-03T18:27:25Z

AM5800: /* 6. String */

Группа Михайлова

2012-11-03T18:25:05Z

AM5800:

Группа Михайлова

2012-11-03T18:15:09Z

AM5800: /* 3. Выделение памяти */

2011-03-15T17:44:55Z

AM5800:

'''Михайлов Александр Владимирович'''

e-mail: [mailto:AM5800@gmail.com AM5800@gmail.com]

blog: [http://au-student.blogspot.com/ http://au-student.blogspot.com/]

[[Файл:Alexander_Mikhailov.png]]

Файл:Alexander Mikhailov.png

2011-03-15T17:37:07Z

AM5800:

Q&A

2011-03-10T19:17:45Z

AM5800:

Предлагаю на этой странице располагать вопросы, связанные с работой SEWiki, и ответы тех, кто может ответить.

'''Q:''' Где можно посмотреть список участников и ссылки на их страницы (кроме своей собственной)?

'''A:''' [http://mit.spbau.ru/sewiki/index.php/Служебная:ListUsers тут]

'''Q:''' А с какой целью у нас на главной странице ссылка на несуществующий раздел по алгоритмам?

'''A:''' Там кто-то хотел постить решения домашних задач. Но дальше создания пустого раздела дело, видимо, не пошло

Q&A

2011-03-10T19:16:19Z

AM5800: