Шпаргалка по «Информатика»

5. Аналоговые и дискретные сигналы.

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

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

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

где А – амплитуда колебания,

А₀ – начальная амплитуда,

ω – частота,

φ – разность фаз.

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

 

 

 

 

 

 

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

где F_в – высшая частота в спектре частот сигнала.

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

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

 

На этом рисунке число  уровней равно восьми. А это  значит, что каждый из уровней можно  закодировать одним байтом. Значит, любое значение оцифрованного сигнала  получит свой двоичный код.

 

6. Понятие алгоритма. Принципы алгоритма.

Под этим интуитивно понятным на первый взгляд словом кроется огромная теория и годы усиленных трудов многих математиков. Казалось бы, сформулировать определение алгоритма проще простого: алгоритм — четкое и понятное исполнителю указание выполнить последовательность действий, направленных на получение какого-то результата. Однако, существуют такие задачи, решение которых опирается на некую последовательность действий, которая укладывается в данное определение, но говорят, что для решения этой задачи не существует алгоритма. Например, знаменитая задача коммивояжера, в которой имеется таблица стоимости проезда из одного города в другой. Требуется посетить все города, но по такому маршруту, чтобы стоимость путешествия была наименьшей. Единственным решением на сегодняшний день является перебор всевозможных маршрутов с замером стоимости. Всего таких маршрутов будет n!, где n — число городов. Если число городов будет 100, то перебрать нужно будет 100! вариантов, а это число больше, чем количество частиц во всей Вселенной. Понятно, что решить эту задачу невозможно, хотя для того, чтобы ее решить, нужно выполнять последователь действий, похожих по определению на алгоритм.

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

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

1. Если мы ему скажем «пойди в магазин и купи чего-нибудь», то в итоге мы не получим результата, потому что нарушается свойство определенности. Алгоритм не должен содержать команды, смысл которых может быть понятен неоднозначно.

2. Если мы скажем ребенку «go to the shop and buy a bread», то он вряд ли вообще что-то сделает, так как скорее всего он не поймет наших слов. Алгоритм должен быть понятен исполнителю, то есть команды должны содержаться в системе команд исполнителей (СКИ).

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

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

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

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

Итак, свойства алгоритма:

1) определенность;

2) понятность;

3) результативность;

4) конечность;

5) дискретность;

6) массовость.

 

7. Языки программирования: назначение, виды. Компиляция, интерпретация, трансляция.

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

Первые  программы появились едва ли позже  создания компьютера. Первым программистом  принято считать знаменитую Аду  Лавлейс, дочь лорда Байрона, которая так была сильно увлечена математикой и трудами Чарльза Бэббиджа. Чарльз Бэббидж вошел в историю благодаря конструированию «Аналитической машины», которая, исходя из ее проектирования, должна была быть очень похожа по своей структуре на современный компьютер. Она должна была иметь устройство для ввода и вывода данных, «накопитель», в которых должны были размещаться промежуточные результаты, «мельницу» для вычислений, управляющее устройство. Юная Ада буквально подхватила идею создания этой машины и помимо новых идей по конструированию узлов и механизмов, она занималась разработкой программ к еще не существующей машине. Надо отметить, что после себя эти два замечательных человека оставили только гору чертежей и схем. Сама же машина была построена много позже, в XX века группой студентов в дань уважения «отцу компьютерной техники».

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

15 0049 2376

