Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







Понятие информации. Общая характеристика процессов сбора, передачи, обработки и накопления информации





Основные понятия информатики и информационных систем

 

Основные понятия информатики

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

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

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

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

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



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

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

Развитие современной науки предполагает проведение сложных и дорогостоящих экспериментов, таких, как, например, при разработке термоядерных реакторов. Информатика позволяет заменить реальные эксперименты машинными. Это экономит колоссальные ресурсы, дает возможность обработать полученные результаты самыми современными методами. Кроме того, такие эксперименты занимают гораздо меньше времени, чем настоящие. А в некоторых областях науки, например, в астрофизике, проведение реального эксперимента просто невозможно. Здесь в основном все исследования проводятся посредством вычислительных и модельных экспериментов.

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

 

 

Информационные революции

Информационная революция (англ. Information revolution) — преобразование общественных отношений в результате кардинальных изменений в сфере обработки информации. В истории развития цивилизации произошло несколько информационных революций. Следствием подобных преобразований являлось приобретение человеческим обществом нового качества.

 

Хронология информационных революций

Первая информационная революция

Началом первой информационной революции стало одно из самых важнейших изобретений человечества — письменность. Она появилась около пяти тысяч лет назад в Месопотамии и Египте, затем (независимо, но несколько тысяч лет спустя) — в Китае и ещё на 1500 лет позднее — в Центральной Америке у индейцев племени майя. Её ранние примеры — глиняные дощечки с клинописью жителей Вавилона — представляют собой деловые расписки и правительственные документы, летописи или описания методов земледелия.

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

 

Вторая информационная революция

 

Вторая информационная революция связана с появлением рукописной книги. Месяцами, а иногда и годами трудился писец, чтобы воспроизвести литературное или научное произведение на листах пергамента, изготовлявшегося из шкур животных. Удешевила книгу, сделала её более массовой бумага, её изобретателем считается китаец Цай Лунь, живший в II—I вв. до н. э. В Греции афинский тиран Писистрат (правил в 560—527 гг. до н. э. с перерывами) распорядился записать в книгу поэмы Гомера, до этого передававшиеся изустно.

Эффект рукописной книги в Китае, Древней Греции и Древнем Риме был огромным. По сути, вся китайская цивилизация и система государственного устройства основаны именно на рукописной книге. Но тиражирование письменных материалов — дорогостоящий и длительный процесс, ограничивавший круг людей, которым автор мог сообщить знания. Переписывание сказывалось и на точности передачи знаний, поскольку в ходе многократного копирования текста в него непременно вкрадывались ошибки.

 

Кодирование информации

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

Кодирование информации необычайно разнообразно. Указания водителю автомобиля по проезду дороги кодируются в виде дорожных знаков, а также специальных индикаторных устройств (светофоров и всевозможных светящихся табло около них). Музыкальное произведение кодируется с помощью знаков нотной грамоты, для записи шахматных партий и химических формул также созданы специализированные нотации (системы записи). Менее стандартными, но легко интуитивно понимаемыми являются комбинации изображений солнышка и облаков, компактно описывающие погоду. Весьма специфическую азбуку флажков придумали моряки. Устная речь человека, которая служит одним из важных каналов передачи информации, состоит из стандартного набора звуков (имеющего свои особенности для каждого национального языка) в различных сочетаниях. Любой грамотный компьютерный пользователь знает о существовании кодировок символов ASCII, Unicode и некоторых других. Правила записи чисел в десятичной системе — это тоже способ кодирования, предназначенный для произвольных чисел. Географическая карта по определенным правилам кодирует информацию о рельефе местности и относительном расположении объектов, электрическая схема или сборочный чертеж — о соединении деталей. Высота столбика термометра или отклонение стрелки амперметра на фоне нарисованной шкалы представляют данные о температуре или силе тока и т.д.

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

Теория кодирования информации является одной из дисциплин, которые входят в состав информатики. Она занимается вопросами экономичности (архивация, ускорение передачи данных), надежности (обеспечение восстановления переданной информации в случае повреждения) и безопасности (шифрование) кодирования информации.

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

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

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

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

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

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

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

