1. Сравнение методов сортировки массивов

 

Написать функции для сортировки массивов следующими методами:

   1. метод выбора                                            int sort_select(double *arr, int arr_size, int *n_cmp, int *n_move);

   2. метод вставок                                            int sort_insert(double *arr, int arr_size, int *n_cmp, int *n_move);

   3. метод обмена (метод пузырька)         int sort_bubble(double *arr, int arr_size, int *n_cmp, int *n_move);

   4. быстрая сортировка ( рекурсивный алгоритм Хоaра)  int sort_qsort(double *arr, int arr_size, int *n_cmp, int *n_move);

 

В каждой функции сортировки производить подсчет количества сравнений и перемещений элеменов массива. Указатели на эти величины задаются параметрами функций сортировки n_cmp и n_move соответственно.

 

Выполнить сортировку массивов различной длины указанными четырьмя методами для следующих трех случаев:

   1. массив уже отсортирован в нужном порядке

   2. массив отсортирован в обратном порядке

   3. массив заполнен случайными числами

 

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

 

Литература

 

1. Н. Вирт, Алгоритмы и структуры данных, Москва, "Мир" 1989.

 

2. Д. Кнут, Искусство программирования. Том 3. Сортировка и поиск 2-е издание, Вильямс 2011.

 

 

 

2. Генетический алгоритм глобальной оптимизации

 

Написать программу для поиска глобального экстремума функции нескольких переменных f(x_1, ... , x_n) с помощью генетического алгоритма дифференциальной эволюции (differential evolution). В качестве примера рассмотреть поиск глобального минимума функции Розенброка f_R(x, y) = 100*(y - x*x)*(y - x*x) + (1 - x)*(1-x). Для значений силы мутации F и вероятности мутации R, можно взять F = 0.5 и R = 0.9. В качестве минимальной численности популяции можно использовать значение N = 10*D, где D - количество переменных, от которых зависит оптимизируемая функция.

 

Для каждого поколения программа должна выводить средние значения и дисперсии всех переменных, от которых зависит оптимизируемая функция.

 

 

Литература

 

1. Price, Kenneth, Storn, Rainer M., Lampinen, Jouni A.,  Differential Evolution. A Practical Approach to Global Optimization, Springer 2005.

 

2. В.В. Курейчик, Л. Гладков, В.М. Курейчик, Генетические алгоритмы, Физматлит 2006.

 

 

3. Построение координационных сфер для произвольной кристаллической решетки

 

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

 

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

 

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

 

- для ОЦК

   набор #1

    векторы трансляций a_1 = 1/2(1, 1, -1)   a_2 = 1/2(1, -1, 1)   a_3 = 1/2(-1, 1, 1)  

    один базисный атом с координатами (0, 0, 0)

  

   набор #2

    векторы трансляций a_1 = (1, 0, 0)   a_2 = (0, 1, 0)   a_3 = (0, 0 1)  

    два базисных атома с координатами (0, 0, 0) и 1/2(1, 1, 1)

 

- для ГЦК

   набор #1

    векторы трансляций a_1 = 1/2(1, 1, 0)   a_2 = 1/2(1, 0, 1)   a_3 = 1/2(0, 1, 1)  

    один базисный атом с координатами (0, 0, 0)

  

   набор #2

    векторы трансляций a_1 = (1, 0, 0)   a_2 = (0, 1, 0)   a_3 = (0, 0 1)  

    четыре базисных атома с координатами (0, 0, 0),  1/2(1, 1, 0), 1/2(1, 0, 1), 1/2(0, 1, 1).

 

Поскольку для обеих решеток каждый из двух наборов задает одни и те же множества атомов, то атомы для наборов #1 и #2 распределятся по координационным сферам одинаково.

 

Литература

 

Ч. Киттель, Введение в физику твердого тела, Москва, "Наука" 1978.

 

 

4. Сжатие данных по алгоритму LZ77

 