Здесь первое число означает код операции, а два других — номера ячеек  памяти, откуда нужно взять значения. Например, если «15» - код операции сложения, то запись означает, что нужно было взять число, лежащее в ячейке с номером 0049 и сложить с числом, лежащем в ячейке с номером 2376 и положить результат в ячейку с номером 0049. Понятно, что в этих числах легко можно было запутаться. Разобраться в таких записях иногда просто невозможно. Нужно помнить все коды операций, кроме того, нужно помнить все адреса ячеек, где лежат данные. Кроме того, все эти команды записывались в двоичной системе счисления. Конечно же, ни о каком удобстве программирования говорить в этом случае не приходится. Зато процессору такие команды не просто понятны, но и являются единственно возможными. Процессору команды понятны, а человеку совершенно нет. Чтобы как-то приблизить программирование к человеку, были созданы специальные языки с транслятором¹ типа Ассемблер (англ. assembler — сборщик). Такие языки назывались языками Ассемблера. Эти языки имели общую структуру, которая состояла из метки, кода и комментария. Код состоял из так называемой мнемоники и списка аргументов. Мнемоника — трех-, четырехбуквенное сокращение команды, аналог кода операции. Список аргументов записывался через запятую, их количество зависело от конкретной операции. В этом случае команды могли выглядеть так:

MOV a, 15

MOV b, 35

Эти команды означают, что переменной «а» нужно присвоить значение 15, а переменной «b» - значение 35. Аналогом команды из вышеобозначенного примера могла бы быть команда

ADD a, b

что означало бы, «сложить число, лежащее  в ячейке «а» с числом в ячейке «b», а результат положить в ячейку «а».

Как видно из примера, язык очень сильно напоминает машинный, но здесь имеются  некоторые «человеческие» элементы: например, команда «MOV» созвучна с английским словом «move», что означает «передвинуть», а команда «ADD» созвучна со словом «add» (прибавить). Во-вторых, здесь уже нет адресов ячеек, а есть переменные. Дать переменной конкретный адрес ячейки уже не задача программиста, а задача программы-транслятора. Таким образом, программист избавлен от проблемы поиска свободных ячеек памяти, за него это делает машина. Отметим, что в этом случае язык уже не совсем машинный, и для компьютера эти команды незнакомы, ему их нужно переводить (транслировать). Но все же этот язык очень похож на машинный. Такие языки называют языками программирования низкого уровня.

Однако  даже на языках ассемблера работать достаточно сложно и трудоемко. Естественно  желание писать программы так  таком языке, который был бы более  приближен к «человеческому», где  команды звучали бы как фразы. Такие языки называются языками программирования высокого уровня. Например, такой фрагмент программы, написанный на языке Pascal

If n<15 then n:=n+3 else n:=n-2,

в переводе с английского звучит так: «если n < 15, то n:=n+3, иначе n:=n-2». На языке программирования Pascal эта фраза означает «если n < 15, то к n прибавать 3, иначе от n отнять 2». Почти как на английском. Очевидно, что с помощью этого языка можно писать программы легче, такие программы легко понимаемы. Кроме того, языки программирования высокого уровня позволяют работать с любыми данными, а не только с числами. Еще стоит отметить, что если языки Ассемблера были предназначены для процессора определенного типа (поэтому неверно говорить «язык Ассемблер», так как ассемблер — это только программа-транслятор), то языки программирования высокого уровня не зависят от типа компьютера.

 

 

 

 

 

 

 

Языки программирования высокого уровня делятся  на 2 типа:

 

 

 

императивные

декларативные

Программа представляет собой алгоритм решения  какой-то задачи. Алгоритм описывается пошагово. Например, «для того, чтобы перейти дорогу, нужно: Подойти к проезжей части; Посмотреть на светофор; Если светофор зеленый, посмотреть по сторонам и если нет автомобилей, пересекающих проезжую часть, то перейти проезжую часть иначе подождать, пока машины проедут; перейти проезжую часть. иначе подождать одну секунду вернуться к пункту 2; перейти проезжую часть.» Примерами могут служить такие языки, как Pascal BASIC Delphi C++, C#

В них  по сути нет алгоритма, есть только описание данных в их взаимосвязи. На основании полученных данных компьютер должен сформулировать ответ. Например: «на проезжей части 3 автомобиля: красный, синий и зеленый; светофор стоит в пяти метрах, на нем горит красный свет; 2 автомобиля движутся, один стоит. Можно ли мне перейти через проезжую часть?» Примерами декларативных  языков программирования служат: Prolog Lisp SQL