Билет 5.

Передача — это процесс распространения информации в пространстве. Передача

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

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

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

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

что между ними существует канал связи. Основными характеристиками канала связи

являются надёжность передачи информации и его пропускная способность, то есть

скорость передачи информации по каналу.

Схема передачи информации: источник – кодирующее устройство – канал связи (+

защита от помех) – декодирующее устройство – приёмник

Кодирующее устройство — устройство, предназначенное для преобразования исходного

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

Декодирующее устройство — устройство для преобразования кодированного сообщения

в исходное.

Характеристики канала связи

• пропускная способность

• защита от помех

Пропускная способность канала – это отношение количества переданной информации ко

времени, затраченному на передачу. Она измеряется в битах в секунду и кратных

единицах.

Величина Перевод В битах

1 байт/с 8 бит/с 23 бит/с

1 Кбит/с 1024 бит/с 210 бит/с

1 Мбит/с 1024 Кбит/с 220 бит/с

1 Гбит/с 1024 Мбит/с 230 бит/с

Пример 1. Оценить пропускную способность канала связи, по которому за 5 минут было

передано 300 Мбайт информации.

По свойствам пропорции имеем: за 1 секунду было передано 300×220 бит/(5×60) = 220 бит/с

= 1 Мбит/с

Пример 2. У пользователя Васи дома имеется канал с пропускной способностью 8 Мбит/с.

Оцените, за сколько времени он сможет скачать из Интернета фильм размером 1 Гбайт.

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

1 Гбайт / 8 Мбит/с = 8×230 бит / (8×220 бит/с) = 210 с = 1024 с = (примерно) 17 минут.

стр. 12 из 47

Билет 6-7.

Алгоритм — описание последовательности действий(план),строгое исполнение которых

приводит к решению поставленной задачи за конечное число шагов.

Исполнитель — объект,который выполняет алгоритм.

Основные характеристики алгоритма

• среда (обстановка, в которой функционирует исполнитель)

• система команд (что понимает исполнитель)

• элементарные действия (что умеет делать исполнитель)

• отказы (в каких случаях исполнитель прекращает работу).

Каждый исполнитель может выполнять команды только из некоторого строго заданного

списка-системы команд исполнителя (совокупность всех команд, которые может

выполнить исполнитель(СКИ)). Для каждой команды должны быть заданы условия

применимости и описаны результаты выполнения команд.

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

1. Дискретность (алгоритм должен состоять из конкретных действий, следующих в

определенном порядке)

2. Детерминированность (любое действие должно быть строго и недвусмысленно

определено в каждом случае)

3. Конечность (каждое действие и алгоритм в целом должны иметь возможность

завершения)

4. Массовость (один и тот же алгоритм можно использовать с разными исходными

данными)

5. Результативность (отсутствие ошибок, алгоритм должен приводить к правильному

результату для всех допустимых входных значениях).

Для более наглядного представления алгоритма широко используется графическая форма

— блок-схема, которая составляется из стандартных графических объектов.

Название Элемент блок-схемы

начало-конец

процесс

условие

ввод-вывод

цикл

стр. 13 из 47

Билет 8.

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

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

переменная в зависимости от своего содержимого принадлежит одному из следующих

типов:

Название Описание Пример

integer целые числа i = 5

double (float) вещественные числа i = 2.345

string строка string = «Hello, world!»

bool булевский (логический) тип

(значения: true / false)

i = true

array, hash массив или хэш array = [2,3,4,5]

object объект –

Массивы

Массив — это таблица из двух столбцов. Левый называется «ключи», правый –

«значения». Суть массива – запись и обработка группы данных, связанных по смыслу.

Например, цена на нефть за последние 3 дня. Или список триместровых оценок

определённого класса.

Хэш — массив, ключи которого являются строками, а не последовательными целыми

числами

Когда какая-либо переменная принимает определённое значение, говорят, чтобыла

выполнена операция присваивания. Например, код array = [2,3,4,5] означает, что

переменной array было присвоено значение в виде соответствующего массива.

В течение времени выполнения программы переменные могут менять свои значения, а в

языке ruby (и во всех динамически типизированных языках) – даже тип. К переменным

числового типа можно применять арифметические операции: + сложение, — вычитание,

× умножение, / деление, % остаток от деления, ** возведение в степень. Следует отметить,

что при делении двух целых чисел выполняется целочисленное деление с остатком. То

есть, при делении 5/2 получится не 2.5, а 2. А вот если разделить 5.0/2, то получится

вещественное число 2.5.

К массивам можно применять методы — специальные конструкции, позволяющие изменить

