Неизмеримость информации в быту

Понятие информации. Виды информационных процессов. Поиск и систематизация информации. Хранение информации; выбор способа хранения информации. Передача информации в социальных, биологических и технических системах.

 

С развитием теории информации, кибернетики, информа­тики как науки понятие «информация» (от латинского infor-matio — сведения, разъяснения), наряду с понятиями «веще­ство», «энергия», «пространство» и «время» легло в основу современной научной картины мира. В то же время однозначного определения этого понятия пока не существует.

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

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

Процесс обработки информации может представлять со­бой:

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

Процесс передачи информации представляет собой со­здание копии информации на расстоянии от исходного места хранения. В процессе передачи информации обязательно участвуют источник и приемник информации. Между ними действует канал связи. В процессе передачи информация может теряться или искажаться — случайно или намеренно. На устранение этого могут быть направлены методы защиты при передаче информации. Передача информации в социальных, биологических и технических системах с точки зрения информатики осуществляется по общей схеме: источник-канал-приемник. Различие в том, что в таких системах понимают под информацией. «В социальных науках под информацией понимают сведения, данные понятия, отраженные в нашем сознании и изменяющие наши представления о реальном мире. Эту информацию, передающуюся в человеческом обществе и участвующую в формировании общественного сознания, называют социальной информацией. Инженеры, биологи, генетики, психологи отождествляют информацию с теми сигналами, импульсами, кодами, которые наблюдают в технических и биологических системах. Содержание принимаемых и обрабатываемых сигналов ин­женера не интересует» [3], а генетиков и биологов может интересовать.

 

К процессу хранения информации можно отнести:

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

 

Понятие о кодировании информации. Выбор способа представления информации в соответствии с поставлен­ной задачей. Универсальность дискретного (цифрового) представления информации. Двоичное кодирование.

 

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

В настоящее время достаточно распространен процесс ко­дирования, т. е. преобразование информации из одной зна­ковой формы в другую, удобную для ее обработки, хранения или передачи. Используемый для кодирования конечный набор знаков называют алфавитом. Кодирование осуществ­ляется по принятым правилам. Правило кодирования назы­вается кодом (от французского code — кодекс, свод зако­нов). Длина кода — количество знаков алфавита, используе­мое для кодирования.

Многие годы человечество работало с информацией, преж­де чем был изобретен компьютер. С появлением компьютера стало возможным автоматизировать процессы обработки, передачи и хранения информации. При кодировании инфор­мации для технических устройств удобно использовать ал­фавиты, состоящие всего из двух знаков. Такие алфавиты называют двоичными. Чем меньше знаков в алфавите, тем проще должна быть устроена «машина» для распознавания (дешифровки) информационного сообщения. Однако чем ме­ньше знаков в алфавите, тем большее их количество требу­ется для кодирования, следовательно, тем больше длина кода. Легко рассчитать количество М элементарных сообще­ний, которые можно закодировать, используя код постоян­ной длины п и алфавит из R знаков: М = Rⁿ. Длину кода рассчитывают по формуле n = [log_RM + 1]. Если мы исполь­зуем двоичный алфавит, то М = 2ⁿ

При конструировании компьютеров был выбран двоичный алфавит {0, 1}, что позволило использовать достаточно про­стые устройства для представления и автоматического распо­знавания программ и данных. Именно простота сделала этот принцип кодирования таким распространенным. Наряду с этим свойством двоичное кодирование обеспечивает удобство физической реализации, универсальность представления лю­бого вида информации, уменьшение избыточности сообще­ния, обеспечение защиты от случайных искажений или не­желательного доступа. Наиболее распространены кодировки компьютерных символов: ASCII, Win1251, ДКОИ-8.

 

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

 

Различные подходы к измерению количества информа­ции в сообщении определяются различием подходов к опре­делению самого понятия «информация».

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

Выделяют три подхода.

 

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

Исторический обзор. Первым дошедшим до нас алгорит­мом в его интуитивном понимании — конечной последовательности элементарных действии, решающих поставлен­ную задачу, — считается предложенный Евклидом в III веке до нашей эры алгоритм нахождения наибольшего общего де­лителя двух чисел (алгоритм Евклида). Вплоть до начала XX века само слово «алгоритм» употреблялось в устойчивом сочетании «алгоритм Евклида». Для описания пошагового решения других математических задач использовалось сло­во «метод».

Слово «алгоритм», «algorithm» происходит от имени вы­дающегося ученого IX века Мухаммеда ибн Муса ал-Хорезми (в переводе с арабского Мухаммед, сын Мусы из Хорезма). По латинскому переводу его труда (XII век) Западная Европа познакомилась с десятичной позиционной системой счисления и правилами (algorismi) выполнения в ней арифметических действий.

 

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

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