Примечание. Рассмотрим такую, казалось бы, “неарифметическую” величину, как цвет, обычно представляемую в компьютере как совокупность интенсивности трех базовых цветов RGB. Тем не менее, записанные вместе, все три интенсивности образуют единое “длинное” число, которое формально вполне можно принять за номер цвета.

Значение сформулированного выше положения трудно переоценить: оно позволяет любую дискретную информацию свести к единой универсальной форме — числовой. Не случайно поэтому в последнее время большое распространение получил термин “цифровой”, например, цифровой фотоаппарат. Заметим, что для цифрового фотоаппарата важно не столько существование дискретной светочувствительной матрицы из миллионов пикселей (в конце концов “химическая” фотопленка также состояла из отдельных зерен), сколько последующая запись состояния ячеек этой матрицы в числовой форме.

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

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

 

В вычислительной технике существует своя система кодирования — она называется двоичным кодированием и основана на представлении данных последовательностью всего двух знаков: 0 и 1. Эти знаки называются двоичными цифрами, по-английски —binarydigit, или, сокращенно,bit (бит).

Одним битом могут быть выражены два понятия: 0 или 1 (да или нет, черное или белое, истина или ложь и т. п.). Если количество битов увеличить до двух, то уже можно выразить четыре различных понятия:

 

00 01 10 11

 

Тремя битами можно закодировать восемь различных значений:

 

000 001 010 01l 100 101 110 111

 

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

 

Системы счисления

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

Системы счисления весьма разнообразны. Прежде всего они делятся на позиционные и непозиционные. Позиционной называется система счисления, в которой количественный эквивалент цифры зависит от ее положения в записи числа; в противном случае система является непозиционной. Большинство используемых на практике систем позиционно, поскольку именно для них обеспечивается наиболее простая арифметика.
В частности, используемая в быту система представления чисел позиционная (сравните значение цифры 2 в записи чисел 132 и 123!). Что же касается непозиционных систем, то сюда относятся хорошо известный римский способ записи чисел, а также унарная система, с которой вы, вероятно, встречались в первом классе (вспомните счетные палочки!).

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

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

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

Кроме перечисленных достоинств, двоичная система имеет, конечно, и недостатки, среди которых в первую очередь необходимо назвать необходимость перевода данных из “человеческой” (десятичной) системы счисления в “машинную” (двоичную) и обратно, а также громоздкость записи двоичных чисел. Рассмотрим названные проблемы подробнее.

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

Частным случаем указанного выше способа является перевод из десятичной системы счисления в двоичную, который нужен, чтобы узнать представление в компьютере произвольного десятичного числа. Опуская подробности , напомним, как выглядит процесс перевода числа 20(10) в двоичный код:

Остается “собрать” итоговое двоичное число из остатков от деления, не забывая при этом, что старшие разряды получаются всегда позднее, чем младшие. В итоге получим: (20)10 = (10100)2.

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

(10100)2 = 1 x 24 + 0 x 23 + 1 x 22 + 0 x 21 + 0 x 20 =

= 16 + 4 = (20)10.

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

Обратимся теперь к проблеме громоздкости двоичного кода. Если посмотреть на двоичное число, представляющее собой представление некоторого десятичного с весьма умеренным числом цифр (например, трех- или четырехзначного числа), то обнаружится, что выглядит это чрезмерно длинно. Более того, длинная “однообразная” цепочка из нулей и единиц очень плохо воспринимается глазами. Чтобы облегчить ситуацию, для более компактной записи используется восьмеричная или шестнадцатеричная система счисления. Особенностью данных оснований является тот факт, что и 8, и 16 есть степени двойки, а значит, перевод между ними и двоичной системой максимально прост. Учитывая, что 8 = 23, а 16 = 24, получаем, что каждая восьмеричная цифра объединяет ровно 3 двоичных разряда, а шестнадцатеричная — 4.

Отсюда немедленно следует алгоритм перевода из двоичной системы в восьмеричную (шестнадцатеричную):

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

··заменить каждую из полученных групп соответствующей ей восьмеричной (шестнадцатеричной) цифрой.

Например:

110102 = 0001 1010 = 1A16.

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

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

Остается обсудить вопросы, связанные с двоичной арифметикой. Отметим, что арифметические действия в системах счисления с любыми основаниями производятся по одинаковым правилам. Единственное отличие состоит в том значении, при превышении которого возникает перенос в следующий разряд. В общепринятой десятичной системе “критическое” значение равно 10 (вспомните: “8 + 7 = 15, 5 пишем, 1 в уме”).
В двоичной системе, где нет никаких цифр, кроме 0 и 1, перенос наступает, когда в разряде получается результат, равный 2 (или больше). Нетрудно сообразить, что минимальное значение, при котором возникает перенос, равно количеству цифр и, следовательно, основанию системы счисления.

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

Сложение двух чисел в системе счисления с основанием N осуществляется поразрядно от младших разрядов к старшим (“справа налево”, если смотреть на запись числа). Когда сумма данного разряда S не превышает значения N, результат сложения является окончательным. Если же S N, то происходит перенос в старший (“более левый”) разряд, причем каждая единица переноса уменьшает значение S на величину N.

Можно сформулировать аналогичные правила и для остальных арифметических операций. После этого достаточно положить N = 2, и мы получим правила арифметики для двоичной системы.

или в десятичной системе 6 + 10 = 16

Для выполнения арифметических операций (сложение, вычитание, умножение, деление) в системе счисления с основанием P необходимо иметь соответствующие таблицы сложения и умножения. Для P = 2 таблицы представлены ниже.


 

Законы логики

Закон тождества

Всякое высказывание тождественно самому себе

А=А

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

А^!А =0

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

Аv!А =1

Закон двойного отрицания

Если дважды отрицать некоторое высказывание, то в результате получим исходное высказывание:

!!А =А

Законы де Моргана

Логические законы, связывающие с помощью отрицания высказывания, образованные с помощью союзов «и» и «или».

Отрицание дизъюнкций, есть конъюнкция отрицаний:

!(АvВ)=!А^!В


Отрицание конъюнкций, есть дизъюнкция отрицаний:

!(А^В)=!Аv!В

 

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

 

Логическое умножение Логическое сложение
А^В= В ^ А АvВ= ВvА

 

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

Логическое умножение Логическое сложение
(А^В)^С= А ^(В ^ С) (АvВ)vС= Аv(ВvС)

 

Закон дистрибутивности – каким образом раскрываются скобки при совершении сложения и умножения.

Дистрибутивность умножения относительно сложения Дистрибутивность сложения относительно умножения
ab+ac=a(b+c) – в алгебре (А^В)v(А^ С)= А ^(В v С)   (АvВ)^ (АvС)= Аv(В^С)

 

Закон идемпотентности (отсутствие степеней и коэффициентов) – сложение и умножение одних и тех же переменных равно самим переменным.

Логическое умножение Логическое сложение
А^А= А АvА= А

 

Свойства констант 0 и 1:

!0=1; !1=0; 1ÅА=!А; 0ÅА=А; АÅ!А=1

Логическое умножение Логическое сложение
А^1= А А^0= 0 Аv1= 1 Аv0= А

 

Решение логической задачи:

Определите истинность составного высказывания

(2*2=4 и 3*3=10) или (2*2=5 и 3*3=9)

1. Заменить простые высказывания логическими переменными и установить их истинность или ложность.

А: «2*2=4» - истинно (1)

В: «3*3=10» - ложно (0)

С: «2*2=5» - ложно (0)

D: «3*3=9» - истинно (1)

2. Заменить логические связи «и» и «или» операциями умножения и логического сложения. Тогда высказывание примет вид следуюшего логического выражения:

(А^В) v(С^D)

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

(1^0) v(0^1)=0 v0=0

Результат: составное высказывание ложно.

 

 

Алгоритм и его свойства

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

Алгоритмы являются объектом систематического исследования пограничной между математикой и информатикой научной дисциплины, примыкающей к математической логике - теории алгоритмов.

Само слово «алгоритм» происходит от algorithmi - латинской формы написания имени великого математика IX века аль-Хорезми, который сформулировал правила выполнения арифметических действий. Первоначально под алгоритмами и понимали только правила выполнения четырех арифметических действий над многозначными числами.