массив. Например, метод sort способен отсортировать массив по возрастанию: array.sort. А

метод min способен найти минимальный элемент массива: array.min.

Операторы (команды)

Оператор — это наиболее крупное и содержательное понятие языка: каждый оператор

представляет собой законченную фразу языка и определяет некоторый вполне

законченный этап обработки данных.

Например, оператор puts способен вывести на экран любой текст:

puts «Hello, world» выводит на экран приветствие Hello, world.

стр. 14 из 47

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

Алгоритм называется линейным, если все действия выполняются в нём последовательно,

друг за другом.

Пример линейной программы:

array = [70.38, 70.85, 72.30, 69.55]

usd_to_rub = 30.29

rub_array = array.map{|elem| elem*usd_to_rub}

puts rub_array

Данная программа считывает данные из массива array (цена на нефть в USD), переводит

их в рубли по курсу usd_to_rub и выводит итоговый массив на экран.

стр. 15 из 47

Билет 9.

Высказывание (утверждение) – это фомулировка своего понимания окружающего мира.

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

отрицается или утверждается.

Принцип дихотомии: любое высказывание либо истинно, либо ложно. Иными словами,

никакое высказывание не может быть одновременно и истинным, и ложным, или наоборот

– ни истинным, ни ложным.

Обычно истинность или ложность высказывания определяют либо исходя из здравого

смысла, либо путём логических умозаключений.

Пример истинного высказывания: «Мы живём на планете Земля»

Пример ложного высказывания: «Мне – 200000000000 лет»

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

буквой латинского алфавита (как и неизвестные в алгебре). Над логическими

переменными можно проводить операции: конъюнкция (&, логическое «и»), дизъюнкция (V,

логическое «или»), отрицание (¬, логическое «не»), импликация (=>, «следовательно») и

др. Эти операции задаются аксиоматически с помощью таблиц истинности. Эти таблицы

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

высказываний.

A B A&B

конъюнкция И И И

И Л Л

Л И Л

Л Л Л

A B AVB

дизъюнкция И И И

И Л И

Л И И

Л Л Л

A B A=>B

импликация И И И

И Л Л

Л И И

Л Л И

A ¬A

отрицание И Л

Л И

стр. 16 из 47

Логическая формула – несколько логических переменных, связанных операциями.

Например, (A&B=>C).

Приоритет операций: отрицание, конъюнкция, дизъюнкция, импликация.

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

все возможные значения этой формулы при всех возможных входных данных. Две

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

Например, в силу симметрии таблиц истинности, выполняется переместительный закон

для конъюнкции и дизъюнкции (коммутативность): A&B = B&A, AVB = BVA. Аналогично

выполняются сочетательный закон (A&B)&C = A&(B&C), (AVB)VC = AV(BVC),

распределительный закон (A&B)VC = (AVC)&(BVC), (AVB)&C = (A&C)V(B&C), правила де

Моргана ¬(A&B)= ¬AV¬B, ¬(AVB)= ¬A&¬B. Каждый из этих законов можно доказать,

построив таблицы истинности для левой и правой частей, и увидев их равенство.

Пример построения таблицы истинности для правила де Моргана

A B ¬(A&B)

И И ¬(И&И)=Л

И Л И

Л И И

Л Л И

Пример алгоритма с условием

Часто при создании алгоритма необходимо определить поведение исполнителя в

зависимости от каких-либо условий. К примеру, если мы хотим вывести на экран

приветствие на языке пользователя (два варианта – английский и русский языки), то

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

ЕСЛИ (родной язык пользователя = русский)

ТОГДА НАПЕЧАТАТЬ «Привет!»

ИНАЧЕ

НАПЕЧАТАТЬ «Hello»

КОНЕЦ

Кусок программы на ruby:

lang = «russian»

if (lang == «russian»)

puts «Привет»

else

puts «Hello»

end

Операции сравнения

В условиях возможны следующие операции: > - больше, < - меньше, <= - меньше либо

равно, >= - больше либо равно, == - равно, === - эквивалентно, != - не равно.

Пример условия: ЕСЛИ ( (a+b)<= c) – если сумма a и b меньше либа равна c.

стр. 17 из 47

Билет 10.

Представление о программировании: язык программирования (на примере одного из

языков высокого уровня); примеры несложных программ с линейной, ветвящейся и

циклической структурой.

Назначение программирования - разработка программ управления компьютером с целью

решения различных задач. Для составления программ существуют разнообразные языки

программирования.

Процессор компьютера может исполнять только команды на машинном языке,

закодированные в двоичном алфавите. Программа, состоящая из таких команд, “понятна”

компьютеру, но людям работать с последовательностями команд вида