Варианты словесного определения алгоритма, принадле­жащие российским ученым-математикам А. Н. Колмогорову и А. А. Маркову:

Определение 2 (Колмогоров). Алгоритм — это всякая система вычислений, выполняемых по строго определенным правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи.

Определение 3 (Марков). Алгоритм — это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату.

 

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

• Дискретность. Алгоритм состоит из последовательных команд, только выполнив одну команду, исполнитель может приступить к выполнению следующей. То есть структура алгоритма является дискретной (прерывной).
• Конечность. Алгоритм содержит конечное количество элементарных выполнимых предписаний, т. е. удовлетворяет требованию конечности записи. Исполнитель алгоритма должен выполнять конечное количество шагов при решении задачи, т. е. алгоритм удовлетворяет требованию конечности действий.
• Точность (определенность). Каждая команда алгоритма должна определять однозначное действие исполни­теля. Этим свойством часто не обладают предписания и инструкции, которые составляются для людей.
• Понятность. Каждая команда алгоритма должна быть понятна исполнителю. Алгоритм не рассчитан на при­нятие самостоятельных решений исполнителем, не предусмотренных составителем алгоритма.
• Универсальность (массовость). Алгоритм должен быть единым для всех допустимых исходных данных. Разработка алгоритма — процесс творческий, но требующий значительных затрат времени и умственных усилий, поэтому желательно, чтобы он обеспечивал решение за­дач данного типа. Это свойство не является обязатель­ным; не менее важными являются алгоритмы уникальные, разработанные для решения одной задачи.

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

 

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

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

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

Описание в графической форме в виде блок-схемы. В схеме алгоритма каждому типу действий (ввод исходных данных, вычисление, проверка условия, управление циклом, вывод результатов, окончание) соответствует своя геометрическая фигура — блок. Блоки соединяются линиями со стрелками, указывающими последовательность действий. Форма блоков установлена ГОСТом. Внутри блока записывается содержание соответствующего действия. Совокупность блоков образует блок-схему алгоритма. (В Microsoft Office можно использовать готовые шаблоны блоков.)

 

Основные блоки, используемые при графической форме записи алгоритмов:

 

 

Описание в виде программы для компьютера на языке программирования (например, Паскаль, Бейсик, Си).

 

Языки программирования

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

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

Важным этапом в развитии программирования явилась разработка языков программирования высокого уровня (ЯПВУ) — специальных искусственных языков, приближенных к обычному разговорному языку (английскому). Примеры таких языков: FORTRAN, Basic, Pascal, С. Большинство языков высокого уровня универсальны, т. е. предназначены для решения широкого круга задач.

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

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

Компилятор — это программа, автоматически преобразующая (компилирующая) исходный код ЯПВУ в машинный код и создающая таким образом исполняемый файл. Он может быть запущен на исполнение операционной системой. В ОС Microsoft такие файлы могут иметь расширения ехе, com, dll.

Интерпретатор — это программа, преобразующая код ЯПВУ в машинный код шаг за шагом, т. е. каждая коман­да преобразуется интерпретатором и сразу выполняется компьютером, затем интерпретатор преобразует следую­щую команду, компьютер ее выполняет и т. д. (интерпретатор — «синхронный переводчик»). Недостаток интерпретаторов — низкая скорость выполнения программ. Примеры: интерпретаторы языков Basic и Java Script. Для языка Basic в настоящее время существуют как интерпретаторы, так и компиляторы.

 

Типы данных

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

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

Константа — это именованное значение, которое остается неизменным на протяжении всего времени выполнения программы. Числовая константа представляет собой какое-либо число (7; 3.14), а строковая константа - произвольную строку (" количество учеников в классе ").

В любом ЯПВУ переменные и константы характеризуются своими типами. Тип данных — это правила хранения и формат данных. Во время работы программы тип данных будет определять, каким образом данные будут извлекаться из оперативной памяти (ОП), интерпретироваться и сохраняться в ОП. Например, величины 205 и -45 относятся к целочисленному типу и их можно складывать, вычитать, перемножать и делить. Величины " цвет " и " ок " относятся к строковому типу, их можно сцеплять, но над ними нельзя выполнять арифметические операции.

В языке Basic существуют следующие типы данных.

 

Простые	Структурированные
Целые: Integer (2 байта) LONG (4 байта)	Массивы: DIM (могут быть целыми, вещественными, логическими)
Вещественные: SINGLE (4 байта) DOUBLE (8 байтов)	Строковые: STRING (1 байт на символ)
Логические: BOOLEAN (2 байта)

 

Примечание: Массив - индексированный набор элементов одного типа; STRING - ряд, последовательность, цепочка; строка - последовательность символов.

 

Технологии программирования

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

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