Свойства алгоритмов

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

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

2. Используемые на практике алгоритмы составляются с ориентацией на определенного исполнителя. Чтобы составить для него алгоритм, нужно знать, какие команды этот исполнитель может понять и исполнить, а какие - не может. Мы знаем, что у каждого исполнителя имеется своя система команд. Очевидно, составляя запись алгоритма для определенного исполнителя, можно использовать лишь те команды, которые имеются в его СКИ. Это свойство алгоритмов будем называть понятностью.

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

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

Отмеченное свойства алгоритмов называют определенностью или детерминированностью.

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

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

Способы записи алгоритмов

Для записи алгоритмов используют самые разнообразные средства. Выбор средства определяется типом исполняемого алгоритма. Выделяют следующие основные способы записи алгоритмов:

- вербальный, когда алгоритм описывается на человеческом языке;

- символьный, когда алгоритм описывается с помощью набора символов;

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

Общепринятыми способами записи являются графическая запись с помощью блок-схем и символьная запись с помощью какого-либо алгоритмического языка.

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

Алгоритмические структуры

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

1. Линейным называется алгоритм, в котором все этапы решения задачи выполняются строго последовательно, без пропусков и повторений. Такую алгоритмическую структуру иногда называют «следование».

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

3. Цикл предусматривает многократное повторение действий.

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

Циклические алгоритмы по способу организации выхода из цикла можно разделить на два типа – арифметические (циклы со счетчиком) и итерационные (циклы с условием).

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

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

Все алгоритмические конструкции имеют общее свойство: один вход и один выход.

Линейные алгоритмы

Понятие линейного алгоритма

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

Задача 1. Вычислить площадь прямоугольника S. Известно, что его ширина равна а, а длина в 2 раза больше ширины.

Решение.

1. Анализ условия задачи.

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

Итак, проанализировав условие задачи, делаем вывод, что исходными данными (аргументом), является ширина а прямоугольника, а выходными данными являются длина (вторая сторона) и площадь. Причем вторая сторона – назовем ее b – это промежуточный результат, а площадь – назовем ее S – это искомый результат.

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

2. Составим математическую модель решения нашей задачи. Запишем условие в виде одного предложения – найти площадь прямоугольника.

Наша задача может быть разбита на три основных этапа: ввод исходных данных, этап вычислений и вывод результатов. На первом этапе задается ширина а, на последнем этапе выводится результат – значение площади S.

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

Таким образом, решение данной задачи состоит из двух действий. Используя введенные обозначения, запишем их:

3. Учитывая все выше сказанное, составим блок-схему алгоритма нашей задачи. Она будет выглядеть как на рисунке.

4. Запишем алгоритм на алгоритмическом языке.

алг площадь прямоугольника аргВЕЩ а резВЕЩ b, S нач ввод а вывод S кон


Алгоритм ветвления (условный алгоритм)

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

На языке блок-схем ветвление может изображаться в виде как на рисунке:

 

 

Задача 3. Даны два числа А и В. Найти наибольшее из них.

1. Анализируем условие.Что дано в задаче? а) Первое число А. Это переменная, ее задает пользователь в начале алгоритма. б) Второе число В. Тоже переменная определяется в начале алгоритма. Что является результатом в этой задаче? Максимальное из этих двух заданных чисел. Обозначим эту переменную через Max. Все эти переменные относятся к классу действительных чисел.

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

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

Заметим, что эти две ситуации взаимно противоположные: либо первое число больше, либо второе. Поэтому условно можно считать, что один случай соответствует слову «да», тогда другой случай соответствует слову «нет». Может быть еще случай, когда эти числа равны между собой. Тогда оба они равны максимальному значению.

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

Этап сравнения этих чисел описывается так, как было сказано выше, если A больше, чем B, то Мах равен A, в другом случае (если B больше, чем A) Мах равен B. Запишем «русские слова» на математическом языке – язык









Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:


©2015- 2019 zdamsam.ru Размещенные материалы защищены законодательством РФ.