Файл: Алгоритмизация как обязательный этап разработки программы (Преобразование Фурье).pdf

Введение

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

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

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

Алгоритм должен обладать тремя важными характеристиками, чтобы иметь право так называться:

Он должен работать за конечное количество времени. Если ваш алгоритм не может разобраться с проблемой, для которой он был создан, за конечное количество времени, то он бесполезен.

Он должен иметь чётко определённые инструкции. Каждый шаг алгоритма должен быть точно определён. Инструкции должны быть однозначны для каждого случая.

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

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

Алгоритмизация

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

Алгоритм решения задачи имеет ряд обязательных свойств:

— дискретность — разбиение процесса обработки информации на более простые этапы (шаги выполнения), выполнение которых компьютером или человеком не вызывает затруднений;

— определенность алгоритма — однозначность выполнения каждого отдельного шага преобразования информации;

— выполнимость — конечность действий алгоритма решения задач, позволяющая получить желаемый результат при допустимых исходных данных за конечное число шагов;

— массовость — пригодность алгоритма для решения определенного класса задач.

---

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

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

Из известных основных способов представления алгоритмов:

словесный;

структурно-стилизованный (псевдокод);

графический;

программный.

Графическая форма, в виде блок-схем наиболее удобна. Блок-схемой называется графическое изображение структуры алгоритма, в которой каждый этап процесса обработки данных представляется в виде графических символов (блоков)- геометрических фигур, в контуры которых вписано содержание операции. Фигура, представленная в виде блочного символа (блока) называется символом действия.

Алгоритмизация, как процесс преобразования исходной информации к алгоритмическому виду, включает в себя:

выделение актуальных (задействованных в операциях) объектов;

идентификация выделенных объектов;

выделение операций, понятных исполнителю и не допускающих неоднозначных интерпретаций;

указание порядка выполнения операций.

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

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

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

Смешанный порядок в алгоритме предполагает наличие участков с неодинаковым типом последовательностей операций. Смешанный порядок выполнения операций всегда присутствует в сложных алгоритмах и программах. Даже в "примере с задвижками" часто приходится менять порядок действий в зависимости от складывающейся походу дела ситуации и обстановки. Например, менять порядок открытия задвижек из-за неисправности одной из них (ветвление) или повторно включать подремонтированный насос, повторяя порядок открытия-закрытия задвижек (цикл), и т.п.

---

Программирование

Программирование (programming) — теоретическая и практическая деятельность, связанная с созданием программ.

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

Язык программирования — формальная знаковая система, предназначенная для описания алгоритмов в форме, которая удобна для исполнителя (например, компьютера). Язык программирования определяет набор лексических, синтаксических и семантических правил, используемых при составлении компьютерной программы. Он позволяет программисту точно определить то, на какие события будет реагировать компьютер, как будут храниться и передаваться данные, а также какие именно действия следует выполнять над этими данными при различных обстоятельствах.

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

Эти спецификации обычно включают в себя описание:

Типов и структур данных;

Операционную семантику (алгоритм вычисления конструкций языка);

Семантические конструкции языка;

Библиотеки примитивов (например, инструкции ввода-вывода);

Философии, назначения и возможностей языка.

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

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

1. АЛГОРИТМЫ СОРТИРОВКИ

---

Алгоритм сортировки — это алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле по которому производится сортировка, называется ключом сортировки. На практике, в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма.

Для оценки алгоритмов рассмотрим параметры, по которым мы будем оценивать алгоритмы:

Время сортировки — основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для сортировки важны худшее, среднее и лучшее поведения алгоритма в терминах размера списка (n). Для типичного алгоритма хорошее поведение — это O(n log n) и плохое поведение — это Ω(n²). Идеальное поведение для сортировки — O(n). Алгоритмы сортировки, которые используют только абстрактную операцию сравнения ключей, всегда нуждаются, по меньшей мере, в Ω(n log n) сравнениях в среднем;

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

Устойчивость — устойчивая сортировка не меняет взаимного расположения равных элементов. Такое свойство может быть очень полезным, если они состоят из нескольких полей, а сортировка происходит по одному из них.

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

Ещё одним важным свойством алгоритма является его сфера применения. Здесь основных типов сортировки два:

1. Внутренняя сортировка оперирует с массивами, целиком помещающимися в оперативной памяти с произвольным доступом к любой ячейке. Данные обычно сортируются на том же месте, без дополнительных затрат.
2. Внешняя сортировка оперирует с запоминающими устройствами большого объёма, но с доступом не произвольным, а последовательным (сортировка файлов), т.е. в данный момент мы «видим» только один элемент, а затраты на перемотку по сравнению с памятью неоправданно велики. Это накладывает некоторые дополнительные ограничения на алгоритм и приводит к специальным методам сортировки, обычно использующим дополнительное дисковое пространство. Кроме того, доступ к данным на носителе производится намного медленнее, чем операции с оперативной памятью. Доступ к носителю осуществляется последовательным образом: в каждый момент времени можно считать или записать только элемент, следующий за текущим. Объём данных не позволяет им разместиться в ОЗУ.

---

Пузырьковая сортировка.

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

Например, у нас есть массив целых чисел:

3

7

4

4

6

5

8

При первом проходе по массиву мы сравниваем значения 3 и 7. Поскольку 7 больше 3, мы оставляем их как есть. После чего сравниваем 7 и 4. 4 меньше 7, поэтому мы меняем их местами, перемещая семерку на одну позицию ближе к концу массива. Теперь он выглядит так:

3

4

7

4

6

5

8

Этот процесс повторяется до тех пор, пока семерка не дойдет почти до конца массива. В конце она сравнивается с элементом 8, которое больше, а значит, обмена не происходит. После того, как мы обошли массив один раз, он выглядит так:

3

4

4

6

5

7

8

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

И снова был произведен как минимум один обмен, а значит, проходим по массиву еще раз.

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

3

4

4

5

6

7

8

Пример пузырьковой сортировки:

1 public void Sort(T[] items) 2 { 3 bool swapped; 4 5 do 6 { 7 swapped = false; 8 for (int i = 1; i < items.Length; i++) { 9 if (items[i - 1].CompareTo(items[i]) > 0) 10 { 11 Swap(items, i - 1, i); 12 swapped = true; 13 } 14 } 15 } while (swapped != false); 16}

Сортировка вставками.

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

---