Технология восходящего программирования («снизу вверх») реализуется так:

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

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

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

 

Технология нисходящего программирования — это со­здание программы «сверху вниз». Сначала разрабатывается основная программа (точнее, ее общая структура) и в ней за­писываются обращения к пока еще не написанным вспомогательным подпрограммам; и так далее — до самых простых «неделимых» подпрограмм.

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

При этом для ускорения процесса работы над задачей ру­ководитель может разрабатывать основную программу, а другие сотрудники — подпрограммы. Если какая-то подпрограмма не готова, ее заменяют подпрограммой-«заглушкой», которая при заданных входных данных дает разум­ный результат (хотя фактически подпрограмма не работает). Технология нисходящего программирования (метод после­довательной детализации) лежит в основе технологии структурного программирования.

Алгоритм решения основной задачи называется основным алгоритмом. Алгоритм решения некоторой подзадачи по отно­шению к исходной (основной) задаче называется вспомогатель­ным алгоритмом.

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

Итак, особенности структурного программирования:

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

Этапы решения сложной задачи X сверху вниз:

1. Разбиваем задачу X на несколько функциональных подзадач XI, Х2, ХЗ и т. д., т. е. выполняем ее деком­позицию.
2. Предполагаем, что впоследствии эти части будут разра­ботаны, создаем их спецификации:
   - вид подпрограммы (процедура или функция);
   - ее имя;
   - имена и типы формальных параметров, их порядок;
   - для функции — тип возвращаемого значения;
   - комментарии, описывающие назначение подпрограммы.
3. Пишем программу решения задачи X, заменив каждую из подпрограмм XI, Х2, ХЗ «заглушками», и отлаживаем ее в таком виде.
4. Параллельно работаем с каждой из подпрограмм XI, Х2, ХЗ, при необходимости так же разбивая каждую из них на подзадачи еще более низкого уровня, т. е. используя методику, начиная с п. 1. Каждую подзада­чу можно решать независимо от других.
5. Проводим комплексную отладку постепенно, по одной заменяя заглушки на автономно отлаженные подпрограммы.

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

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

 

Процедуры и функции

Подпрограмма (subroutine) — именованная последовате­льность операторов языка, предназначенная для решения некоторой подзадачи. Часто подпрограмма имеет свои пере­менные, не пересекающиеся с переменными других подпрограмм или самой программы (если только переменные не были объявлены специальным образом или переданы под­программе). Каждая подпрограмма имеет имя, по которому к ней можно обратиться. В языке QBasic ме­ханизм подпрограмм реализуется в виде процедур (procedure) и функций (function) с такой же структурой, как и основная программа. Они различаются назначением и способом использования.

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

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

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

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

 

Описание процедуры

SUB <имя>[(<формальные параметры>)]

<Объявление переменных>

<Тело процедуры>

EXIT SUB

END SUB

Обращение к процедуре

CALL <имя>[(фактические параметры)]

 

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

 

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

 

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

 

Описание функции

Function <имя> [(<формальные параметры>)]: <тип результата>

<Объявление переменных>

<Тело функции>

<имя>=<значение>

END FUNCTION

Обращение к функции

Р=<имя>[(<фактические параметры>)]

 

Примечание. <значение> - это результат выполнения арифметичиского выражения.

 

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

 

Структура программы на QBasic:

 

Const — раздел констант

Туре — раздел типов

DEF — раздел переменных

SUB, FUNCTION — раздел процедур и функций

Раздел операторов

END

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

 

Примеры создания и использования процедур и функ­ций:

Задача 1. Написать процедуру возведения в целую степень N некотс рого числа X, N > 0, X > 0. Показать использование процедуры, оба числа вводятся с клавиатуры.

 

DIM Y, К AS INTEGER DIM P AS LONG SUB STEPEN (X, N AS INTEGER, P AS LONG) DEFINT I P=1 FOR I=1 TO N P=P*X NEXT END SUB   CLS INPUT "Введите число Y и степень К "; Y,K CALL STEPEN (Y,К,Р) PRINT "P="; P END

Описание процедуры формальные параметры X, N, P X, N - входные параметры P - выходной параметр I - локальная переменная   конец процедуры   обращение к процедуре с фактическими параметрамиY,K,P

 

 

Структуры данных. Обработка массивов. Поиск в масси­ве. Основные алгоритмы сортировки массивов.

 

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

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

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

Основная операция с массивом — обращение к его эле­ментам. Элементы массива используются и изменяются как обычные переменные.

Операция	Бейсик
Объявление массива 10 вещественных элементов	DIM A(10)
Объявление массива 14 целых элементов	DIM В%(14)
Объявление массива 5 строковых элементов	DIM C$(5)
Обращение к элементу	F=C$(2)
Присваивание	C$(3)= C$(1)+ C$(5)

 

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

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

 

