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

Структура Данных (СД) в ЭВМ представляется в виде последовательных двоичных данных (множество связей между ними)

Простые СД – базовые, примитивные, не могут быть расчленены на составные части.

Интегрированные СД – частями к-ых являются другие СД.

СД – связные и несвязные (от наличия или отсутствия связей данных)

Изменчивость – изменение числа элементов (связей).

Простые (базовые): числовые, символьные, логические, перечисление, интервал, указатели.

Статистические: вектор, массивы, множество, записи, таблицы.

Полустатические: стек, очередь, деки, строки.

Динамические: линейные связные списки, разветвленные связные списки, графы, деревья.

Рекомендуемые материалы

Между элементами структуры не отражен факт изменения значения данных.

Вектор (одномерный массив) – СД с фиксированных числом элементов одного и того же типа.

Массив – последовательность элементов одного типа называется базовым.

Множество – набор неповторяющихся данных одного и того же типа.

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

Таблица – последовательные записи, к-ые имеют одну и ту же организацию.

Списки – упорядоченное множество, состоящее из переменного числа элементов, к к-ым применимы операции включение и выключение.

Список, отражающий отношения соседства между элементами называется линейным.

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

 Связный список: 1. линейный (односвязные, двусвязные – (не)циклические).

2. нелинейный (двусвязные, многосвязные).

В зависимости от характера взаимного расположения СД: 1.с последовательным распределением элементов (векторы, строки, массивы, стеки, очереди), 2.с произвольным связным распределением элементов в памяти (связные и двусвязные списки).

СД в оперативной памяти: полуслово, слово, двойное слово, схема хранения (прямоугольные, связные)

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

Одно слово 8 бит – 1 байт.

Информация по каждому типу данных определяет:

1. Структуру хранения данных указанного типа, т.е. выделения памяти и представления данных с одной стороны, а с другой – интерпретированного двоичного представления.
2. Множество допустимых значений, к-ое может иметь тот или иной объект описанного типа.
3. Множество допустимых операций, к-ые применимы к объектам описанного типа.

Типы данных: integer – целое короткое 4 байта, smallint – 2 байта, longint – целое нормальное, single – действительное нормальное 8 байт, boo-lean – логическое, char – символьное 1 байт, array – массив, record – запись.

Тип данных определяет, каким образом биты данных, представляющие конкретное значение, хранятся в памяти ПК. В каждом языке программирования имеется свой фиксированный набор базовых типов данных. Некоторые языки позволяют создание дополнительных (пользовательских) типов данных. В VBA имеются следующие типы данных:

Поясним некоторые характерные для VBA типы данных.

Byte - Массивы данного типа служит для хранения двоичных данных, например, изображений. Использование данного типа предохраняет двоичные данные во время преобразования формата.

Boolean - для хранения логических (булевых) значений. По умолчанию значением булевской переменной является False- ложь.

Currency - для хранения чисел с дробной частью до четырех цифр и целой частью до 15 цифр, то есть данных с фиксированной десятичной точкой, удобных для денежных вычислений. Числа с плавающей десятичной точкой (Single, Double) имеют больший диапазон значений, но могут приводить к ошибкам округления.

Decimal - в версии 5.0 поддерживается использование типа данных Decimal только в пределах типа Variant, т.е. невозможно описать переменную с типом Decimal. Пользователь, однако, имеет возможность создать переменную типа Variant с подтипом Decimal с помощью функции CDec.

Object - поскольку VBA является объектно-ориентированным языком, в нем можно манипулировать различными объектами, адреса расположения которых в памяти (указатели) имеют этот тип.

String - по умолчанию данные строкового типа имеют переменную длину и могут удлиняться или укорачиваться. Однако такие строки занимают на 10байт памяти больше, поэтому можно объявить строки фиксированной длины, чвно указав количество символов. Если количество символов будет меньше объявленного, то свободные места заполняются пробелами, при попытке занесения большего количества символов лишние отбрасываются.

Variant - может быть использован для хранения данных всех базовых типов без выполнения преобразования (приведения) типов. Применение данного типа позволяет выполнять операции, не обращая внимание на тип данных, которые они содержат. Удобен для объявления переменных, тип которых заранее неизвестен. Переменные этого типа могут содержать специальные значения: Empty, Null, Error.

Над всеми СД могут выполняться 4 операции: 1.создание (выделение памяти ), 2. уничтожение (противоположно созданию), 3. выбор/доступ ( используется программой внутри самой структуры), 3. обновление (позволяет изменить значение данных с СД).

Метод доступа – св-во СД имеет отношение к выбору конкретной СД.

Линейные СД – структуры, в к-ых связи между элементами не зависят от какого-либо условия (матрицы, множества, векторы).

Линейные СД: прямоугольные (партезианские), строчные (типа ряда), списковые.

Строчные структуры – одномерные динамические изменения СД, отмеченные способами включения и исключения элементов.

Строчные: стек (последовательное включение и исключение элементов осуществляется с 1 стороны последовательности), очередь (последовательность, в к-ую включают с одной стороны, а исключают с другой), дек (последовательность, в к-ой включать и исключать элементы могут с 2х концов последовательности).

В списковых структурах логический порядок данных определяется указателями.

Списковая структура представляет собой набор элементов, каждый их к-ых состоит из 2х полей, в 1ом размещен элемент данных или указатель на него, а в другом – указатель на следующий элемент списка.

Нелинейные СД – СД, у к-ых связи между элементами зависят от определенных условий (деревья, древовидные, графы, многосвязные списки, сплетения/плексы).

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

Дерево – совокупность элементов, называемых узлами, 1 из к-ых определяется как корень, и отношений, образующих иерархическую структуру узлов.

Вершины, из к-ых не выходит ни 1 ребро называется листьями. 

Дерево, из каждой вершины к-ого выходит только 2 ребра называется бинарным.

Графи – совокупность 2х множеств вершин и ребер.

Граф – сложная нелинейная  многосвязная структура, к-ая отображает св-ва и связи сложного объекта.

Св-ва: на каждый элемент (узел или вершину) может быть произвольное кол-во ссылок. Каждый элемент может иметь связь с любым другим кол-вом элементов. Каждая связка ребер, дуг может иметь направление и вес.

Типичным графом является метро.

Выбранные точки называются вершинами, а линии дугами.

Сплетения = плексы – нелинейные СД, объединяющие такие понятия как деревья, графы, списковые структуры.

Св-во: наличие у каждого элемента сплетения несколько полей с указателями на другой элемент того же сплетения.

Сплетение – связь элементов, основанная на сплетении указателей.

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

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

Модель – упрощенное представление о реальном объекте, процессе или явлении.

Моделирование – построение модели для исследования и изучения объектов, процессов или явлений.

Можно моделировать то, что уже есть или чего еще нет.

Типы моделирования:

Классификация по области использования:

1. учебные (наглядные пособия, тренажеры, обучающие программы)
2. научно-технические (создаются для исследования процессов или явлений)
3. игровые (военные, эк., деловые игры)
4. имитационные (отражают реальность и имитируют ее)

эксперимент, многократно повторяются или проводятся одновременно с другим экспериментом.

Классификация с учетом фактора времени:

1. статические (одномоментный срез информации по объекту)
2. динамические (позволяет увидеть изменение объекта во времени)

Классификация по способу представления:
Материальные модели – можно назвать предметными или физическими, воспроизводят физические и геометрические св-ва оригинала и всегда имеют материальное воплощение.

Информационные модели (знаковые, вербальные) – совокупность информации, к-ая характеризует св-во и состояние объекта, процесса, явления, а также взаимосвязь с внешним миром.

Вербальные модели – информация в мысленной и разговорной форме (идеи, рифма).

Знаковые модели ((не)компьютерные) – информационная модель, выраженная специальными знаками, т.е. средствами формального языка (рисунки, тексты, схемы).

Классификация по способу представления:

1. геометрические (геом. конструкции)
2. словесные (устные писания)
3. математические (взаимосвязь параметров объектов)
4. структурные (схемы, графики, таблицы)
5. логические (варианты выбора действий представлены на основе анализа, умозаключения)
6. специальные (химические формулы, ноты)
   Этапы моделирования:
   1. постановка задач (описание задач, осмысленные, направленные цели, анализ объекта моделирования)

2. разработка модели (св-ва, состояние, действия, другие св-ва объекта) Сложность модели обусловлена целью моделирования.

       3. компьютерный эксперимент (тестирование, проверка правильности модели)

       4. анализ результатов

       5. принятие решений на основе предыдущих этапов.

  если 3 и 4 не совпадают, то его моделируют заново.

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

Св-ва алгоритмов:
1.    конечность = финитость (алгоритм должен приводить к результату задачи за конечное время)

1. определенность = детерменированность ( неоднозначность записи алгоритма недопустима, только однозначность)

1. дискретность (сам алгоритм может быть разбит на элементарные действия), понятность
2. результативность (доступность результата решения пользователю – возможность просматривать результат)
3. массовость (алгоритм может быть применен для других исходных данных)
4. эффективность/качество (должен сделаться за приемлемое для разработчика время)

Виды алгоритмов. В зависимости от цели, начальных условий, пунктов их решений, определенных действий разработчика: 1. Механические=детерменированные=жесткие – задает определенные действия, объединяет их в единую последовательность, к-ая ведет к результату. 2. Стахостические=вероятностные=гибкие – нарушение последовательности действий, результат решения задач достигается несколькими способами (эвристический), конечный результат и последовательность действий не определена, большую роль играет интуиция разработчика.

Линейный алгоритм – набор команд, выполняемых последовательно во времени, друг за другом.

Разветвляющийся алгоритм – содержит хотя бы 1 проверку  условия, в результате к-ой обеспечивается переход на один из возможных вариантов решения.

Признаком разветвляющегося алгоритма является блок проверки условия. Различают два вида условий: простые и составные. Простым условием (отношением) называется выражение составленное из двух арифметических или текстовых величин, связанных одним из знаков: <, >, <=, >=, <>. Например: x+y<7; “ma”<>”pa”. Блок проверки условия изображается ромбом, внутри которого указывается проверяемое условие, имеет один вход и два выхода: ДА, НЕТ. Если условие истинно (выполняется), то то выходим из блока по вывходу ДА, если ложно (не выполняется), то по выходу НЕТ.

Циклический алгоритм – это алгоритм, предусматривающий многократное повторение одного и того же действия над новыми данными.

Цикл называется арифметическим, если число повторений цикла известно заранее или может быть вычислено.

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

Вспомогательный алгоритм (подчиненный) – раннее разработанный и целиком исполняемый при реализации, решении конкретных задач.

Средства изображения алгоритма: словесный, формально-словесный, блок-схемы, псевдокоды, структурные диаграммы, языки программирования.

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

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

Блок-схемы: графическое изображение алгоритма, в к-ой каждый этап процесса обработка данных представлен в виде геометрических фигур. При изображении алгоритмов, геометрические фигуры должны соответствовать гост 19.701-90 (ИСО 5807-85).

Псевдокод – совокупность операторов языка программирования и обычного языка.

Структурная диаграмма: используется в качестве структурных блок-схем для показа СД и систем обработки данных.

Транслятор (переводчик) – программа-переводчик, к-ая преобразует программу написанную на одном из языков высокого уровня в программу, состоящую из машинных кодов.

Транслятор представляется в виде компиляторов и интерпретаторов.

Компилятор (составитель, собиратель) – читает всю программу целиком, делает ее перевод и создает законченный вариант на машинном языке, к-ый потом выполняется.

Интерпретатор (истолкователь) – переводит и выполняет программу строка за строкой.

Откомпилированные программы работают быстрее, но интерпретированные проще изменить и исправить.

Каждый конкретный язык ориентирован на компилятор или интерпретатор.

Существуют программы, к-ые сначала интерпретируются, а потом откомпилируются.

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

Исполнитель – некоторая абстрактная или реальная система, способная выполнить действия, предписания алгоритма.

Характеризуются: средой, элементами действия, системой команд, отказами.

Среда – место обитания исполнителя.

Системы команд (СКИ) – строго определяют действия.

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

Отказы – если команда вызывается при недопустимой для нее цели, среды.

Команды алгоритмического языка:

1. Команда присваивания служит для вычисления выражения и присвоения их значений переменным, где := - заменить прежнее значений переменной, стоящей в левой части на вычисление значения выражения, стоящего в правой части.
2. Команды «если» и «выбор» применяют для организации ветвлений, команды «для», «пока» - для организации цикла.

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

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

Характерной особенностью базовых структур является наличие в них одного входа и одного выхода.

Базовая структура следование. Образуется из последовательности действий, следующих одно за другим:

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

Структура ветвление существует в четырех основных вариантах:

если-то;

если-то-иначе;

выбор;

выбор-иначе.

Базовая структура цикл. Обеспечивает многократное выполнение некоторой совокупности действий, которая называется телом цикла.

Структура цикл существует в трех основных вариантах:

Цикл типа для.

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

Цикл типа пока.

Предписывает выполнять тело цикла до тех пор, пока выполняется условие, записанное после слова пока.

Цикл типа делать - пока.

Предписывает выполнять тело цикла до тех пор, пока выполняется условие, записанное после слова пока. Условие проверяется после выполнения тела цикла.

Заметим, что циклы для и пока называют также циклами с предпроверкой условия, а циклы делать - пока - циклами с постпроверкой условия. Иными словами, тела циклов для и пока могут не выполниться ни разу, если условие окончания цикла изначально не верно. Тело цикла делать - пока выполнится как минимум один раз, даже если условие окончания цикла изначально не верно.

Итерационные циклы. Особенностью итерационного цикла является то, что число повторений операторов тела цикла заранее неизвестно. Для его организации используется цикл типа пока. Выход из итерационного цикла осуществляется в случае выполнения заданного условия.

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

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

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

Вложенные циклы.

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

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

Для записи алгоритмов, исполнителем к-ых является компьютер, язык должен быть строго формализован (такой яз. принято называть яз. программирования, а запись алгоритма – программой).

В зависимости от степени детализации предписаний определяется уровень яз. программирования.

Чем меньше детализация, тем выше уровень языка.

машинные;

машинно-оpиентиpованные (ассемблеpы);

машинно-независимые (языки высокого уровня).

Машинные языки и машинно-ориентированные языки - это языки низкого уровня, требующие указания мелких деталей процесса обработки данных.

Языки же высокого уровня имитируют естественные языки, используя некоторые слова разговорного языка и общепринятые математические символы. Эти языки более удобны для человека.

Основные преимущества таковы алгоритмических языков.

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

Алгоритмический язык (как и любой другой язык) образуют три его составляющие: алфавит, синтаксис и семантика.

Алфавит - это фиксированный для данного языка набор основных символов, т.е. "букв алфавита", из которых должен состоять любой текст на этом языке - никакие другие символы в тексте не допускаются. Из символов алфавита формируются лексемы языка:

константы;

идентификаторы;

знаки операций;

ключевые (служебные, иначе зарезервированные) слова;

разделители (знаки пунктуации).

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

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

Каждое понятие алгоритмического языка подразумевает некоторую синтаксическую единицу (конструкцию) и определяемые ею свойства программных объектов или процесса обработки данных.

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

Основными понятиями в алгоритмических языках обычно являются данные, имена, операции и выражения, операторы.

Данные - величины, обрабатываемые программой. Имеется три основных вида данных: константы, переменные и массивы.

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

Числовые константы, Логические (да (истина, TRUE), нет (ложь, FALSE)), Символьные и строковые константы, литерные. 

Имена (идентификаторы) - употребляются для обозначения объектов программы (переменных, массивов, процедур и дp.). В VBA имена констант, переменных и процедур должны удовлетворять следующим требованиям:

должны начинаться с буквы; не могут содержать точки и символов объявления типа;

не могут быть длиннее 255 символов. Длина имен объектов не должна превышать 40 символов, не могут быть ключевыми словами (именами операций, операторов, встроенных функций).

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

Массивы - последовательности логически связанных элементов одного типа, которым присвоено одно имя.

Операции. 1. арифметические операции, используемые для выполнения математических вычислений: ^, *, /, , Mod, +, -. Здесь - Возвращает результат целого деления двух чисел, Mod - Возвращает остаток при целом делении двух чисел (значение по модулю).

2. операции сравнения, используемые для выполнения операций сравнения

< , > , <=, >= , = , <> ;

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

4. операция конкатенации символьных значений дpуг с другом с образованием одной длинной строки:

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

Выражения записываются в виде линейных последовательностей символов (без подстрочных и надстрочных символов.

1. Арифметические выражения служат для определения одного числового значения.

2. Логические выражения описывают некоторые условия, которые могут удовлетворяться или не удовлетворяться. Таким образом, логическое выражение может принимать только два значения - "истина" или "ложь" (да или нет).

Ещё посмотрите лекцию "66. Планирование и финансирование мероприятий по охране труда" по этой теме.

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

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

ключевые слова;

данные;

выражения и т.д.

Операторы подразделяются на исполняемые и неисполняемые. Неисполняемые операторы предназначены для описания данных и структуры программы, а исполняемые - для выполнения различных действий (например, оператор присваивания, операторы ввода и вывода, условный оператор, операторы цикла, оператор процедуры и дp.).