Написать программу для сжатия данных с помощью алгоритма LZ77. При запуске программа должна получать из командной строки следующие параметры: параметр определяющий действие - сжатие/восстановление, имя исходного файла, имя файла, куда записываются данные после сжатия/восстановления, размер dictionary, размер look ahead buffer.

 

При написании программы в целях экономии сил и времени допускается использовать следующие упрощения:

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

2. Первые N символов в сжимаемом файле, где N равно размеру dictionary, можно записать в сжатый файл без преобразований.

3. При возникновении такой ситуации, когда окно надо сдвинуть на K символов, а в сжимаемом файле осталоcь только L символов (L < K), допускается записать оставшиеся символы в сжатый файл без сжатия, так же как в том случае, когда нет совпадения между look ahead buffer и dictionary.

 

В качестве возможной оптимизации программы  попробуйте использовать для хранения смещения в dictionary и размера look ahead buffer двух байтов, биты которых поделены неравным образом между первым и вторым параметрами.

 

Литература

 

1. K. Loudon,  Mastering Algorithms with C, O'Reilly, 1999.

 

2. Д. Ватолин, В. Юкин, А. Ратушняк, М. Смирнов, Методы сжатия данных. Устройство архиваторов, сжатия изображения и видео, Диалог МИФИ, 2003.

 

 

5. Кодирование информации с открытым ключом по  методу RSA

 

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

 

Для арифметических операций с длинными числами, не представимыми с помощью стандартных типов языков программирования, использовать библиотеку  GMP  http://sourceforge.net/projects/mingw/files/MinGW/Base/gmp/gmp-5.1.2/

 

 

Литература

 

1 K. Loudon,  Mastering Algorithms with C, O'Reilly, 1999.

 

2.  С. Коутинхо, Введение в теорию чисел. Алгоритм RSA, Постмаркет, 2003.

 

 

Настройка CodeBlocks для работы с библиотекой GMP

 

Перейдя по указанной выше ссылке, необходимо скачать  два файла:  gmp-5.1.2-1-mingw32-dev.tar.lzma и

gmp-5.1.2-1-mingw32-dll.tar.lzma и сохранить их в какой-нибудь каталог, например, c:\GMP. Для распаковки данных файлов

понадобится архиватор 7-zip, который можно скачать по следующей ссылке: 7-zip.org. Установить этот архиватор можно

в папку c:\7-zip (имя папки будет запрошено при установке), для этого не требуются права администратора. После распаковки скачанных файлов появятся файлы с расширениями tar, эти файлы можно распаковать программой winrar, уже установленной на ваших комьютерах. В результате окончательной распаковки файлов в каталоге c:\gmp появятся каталоги bin, lib, include и другие.

 

Теперь надо подправить  некоторые параметры CodeBlocks.

1. Settings -> Compiler ->Linker Settings, добавляем сюда пути к двум библиотекам: c:\gmp\lib\libgmp.dll.a и c:\gmp\lib\libgmpxx.dll.a.

2. Settings -> Compiler ->Search Directories, сюда добавляем путь к заголовочным файлам: c:\gmp\include.

 

Теперь ваши программы, в которых используются GMP функции, будут компилироваться, но еще не будут запускаться. Для того чтобы программы запускались, необходимо добавить каталог, в котором находятся библиотеки времени выполнения (*.dll) в список каталогов, в которых происходит поиск команд и dll библиотек. Список таких каталогов задается переменной окружения PATH. Для этого в Windows выбираем Пуск -> компьютер -> свойства системы ->дополнтельные параметры системы -> переменные среды -> переменные среды для пользователя user1 -> создать переменную;

имя переменной PATH, значение переменной: %PATH%;c:\gmp\bin. После изменения значений переменных окружения необходимо перезапустить CodeBlocks.

 

Не забудьте использовать в ваших программах директиву препроцессора #include<gmp.h>.