Пример — поиск максимального элемента в массиве:

CLS

DEFINT A

DIM A(5)

FOR I = 1 TO 5

A(I) = INT(RND(1) * 100)

PRINT A(I);

NEXT

MAX = 0

FOR I = 1 TO N

IF A(I) > MAX THEN MAX = A(I) ELSE 10

10: NEXT

PRINT "максимальный элемент массива -"; MAX

END

 

Если в массиве выдержан какой-то принцип расположе­ния элементов (упорядочение), то все операции поиска мож­но ускорить. Упорядоченным по неубыванию считается мас­сив, в котором каждый следующий элемент не меньше пре­дыдущего, упорядоченным по невозрастанию — тот, где каждый следующий элемент не больше предыдущего.

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

Алгоритмов сортировки массивов достаточно много, наи­более простой в реализации — метод пузырька. Этот алго­ритм предполагает многократный проход по массиву; на каждом проходе (итерации цикла) циклически обменива­ются местами попарно элементы, стоящие в неправильной последовательности. В результате самый «легкий» элемент (минимальный или максимальный) «всплывает» и занима­ет свое место. На каждой итерации количество обрабатыва­емых элементов уменьшается на единицу. Итерации повто­ряются, пока требуется выполнить хотя бы одну переста­новку:

 

Пример — сортировка элементов массива по возрастанию.

 

CLS

DIM A(10)

FOR I=1 TO 10

A(I) = INT(RND(1)*100)

PRINT A(I);

NEXT

FOR I=1 TO 9

IF A(I) <=A(I+1) THEN 10 ELSE 20

20: R= A(I)

A(I)= A(I+1)

A(I+1)= R

I=0

10: NEXT

PRINT

FOR I=1 TO 10

PRINT A(I);

NEXT

 

 

Основные понятия и операции формальной логики. Зако­ны логики. Логические переменные. Логические выраже­ния и их преобразования. Построение таблиц истинности логических выражений.

 

Основные понятия и операции алгебры логики

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

Логика изучает формы мышления с точки зрения их структуры, законы и правила получения некоторого знания. Формами мышления являются: понятие, суждение, умоза­ключение.

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

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

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

В своем развитии логика прошла ряд этапов. Современную логику называют математической. Алгебра высказываний (алгебра логики) — раздел математической логики.

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

Учение о высказываниях, называемое алгеброй выска­зываний (алгеброй логики), является первой из формаль­ных логических теорий. Объектами алгебры логики явля­ются высказывания.

Алгебра логики имеет приложения при синтезе релейно-контактных и электронных схем. В этой теории отвлека­ются от содержания высказывания, а рассматривают только то его свойство, что оно представляет собой или истину, или ложь. Тогда высказывание можно рассматривать как величину, которая может принимать два значения: «истина» и «ложь». Высказывания обозначаются прописными латин­скими буквами А, В, С, D..., а их значения «Истина» или «Ложь» можно записывать как TRUE и FALSE, или Т и F, или 1 и 0, или И и Л.

Примеры высказываний:

«Луна — спутник Земли».

«Все числа — целые».

 

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

 

Логическое отрицание (инверсия) — это логическая опе­рация, применяемая к одному высказыванию. Высказыва­ние А есть высказывание, которое ложно, когда А истинно, и истинно, когда А ложно. Высказывание называется отри­цанием А.

Возможные обозначения отрицания: A, not А, не А.

 

Логическое умножение (конъюнкция) — это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся ис­тинным тогда и только тогда, когда оба исходных высказы­вания истинны.

Возможные обозначения конъюнкции: A И В, А & В, A AND В, А·В, А U В, АВ.

 

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

Возможные обозначения дизъюнкции: А ИЛИ В, A U В, A OR В, А + В, А || В.

 

Логическое следование (импликация) — это высказыва­ние ложно тогда и только тогда, когда А истинно, а В лож­но.

Возможные обозначения импликации: А®В, А => В.

 

Эквивалентность — это высказывание истинно тогда и только тогда, когда А и В оба истинны или оба ложны.

Возможные обозначения эквивалентности: А ~ В, А U В.

 

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

Исходные высказывания могут быть логическими кон­стантами (если имеют постоянное значение «истина» или «ложь») или логическими переменными.

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

Логические операции позволяют каждой формуле при за­данных значениях входящих в нее высказываний приписать одно из двух значений: 0 или 1. Тем самым каждая формула может рассматриваться как некоторый способ задания или реализации функции алгебры логики. Логическая функ­ция — это функция, определенная на множестве значений (истина, ложь) и принимающая значение из того же множе­ства. Например: F1 = А&В, F2 = AUB.

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

 

Таблица простейших логических функций: