Способы описания алгоритмов языки программирования
Различают следующие виды алгоритмов :
линейный – список команд (указаний), выполняемых последовательно друг за другом;
разветвляющийся – алгоритм, содержащий хотя бы одну проверку условия, в результате которой обеспечивается переход на один из возможных вариантов решения;
циклический – алгоритм, предусматривающий многократное повторение одной и той же последовательности действий. Количество повторений обусловливается исходными данными или условием задачи.
Любая алгоритмическая конструкция может содержать в себе другую конструкцию того же или иного вида, т. е. алгоритмические конструкции могут быть вложенными. Рассмотрим следующие способы описания алгоритма: словесное описание, псевдокод, блок-схема, программа.
Словесное описание представляет структуру алгоритма на естественном языке. Например, любой прибор бытовой техники (утюг,электропила, дрель и т.п.) имеет инструкцию по эксплуатации, т.е.словесное описания алгоритма, в соответствии которому данный прибор должен использоваться. Никаких правил составления словесного описания не существует. Запись алгоритма осуществляется в произвольной форме на естественном, например, русском языке. Этот способ описания не имеет широкого распространения, так как строго не формализуем (под «формальным» понимается то, что описание абсолютно полное и учитывает все возможные ситуации, которые могут возникнуть в ходе решения); допускает неоднозначность толкования при описании некоторых действий; страдает многословностью.
1. определить температуру воздуха
2. если температура ниже 0, то надеть шубу, иначе надеть куртку
Псевдокод — описание структуры алгоритма на естественном, частично формализованном языке, позволяющее выявить основныеэтапы решения задачи, перед точной его записью на языке программирования. В псевдокоде используются некоторые формальные конструкции и общепринятая математическая символика. Строгих синтаксических правил для записи псевдокода не существует. Это облегчает запись алгоритма при проектировании и позволяет описать алгоритм, используя любой набор команд. Однако в псевдокоде обычно используются некоторые конструкции, присущие формальным языкам, что облегчает переход от псевдокода к записи алгоритма на языке программирования. Единого или формального определения псевдокода не существует, поэтому возможны различные псевдокоды, отличающиеся набором используемых слов и конструкций.
Блок-схема — описание структуры алгоритма с помощью геометрических фигур с линиями-связями, показывающими порядок выполнения отдельных инструкций. Этот способ имеет ряд преимуществ. Благодаря наглядности, он обеспечивает «читаемость»алгоритма и явно отображает порядок выполнения отдельных команд. В блок-схеме каждой формальной конструкции соответствует определенная геометрическая фигура или связанная линиями совокупность фигур.
Описания алгоритма в словесной форме, на псевдокоде или в виде блок-схемы допускают некоторый произвол при изображении команд. Вместе с тем они настолько достаточны, что позволяет человеку понять суть дела и исполнить алгоритм. На практике исполнителями алгоритмов выступают компьютеры. Поэтому алгоритм, предназначенный для исполнения на компьютере, должен быть записан на «понятном» ему языке, такой формализованный язык называют языком программирования .
Источник
информатика
Лекции
1. Введение
ИНФОРМАЦИЯ И ЕЕ РОЛЬ В СОВРЕМЕННОМ ОБЩЕСТВЕ.
ИНФОРМАТИКА- НАУКА, ИЗУЧАЮЩАЯ СПОСОБЫ АВТОМАТИЗИРОВАННОГО СОЗДАНИЯ, ХРАНЕНИЯ, ОБРАБОТКИ, ИСПОЛЬЗОВАНИЯ, ПЕРЕДАЧИ И ЗАЩИТЫ ИНФОРМАЦИИ.
ИНФОРМАЦИЯ – ЭТО НАБОР СИМВОЛОВ, ГРАФИЧЕСКИХ ОБРАЗОВ ИЛИ ЗВУКОВЫХ СИГНАЛОВ, НЕСУЩИХ ОПРЕДЕЛЕННУЮ СМЫСЛОВУЮ НАГРУЗКУ.
Например, этот или любой другой текст, имеющий определенный смысл, состоит из набора символов- букв, знаков препинания, цифр, которые объединяются в слова, те в свою очередь — в предложения и далее- в абзацы. Человек, чтобы сообщить что-либо собеседнику произносит определенные фразы- то есть издает звуковые сигналы. Данные – это зарегистрированные сигналы. Однако, не все данные являются информацией. Слыша речь на незнакомом языке, мы получаем данные, но не получаем информацию, в связи с тем, что не владеем методом преобразования данных в известные нам понятия. Изображение на знаке дорожного движения доводит до водителя автомобиля определенную информацию, а для человека, не понимающего эти знаки, они не являются информацией.
Итак, информация – это продукт преобразования зарегистрированных сигналов в известные субъекту понятия. Огромное влияние в передаче информации сыграла письменность. Затем — телефон, радио. Сейчас – телевидение и компьютерные технологии.
ЭЛЕКТРОННО-ВЫЧИСЛИТЕЛЬНАЯ МАШИНА (ЭВМ) ИЛИ КОМПЬЮТЕР (англ. computer- -вычислитель)-УСТРОЙСТВО ДЛЯ АВТОМАТИЗИРОВАННОЙ ОБРАБОТКИ ИНФОРМАЦИИ. Принципиальное отличие использования ЭВМ от всех других способов обработки информации заключается в способности выполнения определенных операций без непосредственного участия человека, но по заранее составленной им программе. Информация в современном мире приравнивается по своему значению для развития общества или страны к важнейшим ресурсам наряду с сырьем и энергией. Еще в 1971 году президент Академии наук США Ф.Хандлер говорил: «Наша экономика основана не на естественных ресурсах, а на умах и применении научного знания».
В развитых странах большинство работающих заняты не в сфере производства, а в той или иной степени занимаются обработкой информации. Поэтому философы называют нашу эпоху постиндустриальной. В 1983 году американский сенатор Г.Харт охарактеризовал этот процесс так: «Мы переходим от экономики, основанной на тяжелой промышленности, к экономике, которая все больше ориентируется на информацию, новейшую технику и технологию, средства связи и услуги..»
2. КРАТКАЯ ИСТОРИЯ РАЗВИТИЯ ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ.
Вся история развития человеческого общества связана с накоплением и обменом информацией (наскальная живопись, письменность, библиотеки, почта, телефон, радио, счеты и механические арифмометры и др.). Коренной перелом в области технологии обработки информации начался после второй мировой войны.
В вычислительных машинах первого поколения основными элементами были электронные лампы. Эти машины занимали громадные залы, весили сотни тонн и расходовали сотни киловатт электроэнергии. Их быстродействие и надежность были низкими, а стоимость достигала 500-700 тысяч долларов.
Появление более мощных и дешевых ЭВМ второго поколения стало возможным благодаря изобретению в 1948 году полупроводниковых устройств- транзисторов. Главный недостаток машин первого и второго поколений заключался в том, что они собирались из большого числа компонент, соединяемых между собой. Точки соединения (пайки) являются самыми ненадежными местами в электронной технике, поэтому эти ЭВМ часто выходили из строя.
В ЭВМ третьего поколения (с середины 60-х годов ХХ века) стали использоваться интегральные микросхемы (чипы)- устройства, содержащие в себе тысячи транзисторов и других элементов, но изготовляемые как единое целое, без сварных или паяных соединений этих элементов между собой. Это привело не только к резкому увеличению надежности ЭВМ, но и к снижению размеров, энергопотребления и стоимости (до 50 тысяч долларов).
История ЭВМ четвертого поколения началась в 1970 году, когда ранее никому не известная американская фирма INTEL создала большую интегральную схему (БИС), содержащую в себе практически всю основную электронику компьютера. Цена одной такой схемы (микропроцессора) составляла всего несколько десятков долларов, что в итоге и привело к снижению цен на ЭВМ до уровня доступных широкому кругу пользователей.
СОВРЕМЕННЫЕ КОМПЬТЕРЫ- ЭТО ЭВМ ЧЕТВЕРТОГО ПОКОЛЕНИЯ, В КОТОРЫХ ИСПОЛЬЗУЮТСЯ БОЛЬШИЕ ИНТЕГРАЛЬНЫЕ СХЕМЫ.
90-ые годы ХХ-го века ознаменовались бурным развитием компьютерных сетей, охватывающих весь мир. Именно к началу 90-ых количество подключенных к ним компьютеров достигло такого большого значения, что объем ресурсов доступных пользователям сетей привел к переходу ЭВМ в новое качество. Компьютеры стали инструментом для принципиально нового способа общения людей через сети, обеспечивающего практически неограниченный доступ к информации, находящейся на огромном множестве компьюторов во всем мире — «глобальной информационной среде обитания».
6.ПРЕДСТАВЛЕНИЕ ИНФОРМАЦИИ В КОМПЬЮТЕРЕ И ЕЕ ОБЪЕМ.
ЛЮБОЕ СООБЩЕНИЕ НА ЛЮБОМ ЯЗЫКЕ СОСТОИТ ИЗ ПОСЛЕДОВАТЕЛЬНОСТИ СИМВОЛОВ- БУКВ, ЦИФР, ЗНАКОВ. Действительно, в каждом языке есть свой алфавит из определенного набора букв (например, в русском- 33 буквы, английском- 26, и т.д.). Из этих букв образуются слова, которые в свою очередь, вместе с цифрами и знаками препинания образуют предложения, в результате чего и создается текстовое сообщение. Не является исключением и язык на котором «говорит» компьютер, только набор букв в этом языке является минимально возможным.
В КОМПЬЮТЕРЕ ИСПОЛЬЗУЮТСЯ 2 СИМВОЛА- НОЛЬ И ЕДИНИЦА (0 и 1), АНАЛОГИЧНО ТОМУ, КАК В АЗБУКЕ МОРЗЕ ИСПОЛЬЗУЮТСЯ ТОЧКА И ТИРЕ. Действительно, закодировав привычные человеку символы (буквы, цифры, знаки) в виде нулей и единиц (или точек и тире), можно составить, передать и сохранить любое сообщение.
ЭТО СВЯЗАНО С ТЕМ, ЧТО ИНФОРМАЦИЮ, ПРЕДСТАВЛЕННУЮ В ТАКОМ ВИДЕ, ЛЕГКО ТЕХНИЧЕСКИ СМОДЕЛИРОВАТЬ, НАПРИМЕР, В ВИДЕ ЭЛЕКТРИЧЕСКИХ СИГНАЛОВ. Если в какой-то момент времени по проводнику идет ток, то по нему передается единица, если тока нет- ноль. Аналогично, если направление магнитного поля на каком-то участке поверхности магнитного диска одно- на этом участке записан ноль, другое- единица. Если определенный участок поверхности оптического диска отражает лазерный луч- на нем записан ноль, не отражает- единица.
ОБЪЕМ ИНФОРМАЦИИ, НЕОБХОДИМЫЙ ДЛЯ ЗАПОМИНАНИЯ ОДНОГО ИЗ ДВУХ СИМВОЛОВ-0 ИЛИ 1, НАЗЫВАЕТСЯ 1 БИТ (англ. binary digit- двоичная единица). 1 бит- минимально возможный объем информации. Он соответствует промежутку времени, в течение которого по проводнику передается или не передается электрический сигнал, участку поверхности магнитного диска, частицы которого намагничены в том или другом направлении, участку поверхности оптического диска, который отражает или не отражает лазерный луч, одному триггеру, находящемуся в одном из двух возможных состояний.
Итак, если у нас есть один бит, то с его помощью мы можем закодировать один из двух символов- либо 0, либо 1.
Если же есть 2 бита, то из них можно составить один из четырех вариантов кодов: 00 , 01 , 10 , 11 .
Если есть 3 бита- один из восьми: 000 , 001 , 010 , 100 , 110 , 101 , 011 , 111 .
1 бит- 2 варианта,
2 бита- 4 варианта,
3 бита- 8 вариантов;
Продолжая дальше, получим:
4 бита- 16 вариантов,
5 бит- 32 варианта,
6 бит- 64 варианта,
7 бит- 128 вариантов,
8 бит- 256 вариантов,
9 бит- 512 вариантов,
10 бит- 1024 варианта,
N бит — 2 в степени N вариантов.
В обычной жизни нам достаточно 150-160 стандартных символов (больших и маленьких русских и латинских букв, цифр, знаков препинания, арифметических действий и т.п.). Если каждому из них будет соответствовать свой код из нулей и единиц, то 7 бит для этого будет недостаточно (7 бит позволят закодировать только 128 различных символов), поэтому используют 8 бит.
ДЛЯ КОДИРОВАНИЯ ОДНОГО ПРИВЫЧНОГО ЧЕЛОВЕКУ СИМВОЛА В КОМПЬЮТЕРЕ ИСПОЛЬЗУЕТСЯ 8 БИТ, ЧТО ПОЗВОЛЯЕТ ЗАКОДИРОВАТЬ 256 РАЗЛИЧНЫХ СИМВОЛОВ.
СТАНДАРТНЫЙ НАБОР ИЗ 256 СИМВОЛОВ НАЗЫВАЕТСЯ ASCII ( произносится «аски», означает «Американский Стандартный Код для Обмена Информацией»- англ. American Standart Code for Information Interchange).
ОН ВКЛЮЧАЕТ В СЕБЯ БОЛЬШИЕ И МАЛЕНЬКИЕ РУССКИЕ И ЛАТИНСКИЕ БУКВЫ, ЦИФРЫ, ЗНАКИ ПРЕПИНАНИЯ И АРИФМЕТИЧЕСКИХ ДЕЙСТВИЙ И Т.П.
КАЖДОМУ СИМВОЛУ ASCII СООТВЕТСТВУЕТ 8-БИТОВЫЙ ДВОИЧНЫЙ КОД, НАПРИМЕР:
A — 01000001, B — 01000010, C — 01000011, D — 01000100, и т.д.
Таким образом, если человек создает текстовый файл и записывает его на диск, то на самом деле каждый введенный человеком символ хранится в памяти компьютера в виде набора из восьми нулей и единиц. При выводе этого текста на экран или на бумагу специальные схемы — знакогенераторы видеоадаптера (устройства, управляющего работой дисплея) или принтера образуют в соответствии с этими кодами изображения соответствующих символов.
Набор ASCII был разработан в США Американским Национальным Институтом Стандартов (ANSI), но может быть использован и в других странах, поскольку вторая половина из 256 стандартных символов, т.е. 128 символов, могут быть с помощью специальных программ заменены на другие, в частности на символы национального алфавита, в нашем случае — буквы кириллицы. Поэтому, например, передавать по электронной почте за границу тексты, содержащие русские буквы, бессмысленно. В англоязычных странах на экране дисплея вместо русской буквы Ь будет высвечиваться символ английского фунта стерлинга, вместо буквы р — греческая буква альфа, вместо буквы л — одна вторая и т.д.
ОБЪЕМ ИНФОРМАЦИИ, НЕОБХОДИМЫЙ ДЛЯ ЗАПОМИНАНИЯ ОДНОГО СИМВОЛА ASCII НАЗЫВАЕТСЯ 1 БАЙТ.
Очевидно что, поскольку под один стандартный ASCII-символ отводится 8 бит,
Остальные единицы объема информации являются производными от байта:
1 КИЛОБАЙТ = 1024 БАЙТА И СООТВЕТСТВУЕТ ПРИМЕРНО ПОЛОВИНЕ СТРАНИЦЫ ТЕКСТА,
1 МЕГАБАЙТ = 1024 КИЛОБАЙТАМ И СООТВЕТСТВУЕТ ПРИМЕРНО 500 СТРАНИЦАМ ТЕКСТА,
1 ГИГАБАЙТ = 1024 МЕГАБАЙТАМ И СООТВЕТСТВУЕТ ПРИМЕРНО 2 КОМПЛЕКТАМ ЭНЦИКЛОПЕДИИ,
1 ТЕРАБАЙТ = 1024 ГИГАБАЙТАМ И СООТВЕТСТВУЕТ ПРИМЕРНО 2000 КОМПЛЕКТАМ ЭНЦИКЛОПЕДИИ.
Обратите внимание, что в информатике смысл приставок кило- , мега- и других в общепринятом смысле выполняется не точно, а приближенно, поскольку соответствует увеличению не в 1000, а в 1024 раза.
СКОРОСТЬ ПЕРЕДАЧИ ИНФОРМАЦИИ ПО ЛИНИЯМ СВЯЗИ ИЗМЕРЯЕТСЯ В БОДАХ.
1 БОД = 1 БИТ/СЕК.
В частности, если говорят, что пропускная способность какого-то устройства составляет 28 Килобод, то это значит, что с его помощью можно передать по линии связи около 28 тысяч нулей и единиц за одну секунду.
7. СЖАТИЕ ИНФОРМАЦИИ НА ДИСКЕ
ИНФОРМАЦИЮ НА ДИСКЕ МОЖНО ОБРАБОТАТЬ С ПОМОЩЬЮ СПЕЦИАЛЬНЫХ ПРОГРАММ ТАКИМ ОБРАЗОМ, ЧТОБЫ ОНА ЗАНИМАЛА МЕНЬШИЙ ОБЪЕМ.
Существуют различные методы сжатия информации. Некоторые из них ориентированы на сжатие текстовых файлов, другие — графических, и т.д. Однако во всех них используется общая идея, заключающаяся в замене повторяющихся последовательностей бит более короткими кодами. Например, в романе Л.Н.Толстого «Война и мир» несколько миллионов слов, но большинство из них повторяется не один раз, а некоторые- до нескольких тысяч раз. Если все слова пронумеровать, текст можно хранить в виде последовательности чисел — по одному на слово, причем если повторяются слова, то повторяются и числа. Поэтому, такой текст (особенно очень большой, поскольку в нем чаще будут повторяться одни и те же слова) будет занимать меньше места.
Сжатие информации используют, если объем носителя информации недостаточен для хранения требуемого объема информации или информацию надо послать по электронной почте
Программы, используемые при сжатии отдельных файлов называются архиваторами. Эти программы часто позволяют достичь степени сжатия информации в несколько раз.
Источник
