- •Информатика.
- •Введение
- •Часть 1. Аппаратное и программное обеспечение вычислительных машин.
- •1.2. Представление информации в виде двоичного кода в памяти эвм.
- •1.3. Аппаратное обеспечение эвм.
- •1.3.1. Хранение данных в памяти эвм.
- •1.3.2. Память.
- •1.3.3. Процессор.
- •1.3.4. Шины и контроллеры.
- •1.3.5. Конструктивное исполнение.
- •1.3.6. Периферийные устройства.
- •1.4. Программное обеспечение эвм.
- •1.4.1. Классификация программного обеспечения.
- •1.4.2 Операционная система.
- •1.4.3. Компоненты операционной системы.
- •Часть 2. Основы программирования.
- •2.1. Алгоритмы.
- •2.1.1. Представление алгоритма.
- •2.1.2. Типовые структуры алгоритмов.
- •2.1.3. Типовые алгоритмы.
- •2.1.4. Эффективность и правильность алгоритмов.
- •2.2. Языки программирования.
- •2.2.1. История языков программирования.
- •2.2.2. Парадигмы программирования.
- •2.2.3. Основные понятия традиционного программирования.
- •2.3. Язык программирования высокого уровня – Паскаль.
- •2.3.1. Структура программы на Паскале.
- •Тело процедуры
- •Тело функции
- •2.3.2. Правила пунктуации.
- •2.3.3. Алфавит и словарь языка.
- •2.3.4. Константы и переменные, типы данных.
- •Пример 6. Запись типа zapic содержит три компонента: номер, фамилию и имя. Доступ к полям записи осуществляется через переменную spicok типа запись и массив tabl, состоящим из записей.
- •2.3.5. Выражения, операнды и операции.
- •2.3.6. Операторы языка Паскаль.
- •2.3.7. Процедуры ввода-вывода.
- •2.3.8. Работа с файлами.
- •2.3.9. Процедуры и функции.
- •Часть 3. Работа с прикладными программами и разработка программного обеспечения.
- •3.1. Текстовые редакторы.
- •3.1.1. Типы текстовых редакторов.
- •3.1.2. Текстовый процессор Word.
- •3.2. Электронные таблицы.
- •3.2.1. Табличный процессор Excel.
- •3.3. Разработка программного обеспечения.
- •3.4. Базы данных.
- •3.4.1. Структуры данных.
- •3.4.2. Структуры баз данных.
- •3.4.3. Модели баз данных.
- •3.4.4.Системы управления базами данных (субд).
- •3.4.5. Microsoft Access - субд реляционного типа.
- •1. Создание таблицы путем ввода данных.
- •2. Создание таблицы с помощью мастера.
- •3. Создание таблицы с помощью Конструктора таблиц.
- •Часть 4. Компьютерные сети. Защита информации.
- •4.1.Компьютерные сети.
- •4.2. Интернет.
- •4.2.1. Система адресов Интернета.
- •4.2.2. Электронная почта.
- •4.2.3. Гипертекстовые документы.
- •4.3. Защита информации.
- •Литература.
- •Содержание
- •Информатика. Основы программирования
2.1.3. Типовые алгоритмы.
Алгоритмы последовательного поиска, двоичного поиска, сортировки относятся к циклическим (итеративным) структурам.
Алгоритмы сортировки.
Для решения многих задач необходимо упорядочить исходные данные по определенному признаку. Алгоритмы сортировки отличаются друг от друга степенью эффективности, под которой понимается количество сравнений, произведенных в процессе выполнения алгоритма.
Сортировки методом простого выбора. Находят максимальный элемент в массиве из N элементов и меняют его местами с последним элементом (сортировка по возрастанию). Далее рассматривают массив без последнего элемента N-1. Общее количество сравнений пропорционально N2.
Сортировка методом поплавка. Рассматривается весь массив и максимальный элемент постепенно перемещается на последнее место. Затем рассматривают массив из N-1 элементов. Общее количество сравнений пропорционально N2.
Сортировка методом вставок. На i-м шаге считается, что первая часть массива, содержащая i-1 элемент, уже упорядочена. Далее берется i-й элемент, и для него подбирается j-е место в отсортированной части массива, такое, что упорядоченность не нарушается. i-й элемент помещается на это место, таким образом, что отсортированная часть массива увеличивается на один элемент. Общее количество сравнений пропорционально N2.
Алгоритмы поиска.
Алгоритм последовательного поиска последовательно рассматривает элементы списка в том порядке, в котором они расположены в списке. Стоит задача найти в списке заданное значение. Алгоритм эффективен, когда имеют дело с короткими списками. Если список упорядочен, то поиск продолжают до тех пор, пока в списке есть имена и искомое имя больше, чем рассматриваемое на данном шаге имя списка. Если список неупорядочен, просматривают весь список. Общее количество сравнений пропорционально количеству элементов в списке N.
Алгоритм двоичного поиска. Если массив упорядочен, то тогда можно использовать алгоритм бинарного (двоичного) поиска. По результату сравнения искомого значения со средним элементом массива из рассмотрения исключают первую или вторую половину списка, в зависимости от того больше или меньше «средний» (находящийся в середине списка) элемент искомого элемента. Для поиска в оставшейся части списка его тоже разбивают на две части и процедура повторяется. Таким образом, метод состоит в последовательном разделении рассматриваемого списка на сегменты до тех пор, пока не будет найден искомый элемент или поле поиска не сузится до пустого сегмента. Общее количество сравнений пропорционально log2N.
Алгоритм двоичного поиска реализуется с помощью рекурсивных структур. Цикл означает многократное выполнение набора команд. Рекурсия же предполагает повторное выполнение набора команд как подзадачу самой себя. При двоичном поиске для половины списка применяется та же процедура, что и для целого: список делится пополам и одна из частей отбрасывается.
Во время выполнения процедуры, включающей рекурсию, создается иллюзия существования множества копий этой процедуры, которые создаются активизацией процедуры. Эти активизации создаются способом, подобным выдвижению отдельных элементов телескопической антенны, и исчезают по мере выполнения алгоритма. В каждый момент времени работает только одна из существующих активизаций. Остальные находятся в состоянии неопределенности, ожидая завершения работы других активизаций процедуры.
Рекурсивные системы представляют собой циклические процессы и зависят от правильного управления ими. Их работа зависит от проверки условия завершения (для двоичного поиска – пустой список или найденное значение) и правильного их построения, которое обеспечивает выполнение этого условия завершения. [1, 10]