Понятие информации Слово информация вошло в русский язык в Петровскую эпоху: от лат. informatio через польское informacja (возможно также посредство фр. - презентация

1 Понятие информации Слово информация вошло в русский язык в Петровскую эпоху: от лат. informatio через польское informacja (возможно также посредство фр. и нем.). Впервые фиксируется в «Духовном регламенте» 1721 г. в значении «представление, понятие о чем-либо». (В европейских языках оно закрепилось раньше - около XIV в.) Лат. informatio образовано от in-formo, с первичным значением «придавать вид, форму, формировать, создавать, образовывать» и со вторичными «обучать, воспитывать», «строить, составлять», а также «воображать, мыслить». Таким образом, исходно информация - это «придание формы».

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

3 Значением может быть реконструируемое по знаку событие, послужившее причиной его возникновения (в случае «природных» и непроизвольных знаков, таких, как следы, улики и проч.), либо сообщение (в случае условных знаков, свойственных сфере языка). Сообщения могут содержать информацию о фактах или интерпретацию фактов.

4 Можно проследить связь: источник сообщения => потребитель сообщения. Необходимым условием возникновения информации будет адекватная интерпретация потребителем полученного им сообщения. Компьютер может выступать и как источник, и как потребитель сообщений. Информация, зафиксированная в памяти ЭВМ как последовательность сообщений, носит название данных. Нам представляется невозможным (в современных условиях) возникновение информации в связке компьютер компьютер, поскольку любая вычислительная машина оперирует с данными, а не с информацией.

5 Живое существо получает информацию с помощью органов чувств, а также посредством размышления или интуиции. Обмен информацией между субъектами есть общение или коммуникация (от лат. communicatio, сообщение, передача, производное в свою очередь от лат. communico, делать общим, сообщать, беседовать, соединять). Информация, как выраженный разумный смысл, есть знание, которое может храниться, передаваться и являться основой для порождения другого знания. Формы консервации знания (историческая память) многообразны: от мифов, летописей и пирамид до библиотек, музеев и компьютерных баз данных. Четкого определения термина "информация" не существует; есть множество вариантов, приведем некоторые из них.

6 Определение 1. Информация есть форма движения материи. Определение 2. Информация - одна из трех составляющих основ мироздания наряду с материей и энергией. Определение 3. Информация есть отражение реального мира, это сведения, которые один реальный объект содержит о другом реальном объекте. Согласно последнему определению, понятие информации связывается с определенным объектом, свойства которого она отражает. Информация о любом материальном объекте может быть получена путем наблюдения за этим объектом, вычислительного эксперимента над ним или путем логического вывода. В связи с этим информацию делят на доопытную, или априорную, и послеопытную, или апостериорную, полученную в результате проведенного эксперимента. Информация передается с помощью сообщений. Под сообщением будем понимать различные средства общения людей. Соответствие между сообщением и информацией не является взаимно однозначным. Для одной и той же информации могут существовать различные передающие ее сообщения, которые появляются при добавлении сообщения, не несущего никакой дополнительной информации. Сообщения, передающие одну и ту же информацию, образуют класс эквивалентных сообщений.

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

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

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

10 Методы хранения и передачи информации Процедура хранения информации в ПК состоит в том, чтобы сформировать и поддерживать структуру хранения данных в памяти компьютера. Современные структуры хранения данных должны быть независимы от программ, использующих эти данные, и реализовывать принципы полноты и минимальной избыточности. Такие структуры получили название "базы данных". Процедуры создания структуры хранения (базы данных), актуализации, извлечения и удаления данных производятся при помощи специальных программ, называемых "системы управления базами данных". Процедура актуализации данных позволяет изменить значения данных, записанных в базе, либо дополнить определенный раздел, группу данных. Устаревшие данные могут быть удалены с помощью соответствующей операции. Процедура извлечения данных необходима для пересылки из базы данных необходимых сведений либо для преобразования, либо для отображения, либо для передачи по вычислительной сети.

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

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

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

14 Сообщение от источника к получателю передается посредством какой-нибудь среды, являющейся в таком случае «каналом связи». Так, при передаче речевого сообщения в качестве такого канала связи можно рассматривать воздух, в котором распространяются звуковые волны, а в случае передачи письменного сообщения (например, текста, распечатанного на принтере) каналом сообщения можно считать лист бумаги, на котором напечатан текст. Человеку свойственно субъективное восприятие информации через некоторый набор ее свойств: важность, достоверность, своевременность, доступность, «больше- меньше» и т.д. Использование терминов «больше информации» или «меньше информации» подразумевает некую возможность ее измерения (или хотя бы количественного соотнесения). При субъективном восприятии измерение информации возможно лишь в виде установления некоторой субъективной порядковой шкалы для оценки «больше-меньше». При объективном измерении количества информации следует заведомо отрешиться от восприятия ее с точки зрения субъективных свойств, примеры которых перечислены выше. Более того, не исключено, что не всякая информация будет иметь объективно измеряемое количество.

15 Чтобы сообщение было передано от источника к получателю необходима некоторая материальная субстанция носитель информации. Сообщение, передаваемое с помощью носителя сигнал. В общем случае сигнал это изменяющийся во времени физический процесс. Та из характеристик процесса, которая используется для представления сообщений, называется параметром сигнала. В случае, когда параметр сигнала принимает последовательное во времени конечное число значений (при этом все они могут быть пронумерованы), сигнал называется дискретным, а сообщение, передаваемое с помощью таких сигналов дискретным сообщением. Если же источник вырабатывает непрерывное сообщение (соответственно параметр сигнала непрерывная функция от времени), то соответствующая информация называется непрерывной. Примеры дискретного сообщения текст книги, непрерывного сообщения человеческая речь, передаваемая модулированной звуковой волной; параметром сигнала в этом случае является давление, создаваемое этой волной в точке нахождения приемника человеческого уха.

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

17 Единицы количества информации: вероятностный и объемный подходы Определить понятие «количество информации» довольно сложно. В решении этой проблемы существуют два основных подхода. Исторически они возникли почти одновременно. В конце 40-х годов XX века один из основоположников кибернетики американский математик Клод Шеннон развил вероятностный подход к измерению количества информации, а работы по созданию ЭВМ привели к «объемному» подходу. Вероятностный подход Рассмотрим в качестве примера опыт, связанный с бросанием правильной игральной кости, имеющей N граней. Результаты данного опыта могут быть следующие: выпадение грани с одним из следующих знаков: 1, 2,... N. Введем в рассмотрение численную величину, измеряющую неопределенность энтропию (обозначим ее H). Согласно развитой теории, в случае равновероятного выпадания каждой из граней величины N и H связаны между собой формулой Хартли H = log2 N. Важным при введении какой-либо величины является вопрос о том, что принимать за единицу ее измерения. Очевидно, H будет равно единице при N = 2. Иначе говоря, в качестве единицы принимается количество информации, связанное с проведением опыта, состоящего в получении одного из двух равновероятных исходов (примером такого опыта может служить бросание монеты при котором возможны два исхода: «орел», «решка»). Такая единица количества информации называется «бит».

18 Единицы количества информации: вероятностный и объемный подходы В случае, когда вероятности Pi результатов опыта (в примере, приведенном выше бросания игральной кости) неодинаковы, имеет место формула Шеннона. Формула Шеннона: I = – ( p1 log2 p1 + p2 log2 p pN……log2….), где pi вероятность того, что именно i-е сообщение выделено в наборе из N сообщений. Легко заметить, что если вероятности p1,..., pN равны, то каждая из них равна 1/N, и формула Шеннона превращается в формулу Хартли. В качестве примера определим количество информации, связанное с появлением каждого символа в сообщениях, записанных на русском языке. Будем считать, что русский алфавит состоит из 33 букв и знака «пробел» для разделения слов. По формуле Хартли H = log2 34 ~ 5.09 бит. Однако, в словах русского языка (равно как и в словах других языков) различные буквы встречаются неодинаково часто. Ниже приведена табл. 3 вероятностей частоты употребления различных знаков русского алфавита, полученная на основе анализа очень больших по объему текстов.

19 Воспользуемся для подсчета H формулой Шеннона: H ~ 4.72 бит. Полученное значение H, как и можно было предположить, меньше вычисленного ранее. Величина H, вычисляемая по формуле Хартли, является максимальным количеством информации, которое могло бы приходиться на один знак. Аналогичные подсчеты H можно провести и для других языков, например, использующих латинский алфавит английского, немецкого, французского и др. (26 различных букв и «пробел»). По формуле Хартли получим H = log2 27 ~ 4.76 бит. Таблица 1 Частотность букв русского языка

20 Рассмотрим алфавит, состоящий из двух знаков 0 и 1. Если считать, что со знаками 0 и 1 в двоичном алфавите связаны одинаковые вероятности их появления (P(0)=P(1)= 0.5), то количество информации на один знак при двоичном кодировании будет равно H = log2 2 = 1 бит. Таким образом, количество информации (в битах), заключенное в двоичном слове, равно числу двоичных знаков в нем. Объемный подход В двоичной системе счисления знаки 0 и 1 называют битами (от английского выражения Binary digiTs двоичные цифры). В компьютере бит является наименьшей возможной единицей информации. Объем информации, записанной двоичными знаками в памяти компьютера или на внешнем носителе информации, подсчитывается просто по количеству требуемых для такой записи двоичных символов. При этом, в частности, невозможно нецелое число битов (в отличие от вероятностного подхода). Для удобства использования введены и более крупные, чем бит, единицы количества информации. Так, двоичное слово из восьми знаков содержит один байт информации байта образуют килобайт (Кбайт), 1024 килобайта мегабайт (Мбайт), а 1024 мегабайта гигабайт (Гбайт). статистики.

21 Между вероятностным и объемным количеством информации соотношение неоднозначное. Далеко не всякий текст, записанный двоичными символами, допускает измерение объема информации в вероятностном (кибернетическом) смысле, но заведомо допускает его в объемном. Далее, если некоторое сообщение допускают измеримость количества информации в обоих смыслах, то это количество не обязательно совпадает, при этом кибернетическое количество информации не может быть больше объемного. В прикладной информатике практически всегда количество информации понимается в объемном смысле. Как ни важно измерение информации, нельзя сводить к нему все связанные с этим понятием проблемы. При анализе информации социального (в широким смысле) происхождения на первый план могут выступить такие ее свойства как истинность, своевременность, ценность, полнота и т.д. Их невозможно оценить в терминах «уменьшение неопределенности» (вероятностный подход) или числа символов (объемный подход). Обращение к качественной стороне информации породило иные подходы к ее оценке. При аксиологическом подходе стремятся исходить из ценности, практической значимости информации, т.е. качественных характеристик, значимых в социальной системе. При семантическом подходе информация рассматривается как с точки зрения формы, так и содержания. При этом информацию связывают с тезаурусом, т.е. полнотой систематизированного набора данных о предмете информации. Отметим, что эти подходы не исключают количественного анализа, но он становится существенно сложнее и должен базироваться на современных методах математической статистики.

22 Понятие информации нельзя считать лишь техническим, междисциплинарным и даже наддисциплинарным термином. Информация это фундаментальная философская категория. Дискуссии ученых о философских аспектах информации надежно показали несводимость информации ни к одной из этих категорий. Концепции и толкования, возникающие на пути догматических подходов, оказываются слишком частными, односторонними, не охватывающими всего объема этого понятия. Попытки рассмотреть категорию информации с позиций основного вопроса философии привели к возникновению двух противостоящих концепций так называемых, функциональной и атрибутивной. «Атрибутисты» квалифицируют информацию как свойство всех материальных объектов, т.е. как атрибут материи. «Функционалисты» связывают информацию лишь с функционированием сложных, самоорганизующихся систем. Можно попытаться дать философское определение информации с помощью указания на связь определяемого понятия с категориями отражения и активности. Информация есть содержание образа, формируемого в процессе отражения. Активность входит в это определение в виде представления о формировании некоего образа в процессе отражения некоторого субъект-объектного отношения. При этом не требуется указания на связь информации с материей, поскольку как субъект, так и объект процесса отражения могут принадлежать как к материальной, так и к духовной сфере социальной жизни. Однако существенно подчеркнуть, что материалистическое решение основного вопроса философии требует признания необходимости существования материальной среды носителя информации в процессе такого отражения. Итак, информацию следует трактовать как имманентный (неотъемлемо присущий) атрибут материи, необходимый момент ее самодвижения и саморазвития. Эта категория приобретает особое значение применительно к высшим формам движения материи биологической и социальной.

23 Известно большое количество работ, посвященных физической трактовке информации. Эти работы в значительной мере построены на основе аналогии формулы Больцмана, описывающей энтропию статистической системы материальных частиц, и формулы Хартли. Соответствующие материалы можно найти в литературе, отраженной в приведенном ниже перечне. Информацию следует считать особым видом ресурса, при этом имеется в виду толкование «ресурса» как запаса неких знаний материальных предметов или энергетических, структурных или каких-либо других характеристик предмета. В отличие от ресурсов, связанных с материальными предметами, информационные ресурсы являются неистощимыми и предполагают существенно иные методы воспроизведения и обновления, чем материальные ресурсы. В связи с таким взглядом центральными становятся следующие свойства информации: запоминаемость, передаваемость, преобразуемость, воспроизводимость, стираемость.

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

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

26 Системы счисления Системы счисления одна из традиционных тем курса информатики, восходящих к программированию ЭВМ первых поколений в машинных кодах. В настоящее время данная тема сохраняет свое значение как весьма типичный случай кодирования информации, а также в связи с широким использованием шестнадцатеричных обозначений в машинно-ориентированных разделах программирования. Знание систем счисления полезно для понимания представления данных в памяти ЭВМ и операций над ними. Системы счисления (особенно по основанию 10) достаточно подробно изучаются в курсах математики и информатики средней общеобразовательной школы. В данном курсе эта тема предполагает повторение уже известных сведений, специализацию в отношении систем счисления по основанию 16, 8 и 2, а также обобщение в плане кодирования информации. Целесообразно проведение семинарского занятия, подготовка рефератов, посвященных истории и значению позиционных систем счисления. Особое внимание следует уделить формированию стабильных навыков чтения и записи чисел в шестнадцатеричной системе. Полезным является и знакомство с различными приемами перевода чисел в системы счисления по основанию 2, 8 и 16, в том числе с помощью калькулятора или компьютера и встроенного интерпретатора языка BASIC. Перевод чисел из одной позиционной системы счисления в другую. Арифметические операции При переводе чисел из десятичной системы счисления в систему с основанием P > 1 обычно используют следующий алгоритм: 1) если переводится целая часть числа, то она делится на P, после чего запоминается остаток от деления. Полученное частное вновь делится на P, остаток запоминается. Процедура продолжается до тех пор, пока частное не станет равным нулю. Остатки от деления на P выписываются в порядке, обратном их получению; 2) если переводится дробная часть числа, то она умножается на P, после чего целая часть запоминается и отбрасывается. Вновь полученная дробная часть умножается на P и т.д. Процедура продолжается до тех пор, пока дробная часть не станет равной нулю. Целые части выписываются после двоичной запятой в порядке их получения. Результатом может быть либо конечная, либо периодическая двоичная дробь. Поэтому, когда дробь является периодической, приходится обрывать умножение на каком-либо шаге и довольствоваться приближенной записью исходного числа в системе с основанием P.

27 Пример 1. Перевести данное число из десятичной системы счисления в двоичную (получить пять знаков после запятой в двоичном представлении). а) 464 (10) ;б) 380,1875 (10) ;в) 115,94 (10) Решение а) 464 (10) = (2) ; б) 380,1875 (10) = ,0011 (2) ; в) 115,94 (10) ,11110 (2) (в данном случае было получено шесть знаков после запятой, после чего результат был округлен.) Если необходимо перевести число из двоичной системы счисления в систему счисления, основанием которой является степень двойки, достаточно объединить цифры двоичного числа в группы по столько цифр, каков показатель степени, и использовать приведенный ниже алгоритм. Например, если перевод осуществляется в восьмеричную систему, то группы будут содержать три цифры (8 = 2 3 ). В целой части числа группировка производится справа налево, в дробной части слева направо. Если в последней группе недостает цифр, дописываются нули: в целой части слева, в дробной справа. Затем каждая группа заменяется соответствующей цифрой новой системы. Соответствия приведены в таблице.

28 PСоответствия ABCDEF Переведем из двоичной системы в шестнадцатеричную число ,11 (2) ,1100 (2) = 3D5,C (16). При переводе чисел из системы счисления с основанием P в десятичную систему счисления необходимо пронумеровать разряды целой части справа налево, начиная с нулевого, и дробной части, начиная с разряда сразу после запятой, слева направо (начальный номер –1). Затем вычислить сумму произведений соответствующих значений разрядов на основание системы счисления в степени, равной номеру разряда. Это и есть представление исходного числа в десятичной системе счисления.

29 Пример 2. Перевести данное число в десятичную систему счисления: а) (2) (2) = = = 65(10). Замечание. Если в каком-либо разряде стоит нуль, то соответствующее слагаемое можно опускать. б) ,0101(2) ,0101(2) = – –4 = = ,25 + 0,0625 = 543,3125(10). в) 1216,04(8). 1216,04(8) = –2 = ,0625 = 654,0625(10). г) 29A,5(16). 29A,5(16) = –1 = ,3125 = 656,3125(10). Для выполнения арифметических операций в системе счисления с основанием P необходимо иметь соответствующие таблицы сложения и умножения

30 ABCDEF ABCDEF ABCDEF ABCDEF ABCDEF ABCDEF ABCDEF ABCDEF ABCDEF ABCDEF ABCDEF AABCDEF BBCDEF A CCDEF A1B DDEF A1B1C EEF A1B1C1D FF A1B1C1D1E

31 ABCDEF ABCDEF ACE A1C1E 30369CF B1E A2D 4048C C C C 505AF14191E23282D32373C41464B 606C12181E242A30363C42484E545A 707E151C232A31383F464D545B B242D363F48515A636C757E87 A0A141E28323C46505A646E78828C96 B0B16212C37424D58636E79848F9AA5 C0C C C CA8B4 D0D1A E5B F9CA9B6C3 E0E1C2A E8C9AA8B6C4D2 F0F1E2D3C4B5A A5B4C3D2E1

32 Пример 3. Сложить числа: а) (2) (2) = (2) ; б) 223,2 (8) + 427,54 (8) = 652,74 (8) ; в) 3B3,6 (16) + 38B,4 (16) = 73E,A (16) ,2 3B3, ,54 38B, ,74 73E,A Пример 4. Выполнить вычитание: а) ,011 (2) – ,1 (2) = ,111 (2) ; б) 1510,2 (8) – 1230,54 (8) = 257,44 (8) ; в) 27D,D8 (16) – 191,2 (16) = EC,B8 (16) , ,2 27D,D8 – – – , , , ,44 EC,B8

33 Пример 5. Выполнить умножение: а) (2) (2) = (2) ; б) 1170,64 (8) 46,3 (8) = 57334,134 (8) ; в) 61,A (16) 40,D (16) = 18B7,52 (16) ,6,6 4 61,1, A ,3,3 40,0, D F B7,5, ,1,

34 Контрольные вопросы 1.Какие системы счисления называются позиционными, а какие непозиционными? Приведите примеры. 2.Что называется основанием системы счисления? 3.Почему для вычислительной техники особенно важна система счисления по основанию 2? 4.Почему произошел переход от двоичных к шестнадцатеричным обозначениям в архитектуре ЭВМ? 5.Какие способы перевода целых десятичных чисел в двоичные и обратно вы знаете? 6.Каковы правила выполнения арифметических операций над числами в двоичном представлении? 7.Как переводить целые числа из двоичного представления в восьмеричное и шестнадцатеричное представления и обратно? 8.Какое двоичное представление отрицательных целых числе используется в вычислительной технике? 9.Как представляются в вычислительной технике действительные числа (числа с плавающей запятой)? 10.Дать определение системы счисления. Назвать и охарактеризовать свойства системы счисления. 11.Какие символы используются для записи чисел в двоичной системе счисления, восьмеричной, шестнадцатеричной? 12.Чему равны веса разрядов слева от точки, разделяющей целую и дробную часть, в двоичной системе счисления (восьмеричной, шестнадцатеричной)? 13.Чему равны веса разрядов справа от точки, разделяющей целую и дробную часть, в двоичной системе счисления (восьмеричной, шестнадцатеричной)?

35 ОСНОВЫ АЛГОРИТМИЗАЦИИ Слово «алгоритм» появилось в 9-м веке и связано с именем математика Аль-Хорезми, который сформулировал правила выполнения четырех арифметических действий над многозначными числами. В настоящее время понятие алгоритма - одно из фундаментальных понятий науки информатики. С одной стороны алгоритм является предметом изучения такой отрасли математики как теория алгоритмов (Марков), с другой стороны в информатике существует неформальное определение алгоритма, и алгоритмизация выступает в качестве общего метода информатики. Объектом приложения алгоритмов являются самые различные науки и области практической деятельности (Хохлюк, Ахо). Широкое применение алгоритмов для решения практических задач не только при использовании ЭВМ позволяет рассматривать эту область информатики как отдельную дисциплину - алгоритмику. Алгоритм – это точно определенная последовательность действий для некоторого исполнителя, выполняемых по строго определенным правилам и приводящих через некоторое количество шагов к решению задачи. Исполнитель алгоритмов определяет элементарные действия, из которых формируется алгоритм. Отдельные действия, составляющие алгоритм, называются операциями. При этом под операцией понимается как какое-то единичное действие, например, сложение, так и группа взаимосвязанных действий.

36 Свойства алгоритма: Определенность – выполнив очередное действие, исполнитель должен точно знать, что ему делать дальше. Дискретность – прежде, чем выполнить определенное действие, надо выполнить предыдущее. Массовость – по одному и тому же алгоритму решаются однотипные задачи и неоднократно. Понятность – алгоритм строится для конкретного исполнителя человеком и должен быть ему понятен. Это облегчает его проверку и модификацию при необходимости. Результативность – алгоритм всегда должен приводить к результату. Основными особенностями любого алгоритма являются решение задачи в обобщенном виде и возможность выполнять действия по решению задачи для конкретных значений (не только человеку, но и различным техническим устройствам (исполнителям)). Основным исполнителем несложных алгоритмов является человек. Достаточно вспомнить последовательность действий для решения систем линейных уравнений, вычисления корней уравнений. При решении сложных задач исполнителем является ЭВМ и составление алгоритма решения задачи является необходимым этапом, детализирующим метод решения для дальнейшего программирования. Программа осуществляет еще более глубокую детализацию решения и его визуализацию. Можно сказать, что в процессе формального решения задачи, ее решение сначала описывается на языке математики в виде системы формул, а затем на языке алгоритмов в виде некоторого процесса, в котором используются ранее определенные математические формулы и условия их выполнения. Таким образом, алгоритм может рассматриваться как связующее звено в цепочке "метод решения - реализующая программа".

37 ОСНОВНЫЕ СРЕДСТВА ПРЕДСТАВЛЕНИЯ АЛГОРИТМОВ Алгоритм моделирует решение задачи в виде точно определенной последовательности действий для некоторого исполнителя по преобразованию исходных данных в результирующие. Процесс составления алгоритмов называют алгоритмизацией. Алгоритм, реализующий решение задачи, можно представить различными способами: с помощью графического или текстового описания, в виде таблицы значений. Графический способ представления алгоритмов имеет ряд преимуществ благодаря визуальности и явному отображению процесса решения задачи. Алгоритмы, представленные графическими средствами, получили название визуальные алгоритмы. Текстовое описание алгоритма является достаточно компактным и может быть реализовано на абстрактном или реальном языке программирования в виде программы для ЭВМ. Таблицы значений представляют алгоритм неявно, как некоторое преобразование конкретных исходных данных в выходные. Табличный способ описания алгоритмов может быть с успехом применен для проверки правильности функционирования разработанного алгоритма на конкретных тестовых наборах входных данных, которые вместе с результатами выполнения алгоритма фиксируются в "таблицах трассировки". Таким образом, все три способа представления алгоритмов можно считать взаимодополняющими друг друга. На этапе проектирования алгоритмов наилучшим способом является графическое представление, на этапе проверки алгоритма - табличное описание, на этапе применения - текстовая запись в виде программы.

38 ВИЗУАЛЬНЫЕ АЛГОРИТМЫ При проектировании визуальных алгоритмов используют специальные графические элементы, называемые графически блоками, которые представлены на рис. Результатом алгоритмизации решения задачи является блок-схема алгоритма, состоящая из некоторой последовательности таких графических блоков. КОНЕЦ НАЧАЛО Блок начала алгоритма Ввести X,Y Y = F + B Блок действия Блок ввода или вывода + X> Y Блок условия, имеет два выхода Блок окончания алгоритма Рис.1. Основные блоки визуальных алгоритмов

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

40 Итерация - это циклическая управляющая структура, которая содержит композицию и ветвление. Она предназначена для организации повторяющихся процессов обработки последовательности значений данных. В соответствии с наличием в алгоритмах управляющих структур композиции, альтернативы и итерации алгоритмы классифицируют на: линейные, разветвленные и циклические алгоритмы. Линейные алгоритмы не содержат блока условия. Они предназначены для представления линейных процессов. Такие алгоритмы применяют для описания обобщенного решения задачи в виде последовательности модулей. Пример линейного алгоритма приведен на рисунке 2. Начало Ввод X,Y Z = X+Y C = X-Y D = X*Y Вывод Z,C,D Конец Рис. 2. Пример линейного визуального алгоритма

41 РАЗВЕТВЛЕННЫЕ АЛГОРИТМЫ Разветвленные алгоритмы в своем составе содержат блок условия и различные конструкции ветвления. Ветвление - это структура, обеспечивающая выбор между альтернативами. _ + А>C Z = AZ = C X

42 Каждая управляющая структура ветвления имеет один вход и один выход. Ветвления содержат блок условия, в котором записывают логические условия, такие как А > С, X С принимает значение "истина" или "ложь" и процесс вычислений включает блок действия Z=A или Z=C. Аналогично происходит и в управляющей структуре неполного ветвления (рис. 3 б)). Только в этом случае, если условие X

43 + НАЧАЛО Ввод A,B,C A

44 + + НАЧАЛО Ввод А,В,С АC A

45 Пример 2. Составить алгоритм определения находится ли точка М с координатами Х, У на окружности радиуса R. Решение. Визуальный алгоритм приведен на рис.7. Для решения в нем используется математическая модель в виде формулы окружности R 2 = X 2 +Y 2.

46 Рис. 6.Поиск минимального Рис. 7. Определить находит- числа из трёх А,В,С. Метод ся ли точка М с координата- сравнения с промежуточной ми Х,У на окружности переменной М радиуса R + Начало Kонец Ввод M(X, Y),R НЕ Т T:=X 2 +Y 2 T=R 2 ДА + + Начало Конец Ввод A,B,C Вывод M M:=A M>B M>C M:=B M:=C

47 Пример 3. Составить алгоритм определения корней уравнения (X 2 +B*X+C=0). Решение. При составления этого алгоритма надо рассмотреть случаи, когда уравнение не имеет корней и когда имеется только один корень. Обозначим корни уравнения через переменные Х1,Х2. D - промежуточная переменная для вычисления дискриминанта. Алгоритм вычисления корней уравнения заданного вида приведен на рис КОНЕЦ НАЧАЛО Ввод B,C НЕТ КОРНЕЙ Вывод X1,X2 Вы- вод X D:=B 2 - 4*C X1:=(-B+D 0,5 )/2 X1:=-B/2 X2:=(-B-D 0,5 )/2 D

48 Задания для самостоятельного выполнения: Составить визуальные разветвленные алгоритмы для следующих задач. 1.Для двух чисел Х,У определить, являются ли они корнями уравнения А*Р 4 +D*P 2 +C=0 2.Если среди трех чисел А,В,С имеется хотя бы одно четное вычислить максимальное, иначе - минимальное 3.Ввести положительное А>=1. Найти наибольшее из выражений вида 1\А и SIN(A). 4.Ввести два числа. Меньшее заменить полусуммой, а большее - удвоенным произведением. 5.Ввести три числа А,В,С. Удвоить каждое из них, если А>=В>=С, иначе поменять значения А и В. 6.Определить является ли точка с координатами X,Y точкой пересечения диагоналей квадрата со стороной R,одна вершина которого расположена в начале координат. 7.* Определить значения функции в зависимости от значения аргумента а*х2, если х > 10 у= 1/х, если –10 х 10 Sin(х), если х < 10

49 Циклические алгоритмы являются наиболее распространенным видом алгоритмов, в них предусматривается повторное выполнение определенного набора действий при выполнении некоторого условия. Такое повторное выполнение часто называют циклом. Существуют два основных видов циклических алгоритмов: циклические алгоритмы с предусловием, циклические алгоритмы с постусловием. Они отличаются друг от друга местоположением условия выхода их цикла. Цикл с предусловием начинается с проверки условия выхода из цикла. Это логическое выражение, например I 6.Проверка его осуществляется тоже по-другому. Если условие выхода истинно, то цикл с постусловием прекращает свою работу, в противном случае - происходит повторение действий, указанных в цикле. Повторяющиеся действия в цикле называются "телом цикла". Разновидности циклов приведены на рис. 9 а), б). ЦИКЛИЧЕСКИЕ АЛГОРИТМЫ

50 + i>6 i=1 K:=K+1 i:=i+0,1 K + i=1 I

51 Классическим примером циклического алгоритма служит алгоритм для вычисления степени числа Y=X. Этот алгоритм может быть реализован на основе операции умножения. Табличное представление такого алгоритма, отражающего зависимость У от Х при изменении показателя степени n от 1 до 3, представлено в табл.1. В этой таблице показанны также реккурентные соотношения между У и Х, определяющие как на каждом шаге зависит значение У от значения Х и от значения У, вычисленного на предыдущем шаге. Таблица 1. Реккурентные соотношения при вычислении Y=X nYРеккурентные соотношения 1Y[1]=XY=X 2Y[2]=X*X или Y[2]=Y[1]*XY=X*X или Y=Y*X 3Y[3]=X*X*X или Y[3]=Y[2]*X Y=X*X*X или Y=Y*X

52 НАЧАЛО Ввод x, N S:=0 Y:=x K:=1 K

53 Пример 4. Пусть требуется составить алгоритм вычисления суммы ряда S=x+x 2 +x 3 +…+x n. Решение. Исходные данные для алгоритма это переменные x и n. На каждом шаге будем вычислять очередной член суммы Y и прибавлять его к предыдущему значению суммы S.Для этого используем реккурентную формулу вычисления степени Х (см. таблицу 1) Y=Y*Х, тогда сумма ряда на каждом шаге итерации будет вычисляться по формуле S=S+Y. Количество итераций K изменяется от 1 до n и равно количеству членов ряда. Начальное значение суммы ряда S равно 0. На рис. 10 представлен циклический алгоритм с предусловием для вычисления заданной суммы ряда. Пример 5. Требуется составить алгоритм получения на отрезке [-15,15] множества значений функции Y= SIN(X) в виде таблицы значений (X,Y) при изменении аргумента Х по формуле X[k]=X[k-1]+h, где h = 1,5. Решение. Такие задачи относят к задачам табулирования функций. Из условия задачи определяем, что начальное значение отрезка табулирования X= -15, конечное значение - X=15. Процесс получения множества пар Х,Y является итерационным, значит проектируемый алгоритм будет циклическим. Условие выхода из цикла Х>15. На рис. 11 представлен циклический алгоритм с предусловием вычисления табличного значения функции Y= SIN(X) на отрезке -15

54 X:= -15 x

55 Задания для самостоятельного выполнения Составить визуальные циклические алгоритмы для следующих задач: 1. Вычислить число в факториале Y=X! 2. Вычислить сумму ряда, общий член которого задан формулой A n =(x*n)/n!. 3. При табулировании функции y=cos(x+a) на отрезке [1,10] c шагом h=1 определить сумму значений y, больших p. 4. Подсчитать количество цифр в целом числе Х. 5. Вычислить сумму значений функции у=x 2 на отрезке [1,5] c шагом 1. 6.* Найти минимальное значение функции Y=Sin(X)*X, на отрезке [C,D] с шагом Реализовать цикл с постусловием. 7. Протабулировать функцию y=sin(x) на отрезке [1,5] с шагом h=0,5. Вывести предпоследнее положительное значение функции. 8. Определить постановку задачи и составить визуальный алгоритм для этой задачи, если табличное представление ее решения изображено ниже: Условие N>0SN >0 да0+5=512 12>0 да5+2=71 1>0 да7+1=80 0>0 нет

56 9. Составить визуальную и табличную формы алгоритма по его текстовому представлению, а также определить конечное значение S. А) I=0; S=0; В) I=1; S=0; ПОКА I 1 I=I+3 S=S+1/I S=S+I*I I=I-1 ВЫВОД S ВЫВОД S 10. Составить визуальную и текстовую форму представления алгоритма, заданного в табличной форме. I J S = = = = Определить является ли данный фрагмент алгоритма циклом, если да, то какого вида и какое действие является телом цикла?

57 A) В) + I =1 I := I +1 K I

58 12. * Протабулировать функцию Y=tg(X), при изменении X на отрезке [A,B] с шагом K и определить количество точек разрыва (M) этой функции. 13. Определите местонахождение ошибок в алгоритмическом решении следующей задачи. Найти минимальное значение функции Y=A*X 2 +Sin(X)*X 0,5, для Х изменяющемся на отрезке [C,D] с шагом 0,01. НАЧАЛО C, D X := C M := A*X 2 +SIN(X)*X 0. 5 Y=М X := X Y, X Y D M КОНЕЦ Y := A*X 2 +SIN(X)*X 0. 5 C := Y

59 АЛГОРИТМЫ ОБРАБОТКИ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ЧИСЕЛ Последовательность значений - это набор однотипных величин, которые вводятся и обрабатываются циклически. Примером последовательности целых чисел может быть следующий набор значений: (2,5,- 4,10,1,0). Последовательности значений отличаются от массивов значений тем, что в памяти одновременно все значения последовательности не хранятся. Для обозначения значения последовательности используют одну переменную, в которую на каждом шаге итерации вводится очередное значение последовательности. Отличительной особенностью последовательности является также возможность содержания неопределенного или неизвестного заранее количества ее значений. В этом случае критерием окончания последовательности служит некоторое особое значение, например, ноль. Пример 6. В числовой последовательности определить сумму положительных и произведение отрицательных чисел. Решение представить с использованием циклического алгоритма с предусловием. Признак конца последовательности - значение 0. Решение. Обозначим за Х переменную, содержащую очередное значение последовательности, за S - сумму положительных значений, за Р - произведение отрицательных значений. Полученный алгоритм приведен на рис. 12.

60 Для вычисления суммы значений воспользуемся реккурентной формулой S=S+X с начальным значением S=0, для вычисления произведения - реккурентной формулой P=P*X с начальным значением Р=1. Условие выхода из цикла неравенство Х НАЧАЛО Ввод X P:=1 S:=0 X0 Вывод P, S КОНЕЦ X>0 S:=S+X P:=P*X Ввод Х Рис.12. Алгоритм вычисления суммы положительных и произведения отрицательных значений числовой последовательности для выбора вычислений Х>0.

61 Решение. Обозначим за Х переменную, содержащую очередное значение последовательности, за K - количество четных значений (рис. 13). Условие для выбора четных значений Х mod 2=0 (остаток при делении Х на 2 равен 0). Для вычисления количества значений воспользуемся реккурентной формулой К=К+1 с начальным значением К=0. Рис. 13. Алгоритм определения количества четных чисел в последовательности значений + НАЧАЛО Ввод X K=0 Вывод K КОНЕЦ X0 + K:=K+1 Ввод Х Х mod 2=0

62 Пример 7. Составить циклический алгоритм с постусловием для определения в последовательности целых чисел количества четных чисел Решение. Обозначим за Х переменную, содержащую очередное значение последовательности, за K - количество четных значений (рис. 14). Условие для выбора четных значений Х mod 2=0 (остаток при делении Х на 2 равен 0). Для вычисления количества значений воспользуемся реккурентной формулой К=К+1 с начальным значением К=0. + Рис. 14. Алгоритм определения количества четных чисел в последовательности значений НАЧАЛО Ввод X K=0 Вывод K КОНЕЦ X0 + K:=K+1 Ввод Х Хmod2= 0

63 Задания для самостоятельного выполнения: Составить визуальные циклические алгоритмы для следующих задач обработки последовательности значений. В последовательности чисел подсчитать произведение чисел, кратных 3. В последовательности чисел сравнить,что больше сумма положительных или произведение отрицательных. В последовательности чисел определить предпоследнее отрицательное число.(При решении введите дополнительную переменную для хранения предпоследнего отрицательного числа). В последовательности целых положительных чисел определить максимальное число (Рекомендуем реализовать такой алгоритм : Вводим Х mах=Х Цикл с постусловием а. Если элемент Х > max то max:=Х (значение этого элемента); б. Вводим новый элемент последовательности Х. Условие выхода из цикла Х=0 ) В последовательности целых чисел определить третье положительное число и подсчитать количество цифр в нем.

64 АЛГОРИТМЫ ОБРАБОТКИ ОДНОМЕРНЫХ ЧИСЛОВЫХ МАССИВОВ Под структурой данных типа массив понимают однородную структуру однотипных данных, одновременно хранящихся в последовательных ячейках оперативной памяти. Эта структура должна иметь имя и определять заданное количество данных (элементов). Однотипность данных определяет возможность использования циклических алгоритмов для обработки всех элементов массива. Количество итераций цикла определяется количеством элементов массива. Одновременное хранение в памяти всех элементов массива позволяет решать большой набор задач, таких как, поиск элементов, упорядочение и изменение порядка следования элементов. Доступ к любому элементу массива осуществляется по его номеру (индексу). Поэтому для обращения к элементу массива используют имя_массива (номер элемента), например, А(5). Массив называется одномерным, если для получения доступа к его элементам достаточно одной индексной переменной. Рассмотрим простой алгоритм ввода элементов одномерного числового массива A из 9 элементов. В этом циклическом алгоритме условие выхода из цикла определяется значением специальной переменной К, которая называется счетчиком элементов массива А (рис.15), эта же переменная К определяет количество итераций циклического алгоритма ввода элементов массива. На каждом шаге итерации переменная К(значение номера элемента массива А) изменяется на 1, то есть происходит переход к новому элементу массива. В дальнейшем, при рассмотрении алгоритмов обработки одномерных массивов в целях устранения дублирования алгоритм ввода элементов массива будем заменять одним блоком, подразумевая, что он реализуется по схеме, циклического алгоритма, представленного на рисунке 15.

65 Начало K=1 K

66 Пример 9. Составить алгоритм определения в одномерном числовом массиве А из N элементов суммы положительных элементов. Решение. Алгоритм представлен на рисунке 16. В этом алгоритме переменная К - является счетчиком элементов массива, S - сумма элементов массива, она вычисляется по реккурентной формуле S=S+A(K). Ввод количества и значений элементов массива осуществляется вначале в отдельном блоке ввода, который реализуется по схеме алгоритма ввода элементов массива, изображенного на рис.15. Часто для проверки правильности работы алгоритмов на конкретных наборах данных используют таблицу трассировки. Эта таблица содержит столько столбцов, сколько переменных и условий в алгоритме, в ней мы выполняем действия шаг за шагом от начала до конца алгоритма для конкретных наборов входных данных. Пример 10. Составить алгоритм поиска элемента с максимальным значением в одномерном массиве А(1..n) и его таблицу трассировки для значений (3, 7, 0, 9). Решение. Введем обозначения K- текущий номер элемента, A[K] - текущее значение элемента массива, N=4 количество элементов одномерного массива, M- номер максимального элемента массива, A[M] - значение максимального элемента массива. Основной идеей алгоритма является выполнение сравнения текущего элемента массива A[K] и элемента с максимальным значением A[М], определенным на предыдущем шаге итерации. По алгоритму изображенному на рис.17 получено максимальное значение для массива (3, 7, 0, 9), процесс и правильный результат поиска которого показаны в таблице 2. НАЧАЛО N, A(N) K := 1 S:= S+A(k) K:= K + 1 Вывод S K 0 КОНЕЦ Рис. 16. Алгоритм вычисления суммы положительных элементов массива

67 + НАЧАЛО K=1; М=1 K:=K+1 KA[M] [M] Рис.17. Алгоритм поиска максимального значения в массиве

68 Таблица 2. Таблица трассировки алгоритма примера 10. Номер элемента массива К Значение элемента А (К)Номер максимального М Значение максимального А(М) Проверка А(К)>А(М) 1313Нет да 3027нет да

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

70 Пример 11.Составить алгоритм решения и таблицу трассировки следующей задачи. В одномерном массиве поменять местами 2-ой нулевой элемент и последний положительный элемент. Применить нисходящее проектирование алгоритма. Решение. Пусть одномерный массив содержит 9 элементов: (5, 0, 4, - 3, -7, 0, -2, -4, 0). Среди этих элементов имеются три нулевых значения, отрицательные и положительные значения. Второй нулевой элемент имеет порядковый номер 6, а последний положительный элемент - номер 3, его значение равно 4. Если поменять местами 2-ой нулевой элемент и последний положительный в исходном массиве (5, 0, 4, -3, -7, 0, -2, -4, 0) то получим новый массив, в котором изменен порядок следования элементов 5, 0, 0, -3, -7, 4, -2, -4, 0. НАЧАЛО Ввод массива Определение номера второго нулевого элемента Перестановка элементов в массиве Вывод массива КОНЕЦ Определение номера последнего элемента >0 Основными операциями алгоритма будут: поиск второго нулевого элемента массива, поиск последнего положительного элемента массива и перестановка найденных элементов. Отметим, что для перестановки элементов необходимо знать номера переставляемых элементов. На рис. 19 изображен обобщенный алгоритм решения задачи, который в дальнейшем будет детализирован.

71 НАЧАЛ О Ввод массива Определение номера второго нулевого элемента Перестановка элементов в массиве Вывод массива Определение номера последнего элемента >0 Рис. 18. Обобщенный алгоритм к примеру 11

72 Ввод количества и значений элементов массива осуществляется вначале в отдельном блоке ввода, который реализуется по схеме алгоритма ввода элементов массива, изображенного на рис.16. Поиск второго нулевого элемента массива будем осуществлять в цикле, проверяя значение очередного элемента на 0. Если очередной элемент равен 0, то для подсчета количества таких элементов используем реккурентную формулу M=M+1. В тот момент времени, когда значение М=2, нам необходимо запомнить номер текущего элемента массива, так как это и есть искомый второй положительный элемент исходного массива. На рис.20 приведен фрагмент алгоритма, реализующего поиск второго нулевого элемента в некотором массиве А из N элементов. m:=m+1 m= 2 K=N A [K]=0 K:=1, m=0 K:=K+1 P:=K Рис. 20. Фрагмент алгоритма поиска второго нулевого элемента в массиве А, состоящем из N элементов. Здесь К- номер очередного элемента, А(К) - значение очередного элемента, m -количество нулевых элементов, Р- номер второго нулевого элемента в массиве

73 Поиск последнего положительного элемента массива будем осуществлять аналогично в цикле, запоминая номер очередного элемента, значение которого больше нуля, в дополнительной переменной S. Учитывая тот факт, что после того, как будут просмотрены и проверены на положительность все элементы массива, в переменной S будет храниться номер последнего положительного элемента массива. На рис. 21 представлен фрагмент алгоритма поиска последнего положительного элемента в массиве А. Рис. 21. Фрагмент алгоритма поиска последнего положительного элемента Рассмотрим фрагменты алгоритма, приведенные на рис. 20 и 21. Можно заметить, что оба этих фрагмента выполняют поиск под управлением цикла, с одинаковым числом повторений, равным количеству элементов исходного массива N. Поэтому в итоговом алгоритме решения задачи примера 11 вместо композиции этих двух фрагментов в виде двух последовательных циклов можно использовать параллельное выполнение операций поиска под управлением одного цикла, который приведен на рис. 22. S=K K=N A [K] > 0 K:=1 K:=K+1

74 НАЧАЛ О Ввод N и элементов А(1.. N) K:=1, m=0 A [K]

75 Напомним, что исходный одномерный массив содержит 9 элементов: (5, 0, 4, -3, -7, 0, -2, -4, 0).По условию задачи необходимо поменять местами 2-ой нулевой элемент и последний положительный элемент. Так как задачи поиска необходимых для перестановки элементов алгоритмически решены (рис. 22), то рассмотрим задачу перестановки элементов. Для реализации перестановки найденных элементов достаточно воспользоваться управляющей структурой следования. Для того, чтобы во время перестановки не потерять переставляемые значения используем дополнительную переменную Q, временно хранящую одно из переставляемых значений элемента массива, в частности, второе нулевое значение. На рис. 23 представлен универсальный алгоритм перестановки двух элементов одномерного массива, имеющих порядковые номера P и S. Q: =A [P] A [P]: =A [S] A [S]: =Q Рис. 23. Фрагмент перестановки двух элементов массива, с номерами S и P Подводя итог для алгоритмического решения примера 11, приведем на рис. 24 алгоритм для вывода элементов преобразованного массива после перестановки найденных элементов.

76 + Начал о K=1 K< =9 Вывод А(к) К=К+1 Конец Рис. 24. Алгоритм вывода элементов массива Таким образом, процесс проектирование первоначального алгоритма перестановки второго нулевого элемента и последнего положительного элемента в одномерном массиве завершен. Полученный алгоритм представлен на рис.25. Следует заметить, что целью решения примера 11 было показать процесс нисходящего проектирования алгоритма " сверху-вниз " с использованием декомпозиции и метода структурной алгоритмизации. Отметим, что с целью упрощения в полученном алгоритме не рассматриваются ситуации, когда в составе элементов массива отсутствуют положительные значения или нулевые значения в количестве большем одного.

77 Рис.25. Алгоритм перестановки второго нулевого и последнего положительного элемента в одномерном массиве НАЧАЛ О Ввод N и элементов А(1..N) K=1, m=0 A [K]

78 Для проверки правильности работы полученного алгоритма составим таблицу трассировки для одномерного массива из 9 элементов: (5, 0, 4, -3, -7, 0, -2, -4, 0), приведенных в примере 11. Напомним, что заполнение таблицы происходит по строкам. Считаем, что все начальные значения числовых переменных равны 0. В таблице 3 выполнена трассировка фрагмента поиска второго нулевого и последнего положительного элементов (их номеров), а в таблице 4 выполнена трассировка следующего фрагмента алгоритма по перестановке в массиве найденных элементов, где K- текущий номер элемента, A[K] - текущее значение элемента массива, М- количество нулей, обнаруженных в массиве при анализе очередного элемента, P- номер второго нулевого элемента массива, S- номер последнего положительного элемента массива, A[S] - значение последнего положительного элемента массива, A[P] - значение второго нулевого элемента массива. Таблица 3.Таблица трассировки операций Таблица 4. Таблица трассировки поиска второго нулевого элемента и перестановки найденных элементов последнего положительного массива.

79 КВходной массив А(К) MМ=2РSA(P) А(6) QА(S) А(3) Выходной массив А(К) 150Нет Да Нет90

80 Пример 12. Составить алгоритм удаления в одномерном массиве элемента с максимальным значением. Решение. Анализ постановки задачи позволяет выделить две последовательно решаемые задачи: поиск элемента с максимальным значением и удаление этого значения из массива. Алгоритм первой задачи был рассмотрен ранее в примере 10 (рис.18). В этом алгоритме был определен номер максимального значения М, а максимальное значение определялось как А(М). Удаление элемента из массива приводит к уменьшению количества элементов массива за счет их перемещения на позицию удаляемого. Например, требуется удалить максимальное значение в массиве (2,4,13,5,7).

81 Максимальное значение в этом примере равно 13. После удаления количество элементов данного массива уменьшится на 1 и станет равным 4, а массив примет вид (2,4,5,7). Таким образом, можно сделать вывод, что для удаления элемента из массива необходимо знать его номер, например М, удаление производится путем сдвига на одну позицию влево всех следующих за удаляемым элементов А(М)=А(М+1), этот сдвиг должен осуществляться под управлением цикла. Цикл завершит свою работу, когда последний элемент массива сдвинется на место предпоследнего элемента. После приведенных рассуждений и используя алгоритмическое решение примера 10, изображенное на рис.18, составим алгоритм удаления элемента с максимальным значением из одномерного массива из N элементов (см. рис.26).

82 Рис. 26. Алгоритм удаления элемента с максимальным значением К - номер очередного элемента, М- номер элемента с максимальным значением, N-1 - уменьшенное в результате удаления одного элемента количество элементов массива А, A [K]: =A [K+1] - удаление путем сдвига влево следующих за удаляемым элементов на одну позицию. НАЧАЛ О Ввод N и элементов А(1.. N) K:=1 M:=1 A [K]>A [M] M:=K K:=K+1 K>N K=М K=N-1 Вывод N-1 элемента массива A КОНЕЦ A [K]: =A [K+1] K:=K+1

83 Задания для самостоятельного выполнения Составить визуальные циклические алгоритмы и таблицы трассировки для следующих задач обработки одномерных массивов. 1. *В одномерном массиве определить первый отрицательный элемент и его номер. Исключить из массива А1..AN пеpвый отpицательный элемент. Исключить из массива А1..AN пеpвый четный элемент, следующий за максимальным. 2. Дан массив целых чисел a1,..an.Выяснить, какая из трех ситуаций имеет место все числа a1,..an равны нулю, в последовательности a1,...,an первое ненулевое число-положительное, первое ненулевое число-отрицательное. 3. Дан массив целых чисел a1,..an.Выяснить, какая из трех ситуаций имеет место: все числа a1,..an равны нулю, в последовательности a1,...,an первое ненулевое число-положительное, первое ненулевое число-отрицательное. 4. Даны целые числа a1,..,an.Определить количество целых чисел, входящих в последовательность a1,...,an по одному разу.

84 Задания для самостоятельного выполнения Составить визуальные циклические алгоритмы и таблицы трассировки для следующих задач обработки одномерных массивов. 5. Даны действительные числа a1,..,an.Требуется найти В равное среднему арифметическому чисел a1,..,an,и наибольшее отклонение от среднего, т.е. max(/a1-b/,/a2- b/,../an-b/). 7. Дан массив действительных чисел a1,...,an.Найти максимальный элемент среди отрицательных элементов и поменять его местами с минимальным положительным. 8. *В одномерном массиве перенести в начало максимальный элемент. 9. Пеpенести в начало одномеpного массива втоpой нулевой элемент. 10. Ввести массив а1,...,а16. Получить новый массив по правилу (а1 + а16, а2+а15,...,а8+а9) Найти минимальный элемент полученного массива. 12 *В одномерном массиве перенести в конец минимальный элемент. 13. Пеpенести в хвост одномеpного массива все отpицательные элементы. 14. Пеpенести в начало одномеpного массива все нечетные элементы. 15. В одномерном массиве найти первую группу повторяющихся элементов. 16. Выполните примеры 10 и 11, реализуя ввод элементов массива в цикле, в котором производится их обработка.

85 АЛГОРИТМЫ СОРТИРОВКИ ОДНОМЕРНЫХ МАССИВОВ Под сортировкой понимают процесс перестановки объектов данного массива в определенном порядке. Целью сортировки являются упорядочение массивов для облегчения последующего поиска элементов в данном массиве. Рассмотрим основные алгоритмы сортировки по возрастанию числовых значений элементов массивов. Существует много методов сортировки массивов. В этой работе будут рассмотрены алгоритмы двух методов: модифицированного метода простого выбора и метода парных перестановок.

86 Сортировка модифицированным методом простого выбора Этот метод основывается на алгоритме поиска минимального элемента. В массиве А(1..n) отыскивается минимальный элемент, который ставится на первое место. Для того, чтобы не потерять элемент, стоящий на первом месте, этот элемент устанавливается на место минимального. Затем в усеченной последовательности, исключая первый элемент, отыскивается минимальный элемент и ставится на второе место и так далее n-1 раз пока не встанет на свое место предпоследний n-1 элемент массива А, сдвинув максимальный элемент в самый конец. Рассмотрим алгоритмическое решение задачи на примере сортировки некоторого массива значений по возрастанию. В соответствии с вышеописанным методом нам необходимо несколько раз выполнять операции поиска минимального элемента и его перестановку с другим элементом, то есть потребуется несколько раз просматривать элементы массива с этой целью. Количество просмотров элементов массива согласно описанию модифицированного метода простого выбора равно n-1, где n- количество элементов массива. Таким образом, можно сделать вывод, что проектируемый алгоритм сортировки будет содержать цикл, в котором будет выполняться поиск минимального элемента и его перестановка с другим элементом Обозначим через i - счетчик (номер) просмотров элементов массива и изобразим обобщенный алгоритм сортировки на рис.27.

87 + НАЧАЛО ВВОД А(1..n) i = 1 ПОИСК НОМЕРА МИНИМАЛЬНОГО ЭЛЕМЕНТА ПЕРЕСТАНОВКА МИНИМАЛЬНОГО ЭЛЕМЕНТА С ДРУГИМ КОНЕЦ i=i+1 ВЫВОД А(1..n) ПОСЛЕ СОРТИРОВКИ i = n-1 Рис.27. Обобщенный алгоритм сортировки массива модифицированным методом простого выбора

88 Отметим, что для перестановки элементов местами необходимо знать их порядковые номера, алгоритм перестановки элементов массива был рассмотрен ранее (см. рис. 23). Алгоритмы ввода исходного массива и вывода этого же массива после сортировки изображены на рисунках 16 и 24 соответственно. Алгоритм поиска в массиве минимального элемента и его номера будет аналогичен рассмотренному в примере 10 алгоритму поиска максимального элемента, который представлен на рис.18. Однако, в этом алгоритме будут внесены изменения. Для того, чтобы определить какие изменения следует внести рассмотрим выполнение сортировки данным методом с акцентом на поиск минимального элемента на конкретном примере. Пусть исходный массив содержит 5 элементов (2,8,1,3,7). Количество просмотров согласно модифицированному методу простого выбора будет равно 4. Покажем в таблице 5, как будет изменяться исходный массив на каждом просмотре. Таблица 5. Пример сортировки Номер просмотра массива i Исходный Массив Минимальный Элемент Переставляемый элементМассив после перестановки НомерЗначениеНомерЗначение 1(2,8,1,3,7)3112(1,8,2,3,7) 21,(8,2,3,7)32281,(2,8,3,7 31,2,(8,3,7)43381,2,(3,8,7) 41,2,3,(8,7)57481,2,3,7,8

89 Введем следующие обозначения : К- номер минимального элемента, J - номер элемента массива, М и А(К)- одно и тоже значение минимального элемента массива, i - номер переставляемого с минимальным элемента, А(i)- значение переставляемого элемента. Тогда циклический алгоритм сортировки модифициро­ванным методом простого выбора будет выглядеть следующим образом (рис.28). Из данных, приведенных в таблице 5, следует, что поиск минимального значения в массиве на каждом просмотре осуществляется в сокращенном массиве, который сначала начинается с первого элемента, а на последнем просмотре массив, в котором ищется минимальный элемент начинается уже с четвертого (или n-1) элемента. При этом можно заметить, что номер первого элемента массива для каждого поиска и перестановки совпадает с номером просмотра i.

90 Рис.28. Алгоритм сортировки массива модифицированным методом простого выбора В этом алгоритме два цикла, внутренний цикл выделен цветом. + + ВВОД N, A(N) A( J ) < М I N - 1 КОНЕЦ К := I J := K + 1 M := A(J) J := J + 1 J N К := J A(I ) := M I := I + 1 M := A(I) I := 1 НАЧАЛО ВЫВОД N A(N) +

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

92 + ВВОД N, A(N) A(K) A(K+1) Q := A(K), A(K) := A(K+1) A(K+1) := Q K := K + 1 K N НАЧАЛО B := 0 K := 1 B := B + 1 K = 0 ВЫВОД А(1..n) КОНЕЦ + Рис.29. Алгоритм сортировки методом парных перестановок содержит два цикла, внутренний цикл выделен цветом

93 Задания для самостоятельного выполнения Составить визуальные циклические алгоритмы и таблицы трассировки для следующих задач сортировки одномерных массивов. 1.Ввести массив a1,a2,...,a15. Расположить ненулевые элементы по убыванию. 2.Ввести массив x1,x2,...,x20. Элементы, на нечетных местах, расположить в порядке возрастания, а на нечетных в порядке убывания. 3.Ввести массив a1,a2,...,a15. Требуется упорядочить его по возрастанию абсолютных значений элементов 4.Ввести массив x1,x2,...,x20. Требуется расположить отрицательные элементы в порядке убывания.

94 АЛГОРИТМЫ ОБРАБОТКИ УПОРЯДОЧЕННЫХ МАССИВОВ Рассмотренные выше алгоритмы сортировки считаются одними из важнейших процедур упорядочивания структурированной данных, хранимых в виде массивов. Одной из главных целей задач сортировки массивов является облегчение их дальнейшей обработки, так как для упорядоченных данных разработаны эффективные методы поиска и обновления. Так, например, поиск минимального или максимального значения в упорядоченном массиве сводится к выборке первого или последнего элемента массива. Рассмотрим некоторые алгоритмы обработки упорядоченных массивов.

95 Поиск элементов в упорядоченном массиве Задача поиска значения Х в упорядоченном по возрастанию значений массиве A(1) Х, то все элементы, имеющие номера с S по n также больше Х в силу упорядоченности массива по возрастанию значений. Поэтому для дальнейшего поиска половину значений массива можно исключить из рассмотрения. В первом случае - левую, во втором случае - правую половину. Рассмотрим пример. Допустим, что требуется определить совпадает ли значение Х=12 с каким-либо элементом в упорядоченном массиве А и если совпадает, то определить порядковый номер S этого элемента. Иллюстрация применения метода бинарного поиска для поиска элемента Х=12 в массиве (2,3,4,6,10,12,20,30,35,45) приведена на рис. 30. Рис.30. Иллюстрация применения метода бинарного поиска Элементы массива А (2,3,4,6,10,12,20,30,35,45). Номера элементов Первое деление S=5, А(5)=10 А(5)Х), исключаем правую половину. Элементы массива А (2,3,4,6,10,12,20,30,35,45). Номера элементов Третье деление S=6, А(6)=12 А(6)=Х), элемент Х=12 найден.

96 Рис.31.Алгоритм поиска методом бинарного поиска НАЧАЛО ВВОД N,X A(1..N) P=1, Q = N Р< Q S=(P+Q) DIV 2 КОНЕЦ A(S)=X A(S)

97 Задания для самостоятельного выполнения Составить визуальные циклические алгоритмы для следующих задач обработки упорядоченных одномерных массивов. 1.Ввести упорядоченный по неубыванию массив Х(1) < = Х(2) < =…Х(n). Найти количество различных чисел среди элементов этого массива. 2.Ввести два упорядоченных по возрастанию числовых массива Х(1)

98 АЛГОРИТМЫ ОБРАБОТКИ ОДНОМЕРНЫХ СИМВОЛЬНЫХ МАССИВОВ Одномерные символьные масивы - это массивы, составленные из определенной последовательности символов, которые образуют тексты. Основными операциями, выполняемыми над текстами, являются операции по определению слов, выделению слова с максимальной длиной, удаление и перестановка слов,сортировка по алфавиту и др. Для простоты будем считать, что символьный массив представляет одну строку произвольного текста, слово - любую последовательность подряд идущих символов не содержащую пробела. Пробел - это специальный символ, используемый для отделения слов, он не может располагаться перед первым словом. Учитывая все эти допущения можно предложить для решения задачи определения количества слов использовать подсчет количества элементов массива, равных пробелу минус 1. Рассмотрим алгоритмическое решение распространенной задачи определения в массиве символов слова с максимальной длиной. Пусть исходный массив А содержит N символов. Для определения слова с максимальной длиной будем использовать сравнение длины текущего слова М с длиной предыдущего слова МАХ. Длина слова определяется как содержащееся в нем количество символов. Для того, чтобы вывести слово с максимальной длиной, необходимо запомнить номер элемента S, с которого начинается это слово. Алгоритм поиска в символьном массиве слова с максимальной длиной приведен на рис. 32, а его таблица трассировки для массива (Дул теплый ветер)- в таблице 6.

99 Рис. 32.Алгоритм поиска в символьном массиве слова с максимальной длиной

100 Таблица 6. Таблица трассировки алгоритма поиска слова с максимальной длиной при N= 16 в тексте : "Дул теплый ветер "

101 Рассмотрите результат, приведенный в таблице 6, для конкретного входного символьного массива "Дул теплый ветер" без последнего столбца. Однако, после выполнения приведенного на рис. 32 алгоритма для предложения "Дул теплый ветер" будет выведено слово из 7 символов, начинающихся с пробела :" теплый". Значит, формулу определения номера символа S = K-1, с которого начинается слово с максимальной длиной, следует изменить на S = K. При этом надо будет изменить содержание блока вывода результата: вместо A( S -MАХ), … A(S) следует использовать A( S -MАХ), … A(S-1). Таким образом, таблица трассировки показала наличие ошибок в алгоритме, изображенном на рис. 32. После внесения изменений этот алгоритм будет работать правильно (см. модернизированный алгоритм поиска в символьном массиве слова с максимальной длиной на рис. 33).

102 Задания для самостоятельного выполнения Составить визуальные циклические алгоритмы для следующих задач обработки символьных одномерных массивов. 1.Найти и вывести слово, содержащее наибольшее количество гласных букв. 2.В слове, в котором обнаружено наибольшее количество шипящих букв, заменить их на символ "*". 3.Вывести все гласные буквы, содержащиеся в слове наибольшей длины и вывести число повторений каждой этой буквы. 4.Подсчитать количество слов и количество символов во всех словах, отличных от заглавных латинских букв. 5.Вывести все слово, содержащее наибольшее количество цифр и вывести число цифр в каждом слове. Слово с минимальной длиной удалить из данного предложения. В предложении перенести в его конец все, встречающиеся в тексте цифры. В предложении расставить все слова в алфавитном порядке.

103 АЛГОРИТМЫ ОБРАБОТКИ ДВУМЕРНЫХ МАССИВОВ Двумерный массив - это структура однотипных элементов, расположенных в виде таблицы значений. Такое представление значений соответствует математическому понятию двумерный массив. Каждый элемент в двумерном массиве идентифицируется номером строки и номером столбца, на пересечении которых он расположен. Например, в двумерном массиве А, изображенном на рис. 34, элемент со значением 5 расположен на пересечении третьей строки и второго столбца. Этот элемент будет обозначаться как А(3,2). А элемент А(1,4) имеет значение, равное нулю. Такое представление набора значений позволяет выполнять обработку как отдельных значений в двумерном массиве, так и последовательности значений, расположенных в строках или столбцах.

104 АЛГОРИТМЫ ОБРАБОТКИ ДВУМЕРНЫХ МАССИВОВ В дальнейшем будем считать, что для двумерного массива A(N,М) в обозначении элемента А(i,j) первое значение i соответствует номеру строки и изменяется от1 до N, а j - номеру столбца и изменяется от 1 до М. В отличие от одномерного массива, в котором использовался только один номер для определения местоположения элемента и требовался только один цикл для ввода элементов, в двумерном массиве для обработки элеменов необходимы два вложенных друг в друга цикла. Внешний цикл предназначен для изменения номера строки i, а второй, внутренний, - для изменеия номера столбца j в текущей строке i.

105 На рис. 35 представлен простой алгоритм ввода элементов, построенный в виде структуры из вложенных циклов. Рис. 35. Алгоритм ввода элементов двумерного массива

106 При рассмотрении в дальнейшем алгоритмов обработки элементов двумерного массива в целях сокращения их размера фрагмент ввода элементов будем заменять отдельным блоком ввода. Пример 13. Составить алгоритм поиска максимального значения в двумерном массиве Решение. Поиск максимального элемента в двумерном массиве осуществляется аналогично поиску в одномерном массиве. Отличие состоит в том, что для обработки двумерного массива используем вложенный цикл. Обозначим максимальный элемент переменной МАХ. Значение этой переменной будет меняться на каждой итерации цикла, если очередной значение элемента массива окажется больше МАХ (см. рис.36). Рис.36. Алгоритм поиска максимального значения в двумерном массиве

107 Пример 14. Составить алгоритм вычисления количества нечетных элементов в каждой строке двумерного массива Решение. Для определения нечетных элементов будем использовать проверку на нечетность A[ I,J] mod 2 0, для подсчета количества нечетных значений - формулу К=К+1и вывод значения К столько раз, сколько строк в массиве. Алгоритм решения представлен на рис. 37. Рис.37. Алгоритм вычисления в каждой строке двумерного массива количества нечетных элементов

108 Рис.38. Алгоритм вычисления суммы элементов двумерного массива, расположенных выше главной диагонали

109 Пример 15. Составить алгоритм вычисления суммы элементов двумерного массива А(1.. N, 1..М), расположенных выше главной диагонали. Решение. Для определения условия расположения элементов выше главной диагонали рассмотрим двумерный массив в обобщенном виде на рис. 38. Обратим внимание на диагональные элементы: номер строки и номер столбца совпадают. Значит для определения элементов на главной диагонали достаточно использовать условие I=J, где I- номер строки, J -номер столбца. Для определения элементов выше главной диагонали достаточно использовать условие I J. По условию задачи нам требуется найти сумму элементов двумерного массива А(1.. N, 1..М), расположенных выше главной диагонали, значит применим условие I

110 Задания для самостоятельного выполнения 1.Составить визуальные циклические алгоритмы для следующих задач обработки двумерных массивов. 2.Ввести двумерный массив А(N,M).Составить визуальный алгоритм замены всех нулевых элементов на минимальный элемент. 3.Ввести двумерный массив А(N.N). Составить визуальный алгоритм подсчета среднего арифметического значений двумерного массива. Найти отклонение от среднего у элементов первой строки. 4.Ввести двумерный массив А(N,N). Составить визуальный алгоритм подсчета среднего арифметического значения двумерного массива. Вычислить отклонение от среднего для всех элементов двумерного массива. 5.Ввести двумерный массив А(N,N).Составить визуальный алгоритм замены всех отрицательных элементов на среднее арифметическое значение элементов двумерного массива. 6.Составить визуальный алгоритм нахождения числа строк двумерного массива А(N,N), количество отрицательных элементов в которых больше Р. 7.Ввести двумерный массив размером 7*4. Найти наибольший элемент двумерного массива. Удалить строку с максимальным элементом. 8.Ввести двумерный массив размером 7*4. Поменять столбец с максимальным элементом с первым столбцом двумерного массива. 9.Ввести двумерный массив размером 7*7. Найти максимальный элемент двумерного массива, расположенный ниже побочной диагонали. 10.Ввести двумерный массив размером 7*4. Найти наименьший элемент двумерного массива. Перенести строку, содержащую этот элемент в конец. 11.Ввести двумерный массив размером 7*4.Найти максимальный элемент двумерного массива. Поменять столбец, содержащий этот элемент с последним столбцом двумерного массива. 12.Ввести двумерный массив размером 6*4.Найти минимальный элемент двумерного массива. Переставляя строки и столбцы, добиться того, чтобы он оказался в правом нижнем углу.

111 Рекурсия Одним из самых известных и популярных методов разработки алгоритмов является рекурсия (в западной литературе рекурсию часто называют методом «разделяй и властвуй»). Она представляет собой мощный, эффективный и в тоже время изящный и элегантный способ решения задач. В информатике рекурсия используется как практически ориентированное знание - некий мощный и изящный инструмент для реальных вычислений. Понятие рекурсии не является сложным для начального понимания и не связано со знанием какого- либо определенного формализма или специальной нотации. Под рекурсией понимают прием последовательного сведения решения некоторой задачи к решению совокупности более простых задач такого же класса и получению на этой основе решения исходной задачи. Иногда на рекурсию смотрят как на наличие в определении объекта ссылки на сам объект. Или, в более общем случае, как на наличии в определениях упорядоченного мно­жества объектов последовательности ссылок друг на друга, замыкающихся на начальный объект. В программировании это выражается в построении программ (процедур или функций), которые при выполнении обращаются сами к себе непосредственно или через цепочку других программ. Кажущаяся при этих самовызовах или последовательных циклических вызовах видимость порочного круга не более чем иллюзия. Во многих конкретных случаях простыми рассуждениями путем отслеживания значений одной или нескольких управляющих величин удается провести доказательство завершимости вычислений за конечное число шагов. Алгоритм называется рекурсивным, если в его определении содержится прямой или косвенный вызов этого же алгоритма. Вычисления, проводимые с помощью рекурсивных алгоритмов (процедур, функций) называют рекурсивными. Различают два основных вида рекурсии: прямая и косвенная. Под прямой рекурсией понимается непосредственный вызов алгоритма (функции, процедуры) F из текста самого алгоритма F. При косвенной рекурсии мы имеем циклическую последовательность вызовов нескольких алгоритмов F1, F2, …, Fk (функций, процедур) друг друга: F1 вызывает F2, F2 вызывает F3, …, Fk вызывает F1 (k>1).

112 Рекурсивная триада А.Р Есаяном предложена схема решения задач с помощью рекурсии, основным компонентом которой является рекурсивная триада, состоящая из трех основных этапов: параметризация, выделение базы (или выделение начальной базы и правил её изменения), декомпозиция. Параметризация задачи заключается в выявлении совокупности исходных величин, определяющих постановку и решение задачи. Значения этих параметров или некоторых из них влияют на трудоемкость решения задачи. Иногда бывает полезно ввести в рассмотрение дополнительные параметры, напрямую с постановкой задачи не связанные, но помогающие организовать рекурсию. Выделение базы – поиск одной или нескольких подзадач, которые могут быть решены непосредственно без рекурсивного вызова. Если база будет меняться в процессе вычислений, то должен быть указан алгоритм её изменения. Как правило, подобная динамическая база расширяется за счет получения решений промежуточных задач и облегчает выполнение процесса отложенных вычислений. Возможно и сужение рекурсивной базы. Декомпозиция общего случая есть процесс последовательного разложения задачи на серию подзадач двух типов: тех, которые мы решать умеем и тех, которые в чем-то аналогичны исходной задаче. В последнем случае каждая из полученных подзадач должна быть упрощенным вариантом предыдущей задачи.

113 Рекурсивная триада При этом декомпозицию следует осуществлять так, чтобы можно было доказать, что при любом допустимом наборе значений параметров рано или поздно она приведет нас к одному из выделенных тривиальных случаев, то есть к базе. Декомпозиция обычно предполагает наличие некоторых вычислений, предшествующих и способствующих переходам к более простым подзадачам. Их удобно называть предварительными вычислениями. Область применения рекурсии достаточно широка это задачи поиска, сортировки, задачи, использующие алгоритм Евклида и его обобщения, задачи связанные с получением различного рода перестановок, а также генерация случайных чисел. При использовании рекурсии следует учитывать следующую особенность: подзадачи, получившиеся в процессе разбиения, не должны повторяться или частично перекрываться друг с другом. Если последнее условие не выполняется (то есть задачи повторяются), то использование рекурсии, в данном случае, будет неэффективным (классическим примером является вычисление чисел Фибоначчи на основе рекуррентного соотношения).

114 Жадные алгоритмы Рассмотрим небольшую задачу. Допустим, что у нас есть монеты достоинством 25, 10, 5 копеек и 1 копейка и нужно вернуть сдачу 63 копейки. Почти не раздумывая, мы преобразуем эту величину в две монеты по 25 копеек, одну монету в 10 копеек и три монеты по одной копейке. Нам не только удалось быстро определить перечень монет нужного достоинства, но и, по сути, мы составили самый короткий список монет требуемого достоинства. Данный алгоритм заключал­ся в выборе монеты самого большого достоинства (25 копеек), но не больше 63 копе­ек, добавлению ее в список сдачи и вычитанию ее стоимости из 63 (получается 38 копеек). Затем снова выбираем монету самого большого достоинства, но не больше остатка (38 копеек): этой монетой опять оказывается монета в 25 копеек. Эту монету мы опять добавляем в список сдачи, вычитаем ее стоимость из остатка и т.д. Этот метод внесения изменений называется «жадным» алгоритмом. На каждой от­дельной стадии «жадный» алгоритм выбирает тот вариант, который является локально оптимальным в том или ином смысле. Обратите внимание, что алгоритм для опреде­ления сдачи обеспечивает в целом оптимальное решение лишь вследствие особых свойств монет. Следует подчеркнуть, что не каждый «жадный» алгоритм позволяет получить оп­тимальный результат в целом. Как нередко бывает «жадная стратегия» подчас обеспечивает лишь сиюминутную выгоду, в то время как в целом результат может оказаться неблагоприятным. Существуют задачи, для которых ни один из известных «жадных» алгоритмов не позволяет получить оптимального решения; тем не менее имеются «жадные» алго­ритмы, которые с большой вероятностью позволяют получать «хорошие» решения. Нередко вполне удовлетворительным можно считать «почти оптимальное» решение, характеризующееся стоимостью, которая лишь на несколько процентов превышает оптимальную. В таких случаях «жадный» алгоритм зачастую оказывается самым бы­стрым способом получить «хорошее» решение. Вообще говоря, если рассматриваемая задача такова, что единственным.способом получить оптимальное решение является использование метода полного поиска, тогда «жадный» алгоритм или другой эври­стический метод получения хорошего (хотя и необязательно оптимального) решения может оказаться единственным реальным средством достижения результата.

115 Как узнать, даст ли жадный алгоритм оптимум применительно к данной задаче? Общих рецептов тут нет, но существуют две особенности, характерные для задач, решаемых жадными алгоритмами. Это принцип жадного выбора и свойство оптимальности для подзадач. Говорят, что к оптимизационной задаче применим принцип жадного выбора, если последовательность локально оптимальных (жадных) выборов дает глобально оптимальное решение. Различие между жад­ными алгоритмами и динамическим программированием можно пояснить так: на каждом шаге жадный алгоритм берёт «самый жирный кусок», а потом уже пытается сделать наилучший выбор среди оставшихся, каковы бы они ни бы­ли; алгоритм динамического программирования принимает решение, просчитав заранее последствия для всех вариантов. Как доказать, что жадный алгоритм даёт оптимальное решение? Это не всегда тривиально, но в типичном случае такое доказательство строится по следующей схеме. Сначала мы доказываем, что жадный выбор на первом шаге не закрывает пути к оптимальному решению: для всякого решения есть другое, согласованное с жадным выбором и не худ­шее первого. Затем показывается, что подзадача, возникающая после жадного выбора на первом шаге, аналогична исходной, и рассуждение завершается по индукции.

116 Говоря иными словами, решаемые с помощью жадных алгоритмов задачи обладают свойством оптимальности для подзадач: оптимальное решение всей задачи содержит в себе оптимальные решения под­задач. (С этим свойством мы уже встречались, говоря о динамическом програм­мировании.) И жадные алгоритмы, и динамическое программирование основываются на свойстве оптимальности для подзадач, поэтому может возникнуть искушение применить динамическое программирование в ситуации, где хватило бы жадного алгоритма, или, напротив, применить жадный алгоритм к задаче, в которой он не даст оптимума. Мы проиллюстрируем возможные ловушки на примере двух вариантов классической оптимизационной задачи.Дискретная задача о рюкзаке состоит в следующем. Пусть вор пробрался на склад, на котором хранится п вещей. Вещь номер i стоит vi долларов и весит wi килограммов (vi и wi целые числа). Вор хочет украсть товара на максимальную сумму, причём максимальный вес, который он может унести в рюкзаке, равен W (число W тоже целое). Что он должен положить в рюкзак?Непрерывная задача о рюкзаке отличается от дискретной тем, что вор может дробить краденые товары на части и укладывать в рюкзак эти части, а не обязательно вещи целиком (если в дискретной задаче вор имеет дело с золотыми слитками, то в непрерывной с золотым песком).

117 Обе задачи о рюкзаке обладают свойством оптимальности для подзадач. В самом деле, рассмотрим дискретную задачу. Вынув вещь номер j из оптималь­но загруженного рюкзака, получим решение задачи о рюкзаке с максимальным весом W wj и набором из п 1 вещи (все вещи, кроме j-й). Аналогичное рассуждение проходит и для непрерывной задачи: вынув из оптимально загру­женного рюкзака, в котором лежит w килограммов товара номер j, весь этот товар, получим оптимальное решение непрерывной задачи, в которой максимальный вес равен W w (вместо W), а количество j-ro товара равно wj w (вместо wj). Хотя две задачи о рюкзаке и похожи, жадный алгоритм даёт оптимум в непрерывной задаче о рюкзаке и не даёт в дискретной. В самом деле, решение непрерывной задачи о рюкзаке с помощью жадного алгоритма выглядит так. Вычислим цены (в расчёте на килограмм) всех товаров (цена товара номер i равна vi/wi). Сначала вор берёт по максимуму самого дорогого товара; если весь этот товар кончился, а рюкзак не заполнен, вор берёт следующий по цене товар, затем следующий, и так далее, пока не наберёт вес W. Поскольку товары надо предварительно отсортировать по ценам, на что уйдёт время O(n logn), время работы описанного алгоритма будет O(n logn). Убедимся в том, что аналогичный жадный алгоритм не обязан давать оптимум в дискретной задаче о рюкзаке. Грузоподъёмность рюкзака 50 кг, на складе имеются три вещи, весящие 10, 20 и 30 кг и стоящие 60, 100 и 120 долларов соответственно. Цена их в расчёте на единицу веса равна 6, 5 и 4. Жадный алгоритм для начала положит в рюкзак вещь номер 1; однако оптимальное решение включает предметы номер 2 и 3.

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

119 Этапы полного построения алгоритма Введение Постановка задачи Разработка модели Построение алгоритма Проверка правильности алгоритма Анализ алгоритма Программная реализация алгоритма

120 Введение Любая человеческая деятельность, направленная на получение, обработку, накопление информации непосредственно связана с реализацией (зачастую неосознанно) соответствующего алгоритма и требует рассмотрения общих стадий построения алгоритма решения прикладных задач. На основе работ А. Ахо, C. Гудмана], Д. Кнута, А.Р. Есаяна, Т. Кормена, Ч. Лейзерсона, Р. Ривеста, А.Г. Кушниренко, Г.В. Лебедева, М.П. Лапчика, и других авторов в процессе полного построения алгоритма можно выделить следующие основные этапы: 1) постановка задачи; 2) разработка модели; 3) построение алгоритма; 4) проверка правильности алгоритма; 5) анализ алгоритма; 6) программная реализация алгоритма. Каждый из перечисленных шагов в реальных условиях может присутствовать самостоятельно или входить в состав соседних с ним этапов в зависимости от конкретной задачи и навыков пользователя. Рассмотрим вышеперечисленные этапы и определим назначение каждого из них.

121 Постановка задачи Наличие точной формулировки задачи является одной из. Стадия постановки задачи в некоторых случаях (когда формулировка не разработана кем-то другим) требует необходимых составляющих ее правильного понимания и решения. В случае неточной, непонятной формулировки затрудняется понимание смысла задачи, становится невозможным выделение системы входных данных и необходимого результата весомых творческих затрат, что подтверждается известным математическим афоризмом: «Поставить задачу труднее, чем решить ее». Можно предложить определенный круг вопросов, помогающих более точно понять смысл задачи, уточнить ее формулировку: - Все ли термины, используемые в предварительной формулировке, понятны и адекватно используются? - Является ли система входных данных полной? - Что требуется найти? - Какие существуют подходы к определению решения данной задачи? - Какие сделаны допущения в предварительной формулировке и насколько они обоснованы? В зависимости от конкретной задачи приведенная система вопросов может расширятся. После получения частичных или полных ответов на поставленные вопросы следует провести повторный анализ и, возможно, некоторые вопросы придется поставить заново.

122 Построение алгоритма После постановки задачи и построения для нее модели необходимо приступить к разработке алгоритма ее решения. Выбор метода разработки, в большинстве случаев, определяется построенной моделью и может существенно повлиять на эффективность алгоритма решения. Несколько различных алгоритмов могут быть правильными, но, в то же время, значительно отличаться по эффективности (понятие и критерии эффективности будут рассмотрены ниже). Для построения «хорошего» алгоритма необходим тщательный анализ построенной модели и ее ограничений. Следует отметить, что среди начинающих (и не только) программистов существует тенденция уделять разработке алгоритма при создании программы необоснованно меньше времени, чем на собственно создание программы. Опыт преподавания дисциплины «Программирование» на факультете Математики и информатики Тульского государственного педагогического университета позволяет утверждать, что в большинстве случаев студенты недооценивают стадию построения алгоритма и стремятся как можно быстрее перейти к написанию программы. Для некоторых достаточно простых задач такой подход во многом оправдан, но более серьезные требуют тщательного продумывания алгоритма, лежащего в их основе. В конечном итоге это приводит к отождествлению понятий «программирование» и «набор программы» и невозможности дальнейшей отладки полученной программы.Стадия разработки предполагает тщательное продумывание идеи алгоритма, базирующейся на двух предыдущих этапах. Существует несколько основных методов разработки алгоритмов: рекурсия, перебор с возвратом, динамическое программирование, жадные алгоритмы, генетические алгоритмы.

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

124 Анализ алгоритма Прежде чем приступить к реализации алгоритма для конкретной аппаратной платформы, следует провести оценку времени работы и объема требуемой памяти. Вполне вероятна ситуация, что для решения относительно простой задачи потребуются часы, дни и даже годы машинного времени. Анализ алгоритмов представляет собой раздел информатики, занимающийся выводом количественной информации об эффективности компьютерных методов. Каждое реальное вычисление характеризуется : 1. определенной длительностью, физическим временем выполнения (время); 2. объемом требуемой памяти, физическим пространством (емкость); Традиционно значения времени и емкости выражают целыми числами. Анализ алгоритмов предлагает общие количественные критерии не только для оценки характеристик данного алгоритма, но и для относительного сравнения двух различных алгоритмов решения одной задачи. Под временной сложностью алгоритма (временем выполнения алгоритма) понимается время выполнения алгоритма, измеряемое в «шагах» (инструкциях алгоритма), которые необходимо выполнить для достижения запланированного результата на некоторой идеализированной вычислительной машине

125 Пусть - алгоритм решения некоторого класса задач, и определяет размерность входных данных (количество элементов массива, число вершин графа и т.п.). Определим как время выполнения алгоритма в зависимости от входных данных. Временная сложность алгоритма характеризуется степенью роста. В большинстве случаев невозможно дать абсолютную оценку для числа шагов, требуемых для выполнения алгоритма. Точное число шагов может быть определено только для конкретной реализации обычно рассматривают как время выполнения алгоритма в наихудшем случае (как максимум времени выполнения по всем входным данным размера ). Иногда рассматривают величину как среднее в статистическом смысле время выполнения по всем входным данным размера.Следует отметить, что задача определения среднего времени выполнения гораздо сложнее нахождения времени выполнения в наихудшем случае, кроме того понятие «средних» данных имеет достаточно расплывчатое определение, поэтому на практике чаще всего используют величину. Говорят, что алгоритм полиномиальный, если растет не быстрее, чем полином некоторой степени от (при алгоритмы называют линейными), в противном случае, выделяют экспоненциальную сложность. Если перед нами стоит задача определения максимального элемента линейного массива длины, то временная сложность такого алгоритма потребует сравнений, здесь время выполнения не зависит от входных данных. Однако в большинстве случаев существенно зависит от структуры начальных условий. Для оценки времени выполнения применяется асимптотическая символика. В 1894 г. П. Бахман предложил использовать символ для описания степени роста функций. Говорят, что имеет порядок если. Константу пропорциональности можно достаточно точно определить только для конкретной реализации алгоритма. Про алгоритмы, имеющие временную сложность, говорят, что они имеют порядок (степень) роста.

126 Рассмотрим усредненный объем памяти, необходимый для хранения базовых скалярных типов данных в байтах. Положим =2 (для целочисленных типов); =4 (для вещественных типов); = (для строковых типов, где максимальная длина строки). Массив, состоящий из элементов имеет размер, где размер скаляра. Пусть алгоритм имеет систему входных данных. Кроме того, для решения задачи требуется система вспомогательных данных. Введем в рассмотрение величину равную усредненному объему памяти, необходимому для хранения всех величин, участвующих в вычислительном процессе. Итак, мы рассмотрели основные характеристики алгоритма: время и емкость. Введение понятий временной сложности алгоритма и усредненного объема памяти, необходимого для реализации алгоритма, позволяет нам перейти к рассмотрению понятия эффективности алгоритма. Пусть имеется некоторая вычислительная машина, выполняющая операций в секунду, несколько алгоритмов с различной временной сложностью и структура данных размера. Рассмотрим время работы данной машины: Из таблицы можно видеть, что вычисления, определяемые алгоритмами (7) и (8), вряд ли закончатся в обозримом будущем. Очень характерным является временной скачок между шестым и седьмым алгоритмами. Согласно эффективным алгоритмом решения частной задачи называется такой алгоритм для которого доказана правильность и получена линейная или полиномиальная оценка временной сложности. Такие алгоритмы еще называют вычислимыми за реальное время. В общем случае имеется широкий класс задач, для которых не существует точных эффективных методов решения. К сожалению многие из таких задач имеют важное прикладное значение. Для них разрабатываются приближенные алгоритмы, позволяющие получить решение с определенной степенью точности или с определенной вероятностью.

127 Программная реализация алгоритма После того, как алгоритм разработан, доказана его правильность и проведен анализ, можно приступить к реализации алгоритма, т.е. созданию программы для ЭВМ. В целом, сложность этого этапа может быть довольно высокой, поскольку не всякий шаг алгоритма может быть напрямую выражен в конструкциях некоторого языка программирования. В некоторых случаях один из шагов алгоритма требует написания отдельной программы, в других необходимо создать сложную структуру вспомогательных данных, исходя из выбранной модели. Следует отметить, что из правильности алгоритма вовсе не следует правильность программы, созданной на основе этого алгоритма. Отладка и тестирование программы. Отладка программы предполагает устранение синтаксических и логических ошибок для получения полнофункционального варианта. Тестирование программы разбивается на две стадии: аналитическую и экспериментальную]. Аналитическая стадия предполагает доказательство правильности программы, которое можно провести аналогично доказательству правильности алгоритма. Экспериментальная проверка заключается в прогонке программы на различного рода тестах, результат которых точно известен. Система тестов должна быть построена таким образом, чтобы охватить все ветви и состояния алгоритма и вариации входных данных. В случае больших программ, состоящих из набора модулей, тестируется каждый модуль в отдельности, а затем проводится комплексное тестирование. Составление документации. Данный этап предполагает составление описания алгоритма, необходимых входных данных, а также инструкцию пользователя, раскрывающую механизм взаимодействия конечного потребителя с интерфейсом программы. Рассмотренная структура этапов полного построения алгоритма не является жестко обусловленной и детерминированной. В процессе решения прикладных задач отдельные этапы могут сливаться в один. Кроме того, возможно более детальное структурирование каждого из предложенных этапов. Несомненным является тот факт, что создание эффективных алгоритмов невозможно без серьезной методологической основы, которую дает теория построения и анализа алгоритмов. Анализ алгоритмов, безусловно, является необходимым средством для обеспечения обратной связи между целями, поставленными в процессе решения некоторой задачи, и конечным результатом в виде алгоритма, программы, последовательности операций.

128 Основные правила анализа алгоритмов Анализ базовых алгоритмических конструкций Решение реккурентных соотношений

129

130

131

132

133

134

135

136