Реализация алгоритмов сортировки данных средствами функционального программирования - Контрольная работа

АКАДЕМИЯ МАРКЕТИНГА И СОЦИАЛЬНО-ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ - ИМСИТ (г. КУРСОВАЯ РАБОТА по дисциплине "Функциональное и логическое программирование" на тему: "Реализация алгоритмов сортировки данных средствами функционального программирования" Цель работы состоит в приобретении навыков по работе с языком программирования F#, осознании его синтаксиса и особенностей, а так же применение языка F# в решении задач сортировки массивов данных различными способами . программирование хоар алгоритмВ декларативных языках, в отличие от императивных (процедурных или объектно-ориентированных), описывается не алгоритм решения задачи, а знания об объектах и процессах соответствующей предметной области. Языки Лисп и Пролог - родились как языки искусственного интеллекта, основанные на математической и логической моделях представления знаний, и были ориентированы именно на процессы принятия решений на основе знаний.Можно рассматривать F# как полноценное пришествие функционального программирования на платформу .NET (в смысле его индустриальной доступности), а можно и как еще один .NET-язык с множеством “причуд” и с непривычным, но очень компактным синтаксисом. Если же начать рассматривать F# с другой стороны, не вдаваясь в его функциональную сущность, то можно заметить, что это компактный язык, в котором есть в т.ч. автоматический вывод типов (нам почти никогда не приходится описывать типы данных для объектов) при статической типизации, в результате чего получается код, как на динамическом языке, но с проверкой типов и более эффективным порождаемым байт-кодом.В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. Итак, каждый алгоритм сортировки состоит из трех основных частей: Функция сравнения пары элементов сортируемого массиваВыбираем в массиве некоторый элемент, который будем называть опорным элементом. С точки зрения повышения эффективности алгоритма выбираться должна медиана, но без дополнительных сведений о сортируемых данных ее обычно невозможно получить. Известные стратегии: выбирать постоянно один и тот же элемент, например, средний или последний по положению; выбирать элемент со случайно выбранным индексом. Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы со значением меньшим или равным опорному элементу, оказались слева от него, а все элементы, превышающие по значению опорный - справа от него. Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r-й или l-й элемент соответственно, изменяется именно индекс опорного элемента и алгоритм продолжает свое выполнение.В качестве примера реализации указанного алгоритма был выбран язык Паскаль, так как он наиболее прост в понимании и более показателен в исполнении. procedure QSORT(var ar: array of real); procedure sort(var ar: array of real; low, high: integer); begin i:=low; j:=high; m:=ar[(i j) div 2]; // Взятие среднего опорного элемента repeat while ar[i]<m do Inc(i); // изменить порядок сортировки можно while ar[j]>m do Dec(j); // поменяв >< в этих двух строках if i<=j then begin wsp:=ar[i]; ar[i]:=ar[j]; ar[j]:=wsp; begin sort(ar, 0, High(ar));На функциональном языке программирования F# сортировка будет выглядеть значительно более компактно: let rec quicksort = functionВ процессе написания данной курсовой работы по предмету «Функциональное и логическое программирование» мной был более подробно изучен язык программирования F#.

Содержание

Введение

1. Обоснование выбора языка программирования

2. Изучение предметной области

3. Практическая реализация алгоритма сортировки данных

3.1 Быстрая сортировка (сортировка Хоара)

3.2 Реализация на процедурном языке программирования

3.3 Реализация на функциональном языке программирования

Заключение

Список использованных источников и литературы