ад)^ Броня у f(alphii)
6 0 =RADIANS(A6) =S/v/C0SCB6) =v*SIN(B6)*C6-9,81*C6"2/2 =D6-H
7 5
S ю:
Рис. 9.10
Обратите внимание, что в формулах мы используем имена ячеек S, Н и V, Это абсолютные ссылки, не меняющиеся при копировании; например, вместо имени S можно было бы написать адрес $В$1, но это было бы менее понятно. Эти формулы можно просто «растянуть» (скопировать) вниз за маркер заполнения.
Теперь построим график функции /(а). Сначала нужно выделить данные в столбцах А и Е, это можно сделать, если удерживать нажатой клавишу Ctrl. Затем строим диаграмму типа Диаграмма XY (в Excel — диаграмма Точечная) — рис. 9.11. График функции пересекает ось ОХ в двух точках, т. е. уравнение Да) = 0 имеет два решения, одно около 35°, второе — около 65°.
Теперь уточним решение, используя возможности табличного процессора, в котором реализован один из приближённых мето-
Решение вычислительных задач на компьютере
дов решения уравнений. Для этого нужно знать начальное приближение Oq — значение неизвестной величины, достаточно близкое к решению. По графику мы определили, что первый раз график пересекает ось ОХ для значения угла около 35°, поэтому можно взять Oq = 35°. Запишем это значение в свободную ячейку, например в Н2, и добавим недостающие формулы так, чтобы получить значение функции /(а) в ячейке L2 (рис. 9.12).
Н I к L
1 Угол Угол (рад) Время У f(alpha)
2 35
Рис. 9.12
Задача подбора параметра формулируется так: «установить в ячейке ... значение ..., изменяя значение ячейки ...». Например, в нашем случае нужно установить в ячейке L2 значение О, изменяя Н2. Ячейка L2 называется целевой, потому что наша цель — получить в ней определённое значение (ноль). Ячейка Н2 — это изменяемая ячейка. В главном меню выбираем пункт Сервис, Подбор параметра и вводим эти данные (рис. 9.13).
Подбор параметра
Настройки по умолчанию
XJ
Яч. с формулой |$L$2 L^l
Целевое значение |о
Изменяемая яч. |$Н$2
ок
Отмена
Справка
Рис. 9.13
После нажатия на кнопку ОК найденное решение уравнения будет записано в ячейку Н2.
Как же найти второе решение? Для этого нужно выбрать другое начальное приближение, например «о ~ ® остальном по-
рядок действий не меняется. Сделайте это самостоятельно.
Проверьте, что будет происходить при изменении начальной скорости до 10 м/с и до 20 м/с. Попробуйте объяснить эти результаты с точки зрения физики.
Решение уравнений
§70
Вопросы и задания
1. Какие методы называются приближёнными? В каких случаях они используются?
2. Что такое итерационный метод?
3. Сравните приближённые и аналитические методы решения уравнений. В чём достоинства и недостатки каждого подхода?
4. Объясните, в чём заключается метод перебора. В чём его недостатки?
5. Как с помощью математических операций определяют, есть ли решение уравнения на заданном отрезке? В каких случаях такой подход не сработает?
6. Как избежать зацикливания в методе перебора?
7. Объясните, почему методом перебора при ширине полосы 5 = 2е можно найти решение с точностью е.
8. Что такое отделение корней и уточнение корней?
9. Объясните изменения, сделанные в первоначальной программе для решения уравнения методом перебора, которые позволили в одном цикле найти все решения на заданном отрезке.
10. Объясните, как работает метод деления отрезка пополам. Сравните его с методом перебора.
Задачи
1. Решите уравнение x2=5cos(x-l) методом перебора и методом деления отрезка пополам. Сравните количество шагов цикла при использовании каждого метода.
2. Решите уравнение =5соз(д;-1), используя табличный процессор.
*3. Попытайтесь улучшить программу для метода перебора, используя
одно из значений функции, вычисленных на предыдущем шаге цикла.
*4. Попытайтесь улучшить программу для метода деления отрезка пополам, используя одно из значений функции, вычисленных на предыдущем шаге цикла.
5. Экспериментально (пробуя различные значения е) определите, с какой точностью можно найти решение уравнения =5cos(x-l) в вашей среде программирования.
6. Решите задачу из примера «Полёт мяча» с помощью собственной программы, а затем с помощью табличного процессора. Обсудите преимущества и недостатки этих способов решения.
*7. Используя замену z = ——, постройте аналитическое решение уравне-
cos^a
ния из примера «Полёт мяча». Для практических вычислений используйте электрюнные таблицы. Сравните точное и численное рюшения.
о
Решение вычислительных задач на компьютере
§71
Дискретизация
Вычисление длины кривой
Определим длину траектории L, по которой летит шарик, брошенный под углом к горизонту (см. задачу в § 70). Это не так просто, потому что траектория — кривая линия.
Постараемся как-то свести задачу к более простой, которую мы умеем решать. Если бы линия состояла из отдельных отрезков, её длину можно было бы точно вычислить с помощью теоремы Пифагора. Например, длина ломаной на рис. 9.14 равна:
L = ^(Х2 -Xi)2 +(l/2 -I/i)2 -н д/(Хд -ЛГ2)2 -Ь (j/g -
Рис. 9.14
Используя эту идею, разделим кривую линию на небольшие участки и заменим каждый участок отрезком так, чтобы получилась ломаная (штриховая линия на рис. 9.15).
Обычно разбивают исходный отрезок [о, 6] (на котором нужно определить длину кривой) на равные участки длины Л. Конечно, длина ломаной отличается от длины кривой, но естественно предположить, что при уменьшении шага разбиения Л эта разница будет уменьшаться.
Дискретизация
§71
Обратим внимание, что мы фактически выполнили дискретизацию — представили кривую в виде набора точек, при этом информация о поведении функции между этими точками была потеряна (вспомните оцифровку звука!). Величина h называется шагом дискретизации.
Подведём итоги:
• дискретизация позволяет представить задачу в виде, пригодном для компьютерных расчётов;
• при дискретизации часть информации теряется, поэтому все методы, основанные на дискретизации, — приближённые, они решают задачу с некоторой погрешностью;
• чтобы уменьшить погрешность, нужно уменьшать шаг дискретизации (увеличивать количество точек), но при этом возрастёт объём (и время) расчётов;
• при выборе малого шага дискретизации на результат могут сильно влиять погрешности вычислений, вызванные неточностью представления веш;ественных чисел в памяти компьютера (см. § 29).
Теперь можно составить программу. Будем считать, что константы (или переменные) а, Ь и h задают границы отрезка и шаг дискретизации. Тогда основная часть программы может выглядеть так на школьном алгоритмическом языке:
х:=а; L:=0 нц пока х<Ь
yl:=f(X) у2:=f(x+h)
L:=L+sqrt(h*h+(у1-у2)*(у1-у2))
X:=x+h; кц
вывод 'Длина кривой ', L и на Паскале:
х:=а; L:=0; while x f{X2), то минимум функции находится на отрезке [Xj, 6], поэтому отрезок [а, Xj ] можно отбросить — переместить левую границу в точку х^; если /(х^) < /(Xg), то правая граница отрезка перемещается в точку Xg.
Остаётся один вопрос: как выбирать г на каждом шаге? Проще всего вычислять его по формуле г = к ф - а), где k — постоянный коэффициент (0< к< 0,5). Тогда ширина отрезка на следующем шаге будет равна
Ь-а
+ к-{Ь -а) = (0,5 + к) {Ь-а).
т. е. составит 0,5 +к от первоначальной ширины. Для ускорения поиска выгодно, чтобы это отношение было как можно меньше, т. е. чтобы коэффициент к был возможно ближе к нулю (ноль выбирать нельзя, потому что при этом точки Xj и Xg совпадут, и метод не будет работать). Программа может выглядеть примерно так:
к:=0.01 delta:=2*eps нц пока b-a>delta г:=к*(Ь-а) х1:= (а+Ь)/2-г х2:= (а+Ь)/2 + г если f(xl)>f(x2) то а: =х1
к:=0.01; delta:=2*eps; while b-a>delta do begin r:=k*(b-a); xl:=(a+b)/2-r; x2:=(a+b)/2+r; if f(xl)>f(x2) then a: =xl
Оптимизация
§72
иначе Ь:=х2 все кц
вывод 'X =',
else Ь:=х2 end;
writeln('X ='
(a+b)/2:10:3);
(a+b)/2
В качестве упражнения можно исследовать работу этой программы при разных значениях k, подсчитав для каждого варианта количество шагов цикла, которое потребуется для получения решения с заданной точностью.
Супдествует вариант метода дихотомии, при котором на каждом шаге цикла нужно вычислять только одно значение функции (второе «переходит» с предыдущего шага). В этом случае нужно выбирать коэффициент k так, чтобы выполнялось равенство
0,5 + ft = i, где ф — отношение «золотого сечения»:
Ф
Ф= 11:!^ «1,618...
2
Пример: оптимальная раскройка листа
Рассмотрим пример практической задачи оптимизации. В углах квадратного листа железа, сторона которого равна 1 м, вырезают четыре квадрата со стороной х. Затем складывают получившуюся развёртку (по штриховым линиям на рис. 9.21), сваривают швы и таким образом получается бак.
Рис. 9.21
Требуется выбрать размер выреза х так, чтобы получился бак наибольшего объёма.
Для того чтобы грамотно поставить задачу оптимизации, нужно:
1) определить целевую функцию: в данном случае выразить объём бака через неизвестную величину л:;
2) задать ограничения на возможные значения х.
Решение вычислительных задач на компьютере
Легко видеть, что основание получившегося бака — это квадрат со стороной Z (см. рис. 9.21), а его высота равна х. Величина z зависит от X и равна 2=1- 2х, поэтому объём бака вычисляется по формуле V =х(1-2х)^, это и есть целевая функция, для которой нужно найти максимум.
Понятно, что X не может быть меньше нуля. Вместе с тем х не может быть больше, чем половина стороны исходного листа (0,5
м), поэтому ограничения запишутся в виде двойного неравенства: о < X < 0,5. Заметим, что при х = 0 и х = 0,5 объём бака равен нулю (в первом случае равна нулю высота, во втором — площадь основания).
Таким образом, нужно искать максимум целевой функции /(х) = х(1-2х)2 на отрезке [0, 0,5]. Для этого можно использовать метод дихотомии (сделайте это самостоятельно). Не забудьте, что приведённый выше вариант программы рассчитан на поиск минимума, а в этой задаче нужно найти максимум.
Использование табличных процессоров
В стандартной поставке OpenOffice.org Calc модуль оптимизации работает только для линейных функций. Для того чтобы решить рассмотренную выше задачу с баком, нужно использовать модуль Solver for Nonlinear Programming (он входит в стандартную поставку последних версий LibreOffice) и в параметрах модуля оптимизации выбрать один из методов нелинейной оптимизации. В табличном процессоре Excel оптимизация выполняется с помощью стандартной надстройки «Поиск решения».
Сначала построим график функции, как мы делали это при решении уравнения (рис. 9.22).
Оптимизация
§72
Рис. 9.23
По этому графику видно, что функция имеет единственный максимум в районе точки Xq =0,2. Это значение можно выбрать в качестве начального приближения для поиска.
Выделим в таблице две ячейки (например, Е2 и F2), в первую запишем начальное приближение (0,2), а во вторую — формулу для вычисления объёма для этого значения х (рис. 9.23).
Задача оптимизации формулируется в виде «найти максимум {или минимум) целевой функции в ячейке ..., изменяя значения ячеек ... при ограничениях ...». В нашей задаче целевая ячейка — F2 (нужно найти ее максимум), изменяемая ячейка — Е2.
Выбираем в главном меню пункт Сервис, Поиск решения, в появившемся окне вводим адреса целевой и изменяемой ячеек (для этого можно установить курсор в нужное поле ввода и щёлкнуть по ячейке) и ограничения (рис. 9.24).
Решатель
■ Х|
|$F$2
Целевая ячейка Оптимизация результа- Максимум С" Минимум С" Значение
Путем изменения ячеек fiiii
L&J
Ссылка на ячейку
fiiii
$Е$2
S1
Операция Значение
1>= d |o
1<= d |o,5
1<= w 1 —
1<= d 1
Параметры,.. | Справка
Закрыть
Решить
Рис. 9.24
Решение вычислительных задач на компьютере
После щелчка на кнопке Решить в ячейку Е2 будет записано оптимальное значение д:, а в целевую ячейку — соответствующее (максимальное) значение объёма.
Надстройка «Поиск решения» позволяет:
находить'максимум или минимум целевой функции; решать уравнения, задавая желаемое значение целевой функции;
• использовать несколько изменяемых ячеек и диапазонов, например запись А2:А6;В15 в списке изменяемых ячеек означает «изменять все ячейки диапазона А2:А6 и ячейку В15»;
использовать ограничения типа «меньше или равно», «больше или равно», «равно», «целое» и «двоичное» (только О или 1).
Кнопка Параметры позволяет опытным пользователям менять настройки алгоритма оптимизации.
Вопросы и задания
1. Что такое оптимизация?
2. Что такое целевая функция?
3. Какое решение называется оптимальным?
4. Почему выражение «самый оптимальный» безграмотно?
5. Что можно сказать о рекламной фразе «Этот крем обеспечивает оптимгьльный цвет лица»?
6. Зачем нужны ограничения в задаче оптимизации?
7. В чём разница между понятиями «локальный минимум» и «глобальный минимум»?
8. Что такое начальное приближение?
9. Почему результат решения задачи оптимизации чаще всего зависит от выбора начального приближения?
10. Объясните принцип работы метода дихотомии.
11. Обязательно ли при использовании метода дихотомии брать пробные точки симметрично относительно середины отрезка? Ответ обоснуйте.
12. Когда метод дихотомии не будет работать (может выдать неверный ответ)?
13. Подумайте, можно ли задачу решения уравнения сформулировать как задачу оптимизации.
Подготовьте сообщение:
а) «Оптимизация для функции двух переменных»
б) «Оптимизация методом случайного поиска*
в) «Программное обеспечение для решения задач оптимизации»
Оптимизация
§72
Задачи
1. Примените метод дихотомии для решения задачи оптимальной раскройки, которая разобрана в параграфе. Решите задачу, используя разные значения коэффициента к, и постройте график зависимости количества шагов цикла от ft.
*2. Напишите программу, которая реализует метод «золотого сечения» (на каждом шаге вычисляется только одно значение функции).
*3. Банка имеет форму цилиндра^, полная площадь её поверхности (боковая поверхность и два круга-основания) равна 100 см^. Определите радиус и высоту банки, которая при этих условиях имеет максимальный объём.
*4. Банка имеет форму цилиндра, её объём равен 500 см^. Определите радиус и высоту банки, которая при этих условиях имеет минимальную площадь полной поверхности.
5. Некоторая фирма хочет провести рекламную кампанию в газетах. Данные о цене рекламного объявления и тиражах газет внесены в таблицу:
О
Газета Тираж Цена одного объявления, руб. Кол-во объявле- ний Расходы, руб. Охват
Ведомости 10 000 1000 1 1000 10 000
Туризм 3500 570 2 1140 7000
Спорт 6000 700 3 2100 18 000
Правда 20 000 1250 4 5000 80 000
Всего 9240 115 000
в каждую газету нужно дать не менее одного и не более 6 объявлений. С помощью надстройки «Поиск решения» табличного процессора определите, сколько объявлений нужно дать в каждую газету, чтобы обеспечить общий охват не менее 200 000 человек и при этом израсходовать как можно меньше денег.
6. В условиях задачи 5 определите, сколько объявлений нужно дать в каждую газету, чтобы обеспечить наибольший общий охват и при этом израсходовать не более 15 000 рублей.
Задачи 3 и 4 предложены В. Я. Лаздиным.
Решение вычислительных задач на компьютере
§73
Статистические расчёты
о
Статистика — это наука, которая изучает методы обработки и анализа больших массивов данных.
О
Табличные процессоры стали незаменимым инструментом для решения этих задач. И Excel, и Calc содержат несколько десятков встроенных статистических функций.
Свойства ряда данных
Простейшая задача статистики — изучить свойства одного ряда данных. Ряд данных X длиной л — это множество значений Xj,JC2,...,x„. Для ряда можно определить количество элементов, их сумму, среднее значение, минимальное и максимальное значения и т. д. Далее мы приводим как английские названия функций (для Calc), так и русские (для русской версии Excel).
Пусть ряд данных записан в ячейках А1:А20. Его сумма, среднее, минимальное и максимальное значения могут быть определены с помощью следующих формул:
сумма:
среднее:
минимальное:
максимальное:
=SUM(A1:A20) =AVERAGE(A1: А20) =MIN(A1:A20) =МАХ(А1:А20)
=СУММ(А1:А20)
=СРЗНАЧ(А1:А20)
=МИН(А1:А20)
=МАКС(А1:А20)
Функции SUM (русское название — СУММ) и AVERAGE (СРЗНАЧ) учитывают только числа в указанном диапазоне (без учёта пустых и текстовых ячеек). Количество числовых значений можно подсчитать с помощью функции COUNT (СЧЁТ), например:
=COUNT(A1:A20) =СЧЁТ(А1:А20)
С помощью функции COUNTIF (СЧЕТЕСЛИ) можно подсчитать число элементов ряда, удовлетворяющих некоторому условию. Например, если в диапазоне А1:А20 записаны школьные отметки, формула
=COUNTIF(A1:A20;"=5")
Статистические расчёты
вычисляет число пятёрок, а формула
=COUNTIF(A1:A20;">3")
вычисляет общее число четвёрок и пятёрок (всех ячеек, значения которых больше 3).
Более сложная характеристика ряда — среднеквадратическое отклонение или стандартное отклонение , с помощью которого оценивается «разброс» значений JC]^,X2,...,x„ относительно среднего значения ряда х:
V"i=i
Среднеквадратическое отклонение — это неотрицательная величина (подумайте почему). Чем больше а^, тем больше разброс значений относительно среднего. Для вычисления стандартного отклонения в табличных процессорах используется функция STDEVP (СТАНДОТКЛОНП):
=STDEVP(A1:A20) Условные вычисления
=СТАНДОТКЛОНП(А1:А20)
Как вы знаете, в программировании важнейшую роль играют условные операторы (ветвления), позволяющие выбирать один из двух (или нескольких) вариантов обработки данных. В табличных процессорах тоже возможны условные вычисления, при которых в ячейку заносится то или иное значение в зависимости от выполнения какого-то условия.
Предположим, что в книжном интернет-магазине «Бука» доставка покупок бесплатна для тех, кто сделал заказ на сумму более 500 рублей, а для остальных доставка стоит 20% от суммы (рис. 9.25).
А L 6 С
1 Заказ .Сумма 1Доставка i
2 1234; 256 еуб.| 51 руб.|
3 1345; 128 Р16.1 26 руб.!
4 1456i 1 024 руб.1 о|
5 15651 512 py6.i 01
1576' 345jDy6., 69 руб.
Рис. 9.25
Решение вычислительных задач на компьютере
Таким образом, есть два варианта вычисления стоимости доставки, поэтому в формулах столбца С нужно использовать ветвление. Например, алгоритм вычисления значения ячейки С2 может выглядеть так: «если В2>500, записать в ячейку О, иначе записать значение В2*0,2». В программе на Паскале мы бы записали:
if В2>500 then С2:=0
else С2:=В2*0.2;
В табличных процессорах для условных вычислений используют функцию IF (ЕСЛИ):
=ЩВ2>500;0;В2*0,2) =ЕСЛИ(В2>500;0;В2*0,2)
У этой функции три аргумента, разделённые точками с запятой:
1) условие (В2>500);
2) значение ячейки в том случае, когда условие истинно (0);
3) значение ячейки в том случае, когда условие ложно (В2*0,2).
Первый аргумент может быть сложным условием, которое
строится с помощью функций NOT (НЕ, отрицание), AND (И, логическое умножение) и OR (ИЛИ, логическое сложение). Например, если бесплатная доставка распространяется только на заказы, у которых номер меньше 1500 и сумма больше 500 рублей, в ячейку С2 нужно записать такую формулу:
=IF(AND(A2<1500;B2>500);0;B2*0,2)
Здесь использовано сложное условие AND(A2<1500;B2>500), которое истинно только при одновременном выполнении обоих простых условий: А2<1500 и В2>500.
Второй и третий аргументы функции IF могут содержать вложенные вызовы этой функции. Пусть, например, для заказов стоимостью более 200 рублей (но не больше 500) стоимость доставки составляет 10% от суммы:
if В2>500 then С2:=0
else
if В2>200 then C2:=B2*0.1 else С2:=В2*0.2;
Статистические расчёты
§73
в табличном процессоре этот гшгоритм запишется в виде:
=IF(B2>500;0;IF(B2>200;B2*0,1;B2*0,2))
Связь двух рядов данных
Одна из задач обработки данных — установить взаимосвязь между величинами, процессами, явлениями. Пусть существуют два ряда данных одинаковой длины:
■^1’^2’*■ •’■^л ^ У1’У2’’“’Уп‘
Например, первый ряд — это температура воздуха за п последних дней, а второй ряд — значения атмосферного давления в те же дни. Требуется определить, есть ли связь между этими рядами, и оценить, насколько она сильная.
Для решения этой задачи чаще всего используется коэффициент корреляции (англ, correlation — взаимоотношение, связь):
О
-у)
f‘xy
Здесь хну — средние значения рядов, а неквадратические отклонения.
н а у — их сред-
Величина р^у — это безразмерный коэффициент^, причём
можно показать, что всегда -1<р^у<1. Если р^„>0, то увеличе
ху ■
ние значения х (в среднем) приводит к увеличению у; если же р^У < О, то при увеличении х значение у чаще всего уменьшается.
Чем больше модуль р^^, тем сильнее связь между двумя величинами. При р^у =-1 или Рд.ц =1 они строго связаны линейной за-
ху
висимостью у -kx + b, где ft и 6 — некоторые числа. В случае Рху =-1 эта зависимость убывающая (ft<0), а при р^у =1 — возрастающая (ft>0).
Считается, что между хну есть сильная связь, если |р^у|>0,5. При меньших значениях р„,, делать какие-то далеко идущие вы-воды не следует (связь слабая или не обнаружена).
Для вычисления коэффициента корреляции в табличных процессорах используется функция CORREL (КОРРЕЛ):
=CORREL(Al: А20;В1 :В20) =КОРРЕЛ(А1: А20;В1 :В20)
Попробуйте доказать это самостоятельно.
Решение вычислительных задач на компьютере
Обратите внимание, что у этой функции два аргумента (два ряда данных одинаковой длины), адреса двух диапазонов отделяются точкой с запятой.
Нужно учитывать, что коэффициент корреляции лучше всего обнаруживает линейную зависимость. Если связь есть, но она далека от линейной, коэффициент корреляции может быть невысок. В таких случаях для установления связи нужно использовать более сложные методы, которые мы здесь рассматривать не будем.
Вопросы и задания
1. Что изучает статистика? Как вы думаете, в чём её задача?
2. Как влияют пустые ячейки в электронной таблице на результат работы функций COUNT и AVERAGE?
3. Чем отличаются функции COUNT и COUNTIF?
4. Что показывает среднеквадратическое отклонение?
5. Что показывает коэффициент корреляции?
6. Для двух рядов коэффициент корреляции равен (-0,5). Что можно сказать о возможной связи этих рядов между собой?
7. Для двух рядов коэффициент корреляции равен 0,1. Что можно сказать о возможной связи этих рядов между собой?
О Задачи
1. В электронной таблице значение формулы =SUM(B1:B2) равно 5. Чему равно значение ячейки ВЗ, если значение формулы =AVERAGE(B1:B3) равно 3?
2. В электронной таблице значение формулы =SUM(C3:E3) равно 12. Чему равно значение формулы =AVERAGE(C3:F3), если значение ячейки F3 равно 4?
3. В электронной таблице значение формулы =SUM(A2:D2) равно 12. Чему равно значение формулы =AVERAGE(A2;E2), если значение ячейки Е2 равно 13?
4. В электронной таблице значение формулы =AVERAGE(A6:C6) равно (-2). Чему равно значение формулы =SUM(A6:D6), если значение ячейки D6 равно 6?
5. В электронной таблице значение формулы =AVERAGE(B5:E5) равно 10. Чему равно значение формулы =SUM(B5:F5), если значение ячейки F5 равно 1?
6. В электронной таблице значение формулы =AVERAGE(A1:C1) равно 6. Чему равно значение ячейки D1, если значение формулы =SUM(A1:D1) равно 7?
Статистические расчёты
§73
7. В электронной таблице значение формулы =AVERAGE(A3:D4) равно 6. Чему равно значение формулы =AVERAGE(A3:C4), если значение формулы =SUM(D3:D4) равно 6?
8. В электронной таблице значение формулы =AVERAGE(C2:D5)'paB-но 4. Чему равно значение формулы =SUM(C5:D5), если значение формулы =AVERAGE(C2:D4) равно 6?
*9. Как изменится значение ячейки СЗ, если после ввода формул переместить содержимое ячейки В2 в ВЗ?
А В С
1 1 2
2 2 6 =COUNT(Al:B2)
3 =AVERAGE(A1:C2)
10. Доставка товара в фирме «Рога и копыта» стоит 200 рублей, если в доме есть лифт. Если лифта нет, подъём на каждый этаж стоит 200 рублей:
А В С D
1 Заказ Этаж Лифт Доставка
2 12 5 нет 1000
3 34 2 да 200
4 56 8 да 200
Какую формулу нужно записать в ячейку D2?
11. При приёме на работу претенденты проходят два тура собеседования. В каждом туре выставляется оценка от 0 до 100 баллов. На работу принимаются те, кто в каждом туре набрал не менее 80 баллов.
А В С D
1 Фамилия 1-й тур 2-й тур Принят
2 Иванов 80 80 да
3 Петров 90 70 нет
4 Сидоров 85 90 да
Какую формулу нужно записать в ячейку D2?
Решение вычислительных задач на компьютере
12. Решите задачу 11 при условии, что на работу принимаются все, кто набрал 90 баллов хотя бы в одном туре собеседования.
13. Сниженный тариф на телефонные разговор — 2 рубля за минуту разговора — действует в рабочие дни после 20 часов и в выходные дни. Обычный тариф — 5 рублей за минуту. Дни в таблице нумеруются с 1 до 7 (1 — понедельник).
А В С D
1 Код Время День недели Тариф, руб.
2 12 21:12:20 2 2
3 34 17:23:50 1 5
4 56 10:21:42 7 2
Какую формулу нужно записать в ячейку D2? Момент времени 20:00:00 в формуле нужно записывать как Т1МЕ(20;0;0).
14. При покупке на сумму более 1000 рублей в магазине владельцам дисконтных карт предоставляется скидка 5%.
А В С D
1 Код Цена, руб. Дисконтная карта Со скидкой,руб.
2 12 1 200 нет 1 200
3 34 1 450 да 1 378
4 56 750 да 750
Какую формулу нужно записать в ячейку D2?
15. Во время уценки цена всех товаров, которых хранятся на складе более 6 месяцев, снижается на 20% (если цена товара больше 1000 рублей) или на 10% (если цена меньше 1000 рублей).
А В С D
1 Код Цена, руб. Хранится (месяцев) Новая цена, руб.
2 12 1 200 3 1 200
3 34 1 450 7 1 160
4 56 750 12 675
Какую формулу нужно записать в ячейку D2?
Обработка результатов эксперимента
§74
§74
Обработка результатов эксперимента
Зачем это нужно?
Многие практические задачи связаны с проведением эксперимента, в результате которого исследователь с помощью измерительных приборов получает массивы данных. Затем эти данные необходимо обработать, для того чтобы выявить закономерности, подтвердить или опровергнуть выводы теории и т, п.
Например, с помощью динамометра и линейки можно экспериментально определить жёсткость пружины (рис. 9.26). Для этого используется закон Гука, связывающий приложенную силу F, жёсткость пружины k и её удлинение А1 линейной зависимостью:
F=k-Al.
Рис. 9.26
Определив жёсткость пружины k, мы сможем вычислять её удлинение при любой нагрузке (в пределах действия закона Гука), не выполняя новых измерений.
Величина k зависит от материала пружины и её размеров. Для определения жёсткости k на нижний конец пружины подвешивают груз известной массы т (так что сила F = mg тоже известна) и измеряют удлинение пружины А1. Тогда k = FjAl.
Обычно такой эксперимент проводится несколько раз, в результате получается серия значений (для i=l,2,...,n) и соответствующих им удлинений АЦ. Для каждой пары рассчитанная жёсткость ki=Fi/Ali будет, скорее всего, различной. Конечно, можно принять за k среднее значение по всем полученным измерениям. Однако такой подход не очень хорошо обоснован с научной точки зрения. Поэтому были разработаны другие методы, один из которых рассматривается далее.
Метод наименьших квадратов
Предположим, что есть два ряда данных одинаковой длины: и Предполагается, что они связаны ли-
нейной зависимостью y=k x, где k — неизвестный коэффициент. Требуется найти оптимальное значение k, которое лучше всего соответствует исходным данным.
Решение вычислительных задач на компьютере
Поскольку речь идёт о задаче оптимизации, нужно определить функцию, которая позволяет оценить, насколько хорошо выбранная зависимость соответствует исходным данным. Предположим, что выбран некоторый коэффициент k, так что для каждого Xj можно найти соответствующее ему значение функции =k x^.
В идеале график функции должен проходить через все точки (Xj,i/i), {Х2,У2\ •••> (^л*Ул)» т. е. при всех i должно выполняться условие Yj =i/j. Однако на практике этого, скорее всего, не будет (рис. 9.27).
Отклонение полученной линии от исходных данных определяется разностями У; -у^: чем они меньше (по модулю), тем лучше соответствие. Однако сумма этих разностей даёт неправильную оценку точности — слагаемые с разными знаками могут скомпенсировать друг друга. Чтобы решить эту проблему, можно сложить квадраты этих величин и выбрать k так, чтобы эта сумма
Е = -у^)2 =(Y, -J/i)2 +(У2 -У2)2+...-КУл -Ул)"
1=1
была минимальной. Такой подход называется методом наименьших квадратов. Впервые его предложил немецкий математик К. Ф. Гаусс.
Как найти коэффициент k наилучшим образом, т. е. так, чтобы сумма квадратов Е была минимальной? Для этого заменим У^ н&k^x^ и раскроем скобки в формуле для вычисления £:
(Yj -1/^)2 ={k x^ -z/i)2 =k^xf +yf.
Группируя слагаемые, содержащие и k, получаем:
E = Ak^ -Bk + C,
n n n
где A = , В = 2^x^ i/j и C = ^yf. График зависимости E от k —
i=l i=l i=l
это парабола, причём её ветви направлены вверх, потому что
Обработка результатов эксперимента
§74
л > о (это сумма квадратов). Вершина параболы (и минимум функ-
ции!) находится в точке k =-, это и будет оптимальное решение.
2А
Таким образом, алгоритм для определения оптимального значения k приобретает вид:
1) вычислить коэффициенты параболы А = и В = 2'^х^у^;
В i=l i=l
2) вычислить k =-.
2А
Решение получилось простым только потому, что мы выбрали очень простую функцию, линейную с нулевым свободным членом. В более сложных случаях строгое решение задачи оптимизации требует знания высшей математики.
Если исходные данные записаны в массивах л:[1..^] и i/[l..iV], программа для рассмотренного случая выглядит так:
А:=0; В:=0
нц для i от 1 до N
А:=А+х[i]*х[i] B:=B+x[i]*y[i] кц
к:=В/А
А:=0; В:=0;
for i:=l to N do begin
A:=A+x[i]*x[i]; B:=B+x[i]*y[i]; end; k:=B/A;
Чтобы избавиться от лишних операций, умножение на 2 при вычислении В и деление на 2 при вычислении k не выполняется (применение двух этих операций не меняет результат).
Для решения задачи методом наименьших квадратов можно использовать табличные процессоры с модулем поиска решения. Пусть в результате измерений получены точки (1; 1,1), (2; 1,8) и (3; 3,5). Занесём эти координаты в столбцы А и В, в ячейку В1 запишем начальное приближение для k, а в столбец С — значения функции у - k x для значений х из столбца А (рис. 9.28).
А
1 к 1,000
2 Е =SUMXMY2(B5;B7;C5:C7)
X У Y
S ■ 1 1.1 =$В$ГА5
б 2 1.8 =$В$ГАБ
7 3 3.5 =$В$ГА7
Рис. 9.28
Решение вычислительных задач на компьютере
Величина Е — это сумма квадратов разностей двух рядов, которая вычисляется с помощью функции SUMXMY2 (СУММКВРАЗН). У этой функции два аргумента — ряд у (измеренные значения в столбце В) и ряд У (вычисленные значения функции в столбце С). Задача оптимизации — найти минимальное значение Е (в ячейке В2), изменяя значение k в ячейке В1 — решается с помощью надстройки «Поиск решения».
Восстановление зависимостей
Пусть заданы пары значений х и у, и предполагается, что они связаны некоторой зависимостью у = f{x), которую нужно найти для того, чтобы вычислять значение функции в других точках, для которых значения у неизвестны. Такая задача называется задачей восстановления зависимости.
Если вид функции не задан, эта задача некорректна, потому что через заданные точки можно провести сколько угодно различных линий (графиков функций), и невозможно сказать, какая из них лучше подходит (рис. 9.29).
Поэтому для того, чтобы сделать задачу осмысленной, нужно заранее задать вид функции, так что останется только найти её неизвестные коэффициенты.
Откуда взять вид функции? В некоторых случаях он известен из физических законов, описывающих явление (так было в примере с исследованием закона Гука). Иногда вид зависимости можно определить по внешнему виду расположения точек. Также можно попробовать функции разного типа и выбрать лучший вариант. Часто используют следующие типы функций (рис. 9.30):
Обработка результатов эксперимента
§74
• линейную I/= а • X + 6;
• логарифмическую I/=а-Inх +ft;
• показательную (экспоненциальную) у = а Ь^;
• степенную I/=а •X*’.
Линия тренде для рядов даннык 'Столбец В*
Тип |линия|
Тип регрессии-------
(• Оииегиый
f' Логарифмический Экспоненциальный Степень
Уравнение -17 (Показать уравнение |7 Показать козффиииент детериинации (R>)
(Ж
Отмена
Огфавка
установить
Рис. 9.30
Задача сводится к тому, чтобы выбрать коэффициенты а и ft наилучшим образом. Для её решения «вручную» нужно применять методы вычислительной математики, выходящие за рамки школьного курса. Однако в современных табличных процессорах есть встроенные возможности для решения задачи восстановления зависимостей. Полученные графики оптимальных функций называются линиями тренда (англ, trend — основное направление развития).
Сначала нужно ввести исходные данные (координаты точек) в таблицу и построить по ним диаграмму типа Диаграмма XY (в Excel — диаграмма Точечная). Лучше оставить на диаграмме только точки, не соединяя их линией.
Для того чтобы построить линию тренда, надо щёлкнуть правой кнопкой мыши на одной из точек и выбрать пункт Вставить линию тренда из контекстного меню. В появившемся окне можно выбрать вид зависимости. Если установить флажок Показать уравнение, уравнение линии тренда будет показано на диаграмме. Флажок Показать коэффициент детерминации (R2) позволяет
Решение вычислительных задач на компьютере
увидеть, насколько точно полученная линия соответствует исходным данным. Коэффициент вычисляется по формуле
Д2 =1-М---------,
ZO/i -у)^
i=l
где через у обозначено среднее значение ряда у. Дробь, которая вычитается из единицы, — это дисперсия ошибки приближения, делённая на дисперсию ряда у. Чем меньше это отношение (и чем больше коэффициент R^), тем больше найденная зависимость соответствует исходным данным. В лучшем случае = 1, при этом у^ = У; для всех i , т. е. все значения функции совпадают с заданными.
Из приведённой формулы видно, что имеет наибольшее
П
значение, когда сумма квадратов отклонений Е = ^(у^ - У^ ми-
1=1
нимальна. Это значит, что задача поиска максимума R^ решается методом наименьших квадратов. Если нужно найти неизвестные коэффициенты функции, которая не входит в стандартный набор (например, у =а• sinfrx+ с), можно применить метод наименьших квадратов с помощью надстройки «Поиск решения».
Прогнозирование
Во многих задачах (например, в экономике) в результате обработки данных нужно сделать прогноз. Если найдена зависимость у = f(x), эта задача решается просто — нужно найти значения функции для тех значений х, которые нас интересуют. Однако может получиться так, что функция, которая очень хорошо соответствует имеющимся данным (см. функцию y = f(x) на рис. 9.31), оказывается непригодна для прогноза.
Обработка результатов эксперимента
§74
в таких случаях для решения задачи прогнозирования нужно выбирать другую функцию, которая дает меньшее значение , но лучше показывает закономерность изменения величины (например, возрастаюш;ий характер функции).
Вопросы и задания
1. Объясните, почему экспериментгшьные исследования требуют специальных методов обработки данных.
2. Объясните суть метода наименьших квадратов. Почему можно считать такой подход решением задачи оптимизации?
Подготовьте сообщение
а) «Интерполяция»
б) «Экстраполяция*
в) «Аппроксимация»
Задачи
1. Результаты серии измерений, сделанных для определения жёсткости пружины на основе закона Гука, записаны в таблицу:
F,H 1 3 6 10
М, м 0,028 0,070 0,170 0,260
Используя метод наименьших квадратов, определите жёсткость пружины. Решите задачу разными способами (с помощью собственной программы и табличного процессора), сравните результаты.
*2. Используя те же данные, что и в задаче 1, найдите жёсткость пружины другим способом. Введём величину, обратную жёсткости: т) = 1/Л, тогда Д/ = т^ Р. Сначала, применив метод наименьших квадратов, найдите г|, а затем рассчитайте k = 1/г). Сравните результат с тем, что получилось в задаче 1. Объясните расхождение.
3. Почему задача восстановления зависимости некорректна, если не задан вид функции?
4. Доходы начинающей фирмы (в тысячах рублей) за первые 5 лет работы приведены в таблице:
Год 1 2 3 4 5
Доход 93 187 270 321 350
О
Решение вычислительных задач на компьютере
с помощью табличного процессора найдите зависимость дохода от года работы (выберите лучший из стандартных вариантов, с наибольшим значением R^). С помощью этой зависимости сделайте прогноз развития фирмы на 2 года вперед.
*5. При изучении волн измерили отклонение уровня поверхности воды у от «нулевого* уровня в одной точке в разные моменты времени f.
t 0 0,2 0,4 0,6 0,8 1
у 1 2 1,2 -0,6 -2 -1,5
Предполагается, что волна описывается формулой у =a-sin{b-t+с), где а, Ь и с — некоторые числа. Определите неизвестные коэффициенты методом наименьших квадратов с помощью табличного процессора. В качестве начального приближения можно выбрать а »1; й « 4; с «1.
Практические работы к главе 9
Работа
Работа
Работа
Работа
Работа
Работа
Работа
Работа
Работа
X» 62
X» 63
X» 64
X» 65
X» 66
Хо 67
Х2 68
X» 69
Хо 70
Х2 71
X» 72
«Решение уравнений методом перебора*
«Решение уравнений методом деления отрезка пополам *
«Решение уравнений в табличных процессорах» «Вычисление длины кривой»
«Вычисление площади фигуры»
«Оптимизация. Метод дихотомии»
«Оптимизация с помощью табличных процессоров» «Статистические расчеты»
«Условные вычисления»
«Метод наименьших квадратов»
«Линии тренда»
ЭОР к главе 9 на сайте ФЦИОР (http//fcior.edu.ru)
Точность вычислений
Особенности выполнения вычислений на ЭВМ. Потеря точности
• Уравнения с одной переменной. Корни уравнения. Линейные уравнения
Дискретизация сигналов
Задачи оптимизации. Динамическое программирование
• Основные алгоритмы работы со структурами данных
Обработка результатов эксперимента
§74
Самое важное в главе 9
• Погрешность вычислений — это разница между вычисленным значением величины и её точным (истинным) значением. Погрешность бывает абсолютная и относительная (в процентах). Для оценки точности измерений и расчётов более полезна относительная погрешность.
• Точность вычислений определяется точностью исходных данных и погрешностями метода.
• Компьютер позволяет легко находить приближённые решения многих задач, которые трудно решаются аналитически (или не решаются вообще).
• Многие приближённые методы решения уравнений — итерационные, т. е. основаны на многократном повторении некоторого алгоритма, который позволяет на каждом шаге приближаться к точному решению. Процедура заканчивается, когда отклонение полученного приближённого решения от точного становится меньше заданной величины е.
• Дискретизация — необходимый этап подготовки вычислительных задач для решения на компьютере. Чтобы повысить точность, нужно уменьшать шаг дискретизации, но это увеличивает объём вычислений.
• Оптимизация — это поиск наилучшего решения в заданных условиях. В задачах оптимизации необходимо ввести целевую функцию, для которой требуется найти минимум или максимум. Кроме того, в большинстве практических случаев нужно задать ограничения на допустимые значения переменных.
• Большинство приближённых методов оптимизации позволяет искать только локальный минимум (максимум), в этом случае результат оптимизации зависит от выбора начального приближения.
• Цель статистических расчётов — выявить закономерности путём математической обработки больших массивов данных.
0 Для того чтобы задача восстановления зависимости по точкам была корректной, необходимо заранее выбрать вид функции, так что останется определить лишь её неизвестные коэффициенты.
Глава 10
Информационная безопасность
§75
Основные понятия
Зависимость современных организаций от компьютерных технологий стала настолько сильной, что вывод из строя компьютерной сети или программного обеспечения может остановить работу предприятия. Чтобы этого не произошло, нужно соблюдать правила информационной безопасности.
О
Информационная безопасность — это защищённость информации от любых действий, в результате которых владельцам или пользователям информации может быть нанесён недопустимый ущерб. Причиной такого ущерба может быть искажение или утеря информации, а также неправомерный доступ к ней.
Прежде всего в защите нуждаются государственная и военная тайны, а также коммерческая, юридическая и врачебная тайны. Необходимо защищать личную информацию: паспортные данные, данные о банковских счетах, пароли на сайтах, а также любую информацию, которую можно использовать для шантажа, вымогательства и т. п.
Конечно, невозможно защититься от любых потерь, поэтому задача состоит в том, чтобы исключить именно недопустимый ущерб. С точки зрения экономики, средства защиты не должны стоить больше, чем возможные потери.
Защита информации — это меры, направленные на то, чтобы не потерять информацию, не допустить её искажения, а также не допустить, чтобы к ней получили доступ люди, не имеющие на это права. В результате нужно обеспечить:
• доступность информации — возможность получения информации за приемлемое время;
• целостность (отсутствие искажений) информации;
• конфиденциальность информации (недоступность для посторонних).
Основные понятия
§7Э
Доступность информации нарушается, например, когда оборудование выходит из строя или веб-сайт не отвечает на запросы пользователей в результате массовой атаки вредоносных программ через Интернет.
Нарушения целостности информации — это кража или искажение информации, например подделка сообщений электронной почты и других цифровых документов.
Конфиденциальность информации нарушается, когда информация становится известной тем людям, которые не должны о ней знать (происходит перехват секретной информации).
В компьютерных сетях защищённость информации снижается в сравнении с отдельным компьютером, потому что:
• в сети работает много пользователей, их состав меняется;
• есть возможность незаконного подключения к сети;
• существуют уязвимости в сетевом программном обеспечении;
• возможны атаки взломщиков и вредоносных программ через сеть.
В России вопросы, связанные с защитой информации, регулирует закон «Об информации, информационных технологиях и о защите информации».
Технические средства защиты информации — это замки, решётки на окнах, системы сигнализации и видеонаблюдения, другие устройства, которые блокируют возможные каналы утечки информации или позволяют их обнаружить.
Программные средства обеспечивают доступ к данным по паролю, шифрование информации, удаление временных файлов, защиту от вредоносных программ и др.
Организационные средства включают:
• распределение помещений и прокладку линий связи таким образом, чтобы злоумышленнику было сложно до них добраться;
• политику безопасности организации.
Серверы, как правило, находятся в отдельном (охраняемом) помещении и доступны только администраторам сети. Важная информация должна периодически копироваться на резервные носители (диски или магнитную ленту) для сохранения её в случае сбоев. Обычные сотрудники (не администраторы):
• имеют право доступа только к тем данным, которые им нужны для работы;
О
Информационная безопасность
€i
не имеют права устанавливать программное обеспечение; раз в месяц должны менять пароли.
Самое слабое звено любой системы защиты — это человек. Некоторые пользователи могут записывать пароли на видном месте (чтобы не забыть) и передавать их другим, при этом возможность незаконного доступа к информации значительно возрастает. Поэтому очень важно обучить пользователей основам информационной безопасности.
Большинство утечек информации связано с инсайдерами (англ, inside — внутри) — недобросовестными сотрудниками, работающими в фирме. Известны случаи утечки закрытой информации не через ответственных сотрудников, а через секретарей, уборщиц и другой вспомогательный персонал. Поэтому ни один человек не должен иметь возможности причинить непоправимый вред (в одиночку уничтожить, украсть или изменить данные, вывести из строя оборудование).
Вопросы и задания
1. Что такое информационная безопасность?
2. Что входит в понятие «защита информации»?
3. На какие группы делятся средства защиты информации?
4. Какие меры безопасности обычно применяются в организациях?
5. Почему при объединении компьютеров в сеть безопасность снижается?
6. Кто такие инсайдеры?
§76
Вредоносные программы
Что такое компьютерный вирус?
О
Компьютерный вирус — это программа, способная создавать свои копии (не обязательно совпадающие с оригиналом) и внедрять их в файлы и системные области компьютера. При этом копии могут распространяться дальше.
Как следует из этого определения, основная черта компьютерного вируса — это способность распространяться при запуске.
Вредоносные программы
§76
Вирус — это один из типов вредоносных программ. Однако очень часто вирусами называют любые вредоносные программы (англ, malware).
Вредоносные программы — это программы, предназначенные для незаконного доступа к информации, для скрытого использования компьютера или для нарушения работы компьютера и компьютерных сетей.
О
Зачем пишут такие программы? Во-первых, с их помощью можно получить управление компьютером пользователя и использовать его в своих целях. Например, через заражённый компьютер злоумышленник может взламывать сайты и незаконно переводить на свой счёт деньги. Некоторые программы блокируют компьютер и для продолжения работы требуют отправить платное SMS-сообщение.
Зараженные компьютеры, подключенные к сети Интернет, могут объединяться в сеть специального типа — ботнет (от англ. robot — робот и network — сеть). Такая сеть часто состоит из сотен тысяч компьютеров, обладающих в сумме огромной вычислительной мощностью. По команде «хозяина» ботнет может организовать атаку на какой-то сайт. В результате огромного количества запросов сервер не справляется с нагрузкой, сайт становится недоступен, и бизнесмены несут большие денежные потери. Такая атака называется DoS-атакой^ (англ. DoS — Denial of Service — отказ в обслуживании). Кроме того, ботнеты могут использоваться для подбора паролей, рассылки спама (рекламных электронных сообщений) и другой незаконной деятельности.
Во-вторых, некоторые вредоносные программы предназначены для шпионажа — передачи по Интернету секретной информации с вашего компьютера: паролей доступа к сайтам, почтовым ящикам, учётным записям в социальных сетях, банковским счетам и электронным платёжным системам. В результате таких краж пользователи теряют не только данные, но и деньги.
В-третьих, иногда вирусы пишутся ради самоутверждения программистами, которые по каким-то причинам не смогли при-
Здесь речь идёт, строго говоря, о распределённой DoS-атаке (англ. DDoS — Distributed DoS), которая проводится сразу со многих компьютеров.
10—49
Информационная безопасность
О
менить свои знания для создания полезного ПО. Такие программы нарушают нормальную работу компьютера: время от времени перезагружают его, вызывают сбои в работе операционной системы и прикладных программ, уничтожают данные.
Наконец, существуют вирусы, написанные ради шутки. Они не портят данные, но приводят к появлению звуковых или зрительных эффектов (проигрывание мелодии; искажение изображения на экране; кнопки, убегающие от курсора и т. п.).
Создание и распространение компьютерных вирусов и вредоносных программ — это уголовные преступление, которое предусматривает (в особо тяжких случаях) наказание до 7 лет лишения свободы (Уголовный кодекс РФ, статья 273).
Признаки заражения вирусом:
• замедление работы компьютера;
уменьшение объема свободной оперативной памяти;
• зависание, перезагрузка или блокировка компьютера;
• ошибки при работе ОС или прикладных программ;
- изменение длины файлов, появление новых файлов (в том числе скрытых);
• рассылка сообщений по электронной почте без ведома автора.
О
Для того чтобы вирус смог выполнить какие-то действия, он должен оказаться в памяти в виде программного кода и получить управление компьютером.
Поэтому вирусы заражают не любые данные, а только программный код, который может выполняться. Например:
• исполняемые программы (с расширениями ехе, сот);
• загрузочные секторы дисков;
• пакетные командные файлы (bat);
• драйверы устройств;
• библиотеки динамической загрузки (dll), функции из которых вызываются из прикладных программ;
• документы, которые могут содержать макросы — небольшие программы, выполняющиеся при нажатии на клавиши или выборе пункта меню; например, макросы нередко используются в документах пакета Microsoft Office;
• веб-страницы (в них можно внедрить программу-скрипт, которая выполнится при просмотре страницы на компьютере пользователя).
Вредоносные программы
§76
в отличие от кода программ файлы с данными (например, тексты, рисунки, звуковые и видеофайлы) только обрабатываются, но не выполняются, поэтому заложенный в них код никогда не должен получить упргшление компьютером. Однако из-за ошибок в программном обеспечении может случиться так, что специально подобранные некорректные данные вызовут сбой программы обработки и выполнение вредоносного кода^. Таким образом, существует некоторый шанс, что вредоносная программа, внедрённая в рисунок или видеофайл, все-таки запустится.
Сейчас существуют два основных источника заражения вредоносными программами — флэш-диски и компьютерные сети. Компьютер может быть заражён при:
• запуске заражённого файла;
• загрузке с заражённого диска CD/DVD или флэш-диска;
• автозапуске заражённого диска CD/DVD или флэш-диска (вирус автоматически запускается из файла autorun.inf в корневом каталоге диска);
• открытии заражённого документа с макросами;
• открытии сообщения электронной почты с вирусом или запуске заражённой программы, полученной в приложении к сообщению;
• открытии веб-страницы с вирусом;
• установке активного содержимого для просмотра веб-страницы.
Кроме того, есть вирусы-черви, которые распространяются по компьютерным сетям без участия человека. Они могут заразить компьютер даже тогда, когда пользователь не сделал никаких ошибочных действий.
О
Типы вредоносных программ
К вредоносным программам относятся компьютерные вирусы, черви, троянские программы и др. По «среде обитания» обычно выделяют следующие типы вирусов:
• файловые — внедряются в исполняемые файлы, системные библиотеки и т. п.;
В 2002 г. был обнаружен вирус, который внедрялся в рисунки формата JPEG. Однако он получал управление только из-за ошибки в системной библиотеке Windows, которая была быстро исправлена.
Информационная безопасность
загрузочные — внедряются в загрузочный сектор диска или в главную загрузочную запись жёсткого диска (англ. MBR — Master Boot Record)’, опасны тем, что загружаются в память раньше, чем ОС и антивирусные программы;
• макровирусы — поражают документы, в которых могут быть макросы;
• скриптовые вирусы — внедряются в командные файлы или в веб-страницы (записывая в них код на языке VBScript или JavaScript);
, сетевые вирусы — распространяются по компьютерным сетям.
Некоторые вирусы при создании новой копии немного меняют свой код, для того чтобы их было труднее обнаружить. Такие вирусы называют полиморфными (от греч. лоЛ.и — много, рорсрг) — форма, внешний вид).
Червь — это вредоносная программа, которая распространяется по компьютерным сетям. Наиболее опасны сетевые черви, которые используют «дыры» (ошибки в защите, уязвимости) операционных систем и распространяются очень быстро без участия человека. Червь посылает по сети специальный пакет данных — эксплойт (англ, exploit — эксплуатировать), который позволяет выполнить код на удалённом компьютере и внедриться в систему.
Как правило, вскоре после обнаружения уязвимости выпускается обновление программного обеспечения («заплатка*, «патч»); если его установить, то червь становится неопасен. К сожалению, системные администраторы не всегда вовремя устанавливают обновления. Это приводит к эпидемиям сетевых червей, которые по статистике вызывают наибольшее число заражений. Заражённые компьютеры используются для рассылки спама или массовых DoS-атак на сайты в Интернете.
Почтовые черви распространяются как приложения к сообщениям электронной почты. Они представляют собой программы, которые при запуске заражают компьютер и рассылают свои копии по всем адресам из адресной книги пользователя. Из-за этой опасности многие почтовые серверы (например, mail.google.com) не разрешают пересылку исполняемых файлов.
Чтобы заставить пользователя запустить червя, применяются методы социальной инженерии: текст сообщения составляется так, чтобы заинтересовать человека и спровоцировать его на
Вредоносные программы
§76
запуск программы, приложенной к письму. В некоторых случаях программа-вирус упакована в архив и защищена паролем, но находится немало людей, которые распаковывают его (пароль указывается в письме) и запускают программу. Часто в почтовых сообщениях содержится только ссылка на сайт, содержащий вирус.
Иногда файл, пришедший как приложение к письму, имеет двойное расширение, например:
СуперКартинка.jpg
. ехе
В самом деле это программа (расширение имени файла ехе), но пользователь может увидеть только первые две части имени и попытаться открыть такой «рисунок».
Существуют черви, которые могут распространяться через файлообменные сети, чаты и системы мгновенных сообщений (например, ICQ), но они мало распространены.
Ещё одна группа вредоносных программ — троянские программы, или «троянцы» (трояны). Троянский конь — это огромный деревянный конь, которого древние греки подарили жителям Трои во время Троянской войны. Внутри него спрятались воины, которые ночью выбрались, перебили охрану и открыли ворота города. Троянские программы проникают на компьютер под видом «полезных» программ, например кодеков для просмотра видео или экранных заставок. В отличие от вирусов и червей они не могут распространяться самостоятельно и часто «путешествуют» вместе с червями. Среди «троянцев» встречаются:
клавиатурные шпионы — передают «хозяину» все данные, вводимые с клавиатуры (в том числе коды доступа к банковским счетам и т. п,);
• похитители паролей — передают пароли, запомненные, например, в браузерах;
• утилиты удалённого управления — позволяют злоумышленнику управлять компьютером через Интернет (например, загружать и запускать любые файлы);
• логические бомбы — при определённых условиях (дата, время, команда по сети) уничтожают информацию на дисках.
Большинство существующих вирусов написано для ОС Windows, которая установлена более чем на 90% персональных компьютеров.
Информационная безопасность
Известны также вирусы для Мае 0S и Linux, но не каждому удается их запустить. Дело в том, что обычный пользователь (не администратор) в этих операционных системах не имеет права на изменение системных файлов, поэтому Мае OS и Linux считают защищёнными от вирусов. Кроме того, вирусы часто полагаются на то, что системные функции размещаются в памяти по определённым адресам. При сборке ядра Linux из исходных кодов эти адреса могут меняться, поэтому вирус, работающий на одном дистрибутиве, может не работать на других.
Вопросы и задания
1. Что такое компьютерный вирус? Чем он отличается от других программ?
2. Что такое вредоносные программы? Какие вредоносные программы вы знаете?
3. Перечислите признаки заражения компьютера вирусом.
4. Какие вредные действия могут совершать вредоносные программы?
5. Какие объекты могут быть заражены вирусами?
6. Какие объекты не заражаются вирусами?
7. При каких действиях пользователя возможно заражение вирусом?
8. Является ли создание и распространение вирусов уголовным преступлением?
9. Какие типы вирусов вы знаете?
10. Что означает сокращение MBR?
11. Чем опасны загрузочные вирусы?
12. Что такое макровирусы? Какие файлы они поражают?
13. Что могут заражать скриптовые вирусы?
14. Что такое полиморфные вирусы? Почему их сложно обнаруживать?
15. Что такое сетевой червь?
16. Что такое эксплойт?
17. Почему необходимо сразу устанавливать обновления для операционных систем?
18. С какими целями могут быть использованы компьютеры, заражённые сетевым червем?
19. Почему многие почтовые серверы запрещают пересылку исполняемых файлов?
20. Что такое социальная инженерия? Как она используется авторами вирусов?
21. Что такое троянские программы? Какие типы троянских программ вы знаете?
22. Какие операционные системы лучше защищены от вирусов? Почему?
Защита от вредоносных программ
1
Подготовьте сообщение:
а) «Сетевые черви»
б) «Социальная инженерия»
в) «Троянские программы»
г) «Вредоносные программы для Linux и MacOS»
д) «Вредоносные программы и закон»
§77
Защита от вредоносных программ
Антивирусные программы
Антивирус — это программа, предназначенная для борьбы с вредоносными программами.
О
Антивирусы выполняют три основные задачи:
1) не допустить заражение компьютера вирусом;
2) обнаружить присутствие вируса в системе;
3) удалить вирус без ущерба для остальных данных.
Код большинства вирусов содержит характерные цепочки байтов — сигнатуры (от лат. signare — подписать). Если в файле обнаруживается сигнатура какого-то вируса, можно предположить, что файл заражён. Такой подход используется всеми антивирусными программами. Сигнатуры известных вирусов хранятся в базе данных антивируса, которую нужно регулярно обновлять через Интернет.
Современные антивирусы — это программные комплексы, состоящие из нескольких программ. Чаще всего они включают антивирус-сканер (иногда его называют антивирус-доктор) и антивирус-монитор.
Для того чтобы антивирус-сканер начал работу, пользователь должен его запустить и указать, какие файлы и папки нужно проверить. Это «защита по требованию». Сканеры используют два основных метода поиска вирусов:
• поиск в файлах сигнатур вирусов, которые есть в базе данных; после обнаружения файл с вирусом можно вылечить, а если это не получилось — удалить;
i
Информационная безопасность
• эвристический анализ (греч, еирг1ка — «нашёл!»), при котором программа ищет в файле код, похожий на вирус.
Эвристический анализ часто позволяет обнаруживать полиморфные вирусы (изменяющие код с каждым новым заражением), но не гарантирует это. Кроме того, случаются ложные срабатывания, когда «чистый» файл попадает под подозрение.
Главный недостаток сканеров состоит в том, что они не могут предотвратить заражение компьютера, потому что начинают работать только при ручном запуске.
Антивирусы-мониторы — это программы постоянной защиты, они находятся в памяти в активном состоянии. Их основная задача — не допустить заражения компьютера и получения заражённых файлов извне. Для этого мониторы:
• проверяют «на лету» все файлы, которые копируются, перемещаются или открываются в различных прикладных программах;
• проверяют используемые флэш-диски;
• перехватывают действия, характерные для вирусов (форматирование диска, замена и изменение системных файлов) и блокируют их;
проверяют весь поток данных, поступающий из Интернета (сообщения электронной почты, веб-страницы, сообщения ICQ).
Мониторы ведут непрерывное наблюдение, блокируют вирус в момент заражения. Иногда они могут перехватить и неизвестный вирус (сигнатуры которого нет в базе), обнаружив его подозрительные действия.
Главный недостаток антивирусов-мониторов — значительное замедление работы системы, особенно на маломощных компьютерах. Кроме того, мониторы фактически встраиваются в операционную систему, поэтому ошибки разработчиков антивируса могут привести к печальным последствиям (вплоть до удаления системных библиотек и вывода ОС из строя). Бывает и так, что при запущенном мониторе некоторые программы работают неправильно или вообще не работают. Тем не менее не рекомендуется отключать монитор, особенно если вы работаете в Интернете или переносите файлы с помощью флэш-дисков.
Защита от вредоносных программ
§77
Современные антивирусы частично защищают компьютер ещё и от:
• фишинга — выманивания паролей для доступа на сайты Интернета с помощью специально сделанных веб-страниц, которые внешне выглядят так же, как «официальные» сайты;
• рекламных баннеров и вспльшающих окон на веб-страницах;
• спама — рассылки нежелательных рекламных сообщений по электронной почте.
Большинство антивирусных программ — условно-бесплатные (англ, shareware), пробные версии с ограниченным сроком действия можно свободно загрузить из Интернета. Наиболее известны антивирусы \Ук AVP (www.kaspersky.ru), DrWeb (www. drweb.com), Nod32 (www.eset.com), ^ McAfee (home.mcafee. com).
Ha многих сайтах (www.kaspersky.ru, www.freedrweb.com) доступны для скачивания лечащие программы-сканеры, которые бесплатны для использования на домашних компьютерах. В отличие от полных версий в них нет антивируса-монитора, и базы сигнатур не обновляются.
Существуют антивирусы, бесплатные для использования на домашних компьютерах, например Microsoft Security Essentials (www.microsoft.com), ^ Avast Home (www.avast.com), ^ Antivir Personal (free-av.com), ^ AVG Free (free.grisoft.com). Антивирус
ClamAV (www.clamav.net) распространяется свободно с исходным кодом.
На сайтах некоторых компаний можно найти онлайновые антивирусы (например, https://www.kaspersky.ru/virusscanner). Они устанавливают на компьютер специальный сканирующий модуль и проверяют файлы и оперативную память. Как правило, онлайновые антивирусы могут обнаружить вирусы, но не удаляют их, предлагая приобрести коммерческую версию.
Брандмауэры
Для защиты отдельных компьютеров и сетей от атак из Интернета (в том числе и вирусных) используются брандмауэры (нем. Brandmauer — стена между зданиями для защиты от распространения огня). Их также называют сетевыми экранами или фаейрволами (от англ, firewall — противопожарная стена). Брандмауэры запрещают передачу данных по каналам связи, которые часто используют вирусы и программы для взлома сетей.
Информационная безопасность
На рисунке 10.1 показана защита одного компьютера с помощью брандмауэра, точно так же защищаются от угроз из Интернета локальные сети.
Брандмауэр Рис. 10.1
Брандмауэр входит в состав современных версий ОС Windows, в ядро Linux также включён встроенный брандмауэр Netfilter. Иногда устанавливают дополнительные брандмауэры, например Agnitum Outpost (www.agnitum.com), ^ Kerio Winroute Firewall (kerio.ru) или бесплатную программу ^ Comodo Personal Firewall (WWW. personal! ire wall. comodo. com).
Меры безопасности
Главный вред, который могут нанести вредоносные программы, — это потеря данных или паролей доступа к закрытой информации.
Чтобы уменьшить возможный ущерб, рекомендуется регулярно делать резервные копии важных данных на дисках CD/DVD или флэш-дисках.
Если вы работаете в сети, желательно включать антивирус-монитор и брандмауэр. Монитор сразу сообщит об опасности, если вставленный флэш-диск содержит вирус. Все новые файлы (особенно программы!) нужно проверять с помощью антивируса-сканера.
Не рекомендуется открывать подозрительные сообщения электронной почты, полученные с неизвестных адресов, особенно файлы-приложения (помните про методы социальной инженерии — заинтересовать жертву и заставить запустить программу). Опасно также переходить по ссылкам в тексте писем, с большой вероятностью они ведут на сайты, зараженные вирусами.
Если компьютер заражён, нужно отключить его от компьютерной сети и запустить антивирус-сканер. Очень часто это позволяет удалить вирус, если его сигнатура есть в базе данных. Если антивирус не был установлен раньше, можно попробовать установить его на заражённый компьютер, но это не всегда приводит к успеху (вирус может блокировать установку антивируса).
В
Защита от вредоносных программ
§77
Если антивирус-сканер не обнаруживает вирус или не может его удалить, можно попытаться (желательно с другого компьютера) найти в Интернете бесплатную утилиту для лечения с новыми базами сигнатур. Например, утилита Curelt (www.freedrweb.com) не требует установки и может быть запущена с флэш-диска. Даже если удалить вирус не удастся, скорее всего, он будет обнаружен, и программа покажет его название. Следующий шаг — искать в Интернете утилиту для удаления именно этого вируса (например, ряд утилит можно найти на сайте support.kaspersky.ru).
В особо тяжёлых случаях для уничтожения вирусов приходится полностью форматировать жёсткий диск компьютера, при этом все данные теряются.
Вопросы и задания
1. Что такое антивирус? Какие задачи он решает?
2. Что такое сигнатура?
3. Почему нужно регулярно обновлять базы сигнатур антивирусов?
4. Чем отличается антивирус-сканер от антивируса-монитора?
5. Что значит «защита по требованию»?
6. Что такое эвристический анализ? В чём его достоинства и недостатки?
7. Какие функции у антивируса-монитора? Каковы его недостатки?
8. Что такое фишинг?
9. Что такое спам?
10. Какие ограшичения есть у пробных версий коммерческих антивирусов?
11. Что такое онлайновый антивирус?
12. Что такое брандмауэр? Зачем он нужен?
13. В чём заключается основной вред, наносимый вирусами? Как можно уменьшить возможные потери?
14. Как можно улучшить безопасность компьютера при работе в сети Интернет?
15. Какие меры безопасности необходимы при работе с электронной почтой?
16. Какие действия можно предпринять, если компьютер заражен вирусом?
Подготовьте сообщение
а) «Бесплатное антивирусное программное обеспечение»
б) «Онлайновые антивирусы»
в) «Настройка брандмауэра»
Информационная безопасность
О
§78
Шифрование
Один из методов защиты информации от неправомерного доступа — это шифрование, т. е. кодирование специального вида.
Шифрование — это преобразование (кодирование) открытой информации в зашифрованную, недоступную для понимания посторонними.
Шифрование применяется в первую очередь для передачи секретной информации по незащищённым каналам связи. Шифровать можно любые данные — тексты, рисунки, звук, базы данных и т. д.
Человечество применяет шифрование с того момента, как появилась секретная информация, которую нужно было скрыть от врагов. Первое известное науке шифрованное сообщение — египетский текст, в котором вместо принятых тогда иероглифов были использованы другие знаки.
Методы шифрования и расшифровывания сообщения изучает наука криптология, история которой насчитывает около четырех тысяч лет. Она состоит из двух ветвей: криптографии и криптоанализа.
Криптография — это наука о способах шифрования информации. Криптоанализ — это наука о методах и способах вскрытия шифров.
О
Обычно предполагается, что сам алгоритм шифрования известен всем, но неизвестен его ключ, без которого сообщение невозможно расшифровать. В этом заключается отличие шифрования от простого кодирования, при котором для восстановления сообщения достаточно знать только алгоритм кодирования.
Ключ — это параметр алгоритма шифрования (шифра), позволяющий выбрать одно конкретное преобразование из всех вариантов, предусмотренных алгоритмом. Знание ключа позволяет свободно зашифровывать и расшифровывать сообщения.
Шифрование
Jflf
Все шифры (системы шифрования) делятся на две группы — симметричные и несимметричные (с открытым ключом).
Симметричный шифр означает, что и для шифрования, и для расшифровывания сообш;ений используется один и тот же ключ. В системах с открытым ключом используются два ключа — открытый и закрытый, которые связаны друг с другом с помощью некоторых математических зависимостей. Информация шифруется с помощью открытого ключа, который доступен всем желающим, а расшифровывается с помощью закрытого ключа, известного только получателю сообщения.
Криптостойкость шифра — это устойчивость шифра к расшифровке без знания ключа.
О
Стойким считается алгоритм, который для успешного раскрытия требует от противника недостижимых вычислительных ресурсов, недостижимого объёма перехваченных сообщений или такого времени, что по его истечении защищённая информация будет уже не актуальна.
Шифр Цезаря
1 ____
один из самых известных и самых древних
шифров. В этом шифре каждая буква заменяется на другую, расположенную в алфавите на заданное число позиций k вправо от неё. Алфавит замыкается в кольцо, так что последние символы заменяются на первые. На рисунке 10.2 — пример шифра Цезаря (со сдвигом 3)2.
Назван в честь римского императора Гая Юлия Цезаря, использовавшего его для секретной переписки.
Будем считать, что буквы «Е» и «Ё* совпадают.
1
Информационная безопасность
Знаменитая фраза «ПРИШЕЛ УВИДЕЛ ПОБЕДИЛ» при использовании шифра Цезаря со сдвигом 3 будет закодирована так:
ТУЛЫИО ЦЕЛЗИО ТСДИЗЛО
Если первая буква алфавита имеет код О, вторая — код 1 и т. д., алгоритм шифрования может быть выражен формулой
y = {x + k) mod п,
где X — код исходного символа, k — величина сдвига, у — код символа-замены, п — количество символов в алфавите, а запись (х + k) mod п обозначает остаток от деления х + k на п. Операция взятия остатка от деления необходима для того, чтобы замкнуть алфавит в кольцо. Например, при использовании русского алфавита (32 буквы, без буквы «Ё») для буквы «Я» (код 31) получаем код заменяющего символа (31 + 3) mod 32 = 2, это буква «В».
Ключом для шифра Цезаря служит сдвиг к, если его знать, то сообщение легко расшифровать. Для этого используется формула
х = {у -к + п) mod п.
Шифр Цезаря относится к шифрам простой подстановки, так как каждый символ исходного сообщения заменяется на другой символ из того же алфавита. Такие шифры легко раскрываются с помощью частотного анализа, потому что в каждом языке частоты встречаемости букв примерно постоянны для любого достаточно большого текста.
Значительно сложнее сломать шифр Виженера^, который стал естественным развитием шифра Цезаря. Для использования шифра Виженера используется ключевое слово, которое задает переменную величину сдвига. Например, пусть ключевое слово — «ЗАБЕГ». По таблице (рис. 10.3) определяем коды букв.
0 1 2 3 4 5 6 7 8 9
А Б В г Д Е Ж 3 И Й ...
Рис. 10.3
Получаем: «3» — 7, «А» — 0, «Б» — 1, «Е» — 5, «Г» — 3. Это значит, что для кодирования первой буквы любого текста используется сдвиг 7, для кодирования второй — 0 (символ не меняется) и т. д. Для пятой буквы используется сдвиг 3, а для шес-
Назван по имени Блеза Виженера, швейцарского дипломата XVI века.
Шифрование
§78
той — снова 7 (начинаем «проходить» кодовое слова с начала). Фраза «ПРИШЕЛ УВИДЕЛ ПОБЕДИЛ» при использовании шифра Виженера с ключом «ЗАБЕГ» будет закодирована в виде «ЦРЙЭИТ УГНЗМЛ РУДМДЙР».
Шифр Виженера обладает значительно более высокой криптостойкостью, чем шифр Цезаря. Это значит, что его труднее раскрыть — подобрать нужное ключевое слово. Теоретически, если длина ключа равна длине сообщения и каждый ключ используется только один раз, шифр Виженера обладает абсолютной криптостойкостью — взломать его невозможно.
Вопросы и задания
1. Чем различаются понятия «шифрование» и «кодирование»?
2. Что такое ключ?
3. Как называется наука, изучающая методы шифрования?
4. Что такое симметричный шифр? Какая проблема возникает при использовании симметричного шифра, если участники переписки находятся в разных странах?
5. Что такое несимметричные шифры? На чём основана их надёжность?
6. Что такое криптостойкость алгоритма? Какой алгоритм считается криптостойким?
Подготовьте сообщение
а) «Полиграммные шифры подстановки»
б) «Шифрование и закон»
в) «Криптостойкость шифров»
г) «Частотный анализ»
Задачи
1. Зашифруйте с помощью шифра Цезаря со сдвигом 6 высказывание «ЛЮДИ ОХОТНО ВЕРЯТ ТОМУ, ЧЕМУ ЖЕЛАЮТ ВЕРИТЬ».
2. Напишите программу, которая выполняет шифрование строки с помощью шифра Цезаря.
*3. Попытайтесь расшифровать сообщение, закодированное шифром Цезаря с неизвестным сдвигом: «ХШЖНПУТ ФКХКОЙКТ». Для этого можно написать программу.
4. Используя шифр Виженера с ключом «ЛЕНА», зашифруйте сообщение «НЕЛЬЗЯ ОБИЖАТЬ ГОСТЯ».
*5. Измените программу для шифрования с помощью шифра Цезаря так, чтобы учитывать букву Ё.
*6. Измените программу для шифрования с помощью шифра Цезаря так, чтобы учитывать и букву Ё, и пробел.
А
О
i
Информационная безопасность
§79
Хэширование и пароли
в современных информационных системах часто используется вход по паролю. Если при этом где-то хранить пароли всех пользователей, система становится очень ненадёжной, потому что «утечка» паролей позволит сразу получить доступ к данным. Вместе с тем кажется, что пароли обязательно где-то нужно хранить, иначе пользователи не смогут войти в систему. Однако это не совсем так. Можно хранить не пароли, а некоторые числа, полученные в результате обработки паролей. Простейший вариант — сумма кодов символов, входящих в пароль. Для пароля «А123» такая сумма равна
215 = 65 (код «А») + 49 (код «1») + 50 (код «2») 4- 51 (код «3»).
Фактически мы определили функцию Н(М), которая сообщение М любой длины превращает в короткий код т. Такую функцию называются хэш-функцией (от англ, hash — мешанина, крошить), а само полученное число — хэш-кодом, хэш-суммой или просто хэшем исходной строки. Важно, что, зная хэш-код, невозможно восстановить исходный пароль! В этом смысле хэширование — это необратимое шифрование.
Итак, вместо пароля «А123» мы храним число 215. Когда пользователь вводит пароль, мы считаем сумму кодов символов этого пароля и разрешаем вход в систему только тогда, когда она равна 215. И вот здесь возникает проблема: существует очень много паролей, для которых наша хэш-функция даёт значение 215, например «В023». Такая ситуация — совпадение хэш-кодов различных исходных строк — называется коллизией (англ. collision — столкновение). Коллизии будут всегда — ведь мы «сжимаем» длинную цепочку байтов до числа. Казалось бы, ничего хорошего не получилось: если взломщик узнает хэш-код, то, зная алгоритм его получения, он сможет легко подобрать пароль с таким же хэшем и получить доступ к данным. Однако это произошло потому, что мы выбрали плохую хэш-функцию.
Математики разработали надёжные (но очень сложные) хэш-функции, обладающие особыми свойствами:
1) хэш-код очень сильно меняется при малейшем изменении исходных данных;
Хэширование и пароли
§79
2) при известном хэш-коде т невозможно за приемлемое время найти сообщение М с таким хэш-кодом (Н(М) = т);
3) при известном сообщении М невозможно за приемлемое
время найти сообщение с таким же хэш-кодом
(ЩМ) = ЩМ^)).
Здесь выражение «невозможно за приемлемое время» (или «вычислительно невозможно») означает, что эта задача решается только перебором вариантов (других алгоритмов не существует), а количество вариантов настолько велико, что на решение могут уйти сотни и тысячи лет. Поэтому даже если взломщик получил хэш-код пароля, он не сможет за приемлемое время получить сам пароль (или пароль, дающий такой же хэш-код).
Чем длиннее пароль, тем больше количество вариантов. Кроме длины для надёжности пароля важен используемый набор символов. Например, очень легко подбираются пароли, состоящие только из цифр. Если же пароль состоит из 10 символов и содержит латинские буквы (заглавные и строчные) и цифры, перебор вариантов (англ, brute force — метод «грубой силы») со скоростью 10 млн паролей в секунду займет более 2000 лет.
Надёжные пароли должны состоять не менее чем из 7-8 символов; пароли, состоящие из 15 символов и более, взломать методом «грубой силы» практически невозможно. Не используйте пароли типа «12345», «qwerty», свой день рождения, номер телефона. Плохо, если пароль представляет собой известное слово, для этих случаев взломщики используют подбор по словарю. Сложнее всего подобрать пароль, который представляет собой случайный набор заглавных и строчных букв, цифр и других знаков^.
Сегодня для хэширования в большинстве случаев применяют алгоритмы MD5, SHA1 и российский алгоритм, изложенный в ГОСТ Р34.11-94 (он считается одним из самых надёжных). В криптографии хэш-коды чаще всего имеют длину 128, 160 и 256 битов.
Хэширование используется также для проверки правильности передачи данных: различные контрольные суммы — это не что иное, как хэш-коды.
Однако такой пароль сложно запомнить.
Информационная безопасность
О
8.
9.
*10.
Вопросы и задания
1. Что такое хэширование? Хэш-функция? Хэш-код?
2. Какую хэш-функцию вы используете, когда начинаете искать слово в словаре?
3. Что такое коллизии? Почему их должно быть как можно меньше?
4. Какие требования предъявляются к хэш-функциям, которые используются при хранении паролей?
5. Что значит «вычислительно невозможно*?
6. Взломщик узнал хэш-код пароля администратора сервера. Сможет ли он получить доступ к секретным данным на сервере?
7. Какие свойства пароля влияют на его надёжность?
Как выбрать надёжный пароль?
Какие алгоритмы хэширования сейчас чаще всего применяются? Предложите какой-нибудь свой метод хэширования. Подумайте, как часто при его использовании могут происходить коллизии.
Подготовьте сообщение
а) «Где используют хэши?*
б) «Хэширование и передача данных*
в) «Хэширование с "солью"»
Задачи
1. Напишите программу, которая запрашивает длину пароля, количество используемых символов и скорость перебора (например, в миллионах вариантов в секунду) и находит время, необходимое для подбора пароля методом «грубой силы».
2. Компьютер выполняет перебор со скоростью 10 млн паролей в секунду. С помощью программы (см. задачу 1) определите, какова должна быть длина пароля, чтобы время его взлома составило не менее 1 месяца, если:
а) пароль состоит только из цифр;
б) пароль состоит только из заглавных латинских букв и цифр;
в) пароль состоит только из латинских букв (заглавных и строчных) и цифр.
§80
Современные алгоритмы шифрования
Государственным стандартом шифрования в России является алгоритм, зарегистрированный как ГОСТ 28147-89. Он является блочным шифром, т. е. шифрует не отдельные символы, а 64-бит-
Современные алгоритмы шифрования
§80
ные блоки. В алгоритме предусмотрены 32 цикла преобразования данных с 256-битным ключом, за счёт этого он очень надёжен (обладает высокой криптостойкостью). На современных компьютерах раскрытие этого шифра путём перебора ключей («методом грубой силы») займёт не менее сотен лет, что делает такую атаку бессмысленной.
В США в качестве стандарта принят блочный шифр AES {англ. Advanced Encryption Standard, передовой стандарт шифрования), выбранный в 2001 г. по результатам проведённого конкурса. Шифр AES используется также в защищённых беспроводных сетях (WiFi).
В Интернете популярен алгоритм RSA, названный так по начальным буквам фамилий его авторов — Р. Райвеста (R. Rivest), А. Шамира (А. Shamir) и Л. Адлемана (L. Adleman). Это алгоритм с открытым ключом, стойкость алгоритма основана на том, что перемножить два очень больших простых числа достаточно просто, а вот разложить такое произведение на простые сомножители очень трудно (эту задачу сейчас умеют решать только перебором вариантов). Поскольку количество вариантов огромно, для раскрытия шифра требуется много лет работы современных компьютеров.
Для применения алгоритма RSA требуется построить открытый и секретный ключи следующим образом.
1. Выбрать два больших простых числа, р и д.
2. Найти их произведение п = р д и значение ф = (р -1) • (д -1).
3. Выбрать число е (1<е<ф), которое не имеет общих делителей с ф.
4. Найти число d, которое удовлетворяет условию d e = k(p + l для некоторого целого k.
5. Пара значений (е, л) — это открытый ключ RSA (его можно свободно публиковать), а пара (d, п) — это секретный ключ. Передаваемое сообщение нужно сначала представить в виде
последовательности чисел в интервале от 0 до л - 1. Для шифрования используют формулу
у = mod л,
где X — исходное сообщение (число), (е,л) — открытый ключ, у — закодированное сообщение (число), а запись х^ mod л обозначает остаток от деления х^ на л. Расшифровка сообщения выполняется по формуле
X = у’^ mod л.
Информационная безопасность
Это значит, что зашифровать сообщение может каждый (открытый ключ общеизвестен), а прочитать его — только тот, кто знает секретный показатель степени d.
Для лучшего понимания мы покажем работу алгоритма RSA на простом примере. Возьмём р = 3 и д = 7, тогда находим п = p q = 21 и ф = (р-1)(<7-1) = 12. Выберем е = Ъ, тогда равенство d e = ft 1® mod 21 = 1, 2 => 2® mod 21 = 11, 3 => 3® mod 21 = 12,
т. е. зашифрованное сообщение состоит из чисел 1, 11 и 12. Зная секретный ключ (17, 21), можно его расшифровать:
1=> 117 mod 21 = 1, iizi>iii7mod21 = 2, 12 => 12i7 mod 21 = 3.
Мы получили исходное сообщение.
Конечно, вы заметили, что при шифровании и расшифровке приходится вычислять остаток от деления очень больших чисел (например, 1217) ^ Оказывается, само число 1217 g этом случае
находить не нужно. Достаточно записать в обычную целочисленную переменную, например х, единицу, а потом 17 раз выполнить преобразование jc = 12 • х mod 21. После этого в переменной х будет значение 1217 j^od 21 = 3. Попробуйте доказать правильность этого алгоритма.
Чтобы взломать шифр, злоумышленнику надо узнать секретный показатель степени d. А для этого необходимо найти большие простые числа р и q, такие что n = p q. Если п велико, это очень сложная задача, её решение перебором вариантов на современном компьютере займёт сотни лет. В 2009 г. группа учёных из разных стран в результате многомесячных расчётов на сотнях компьютеров смогла расшифровать сообщение, зашифрованное алгоритмом RSA с 768-битным ключом. Поэтому сейчас надёжными считаются ключи с длиной 1024 бита и более. Если будет построен работающий квантовый компьютер, взлом алгоритма RSA будет возможен за очень небольшое время.
При использовании симметричных шифров всегда возникает проблема: как передать ключ, если канал связи ненадёжный? Ведь, получив ключ, противник сможет расшифровать все дальнейшие сообщения. Для алгоритма RSA этой проблемы нет, сто-
Современные алгоритмы шифрования
§80
ронам достаточно обменяться открытыми ключами, которые можно показывать всем желающим.
У алгоритма RSA есть ещё одно достоинство: его можно использовать для цифровой подписи сообщений. Она служит для доказательства авторства документов, защиты сообщений от подделки и умышленных изменений.
Цифровая подпись — это набор символов, который получен в результате шифрования сообщения с помощью личного секретного кода отправителя.
Отправитель может передать вместе с исходным сообщением такое же сообщение, зашифрованное с помощью своего секретного ключа (это и есть цифровая подпись). Получатель расшифровывает цифровую подпись с помощью открытого ключа. Если она совпала с незашифрованным сообщением, можно быть уверенным, что его отправил тот человек, который знает секретный код. Если сообщение было изменено при передаче, оно не совпадёт с расшифрованной цифровой подписью. Так как сообщение может быть очень длинным, для сокращения объёма передаваемых данных чаще всего шифруется не всё сообщение, а только его хэш-код.
Во многих современных программах есть возможность шифровать данные с паролем. Например, офисные пакеты OpenOffice.org и Microsoft Office позволяют шифровать все создаваемые документы (для их просмотра и/или изменения нужно ввести пароль). При создании архива (например, в архиваторах Qzip> ^WinRAR, Щ WinZip) также можно установить пароль, без которого извлечь файлы невозможно.
В простейших задачах для шифрования файлов можно использовать бесплатную программу Шифровальщик (www. familytree.ru/ru/cipher.htm), версии которой существуют для Linux и Windows. Программы TrueCrypt (www.truecrypt.org), BestCrypt (www.jetico.com) и FreeOTFE (freeotfe.org) создают логические диски-контейнеры, информация на которых шифруется. Свободно распространяемая программа |£ DiskCryptor (diskcryptor.net) позволяет шифровать разделы жёстких дисков и даже создавать шифрованные флэш-диски и диски CD/DVD.
Программа ^ GnuPG (gnupg.org) также относится к свободному программному обеспечению. В ней поддерживаются симметричные и несимметричные шифры, а также различные алгоритмы электронной цифровой подписи.
О
Информационная безопасность
О
Вопросы и задания
1. Какой алгоритм шифрования принят в России в качестве государственного стандарта?
2. Что такое блочный алгоритм шифрования?
3. К какому типу относится алгоритм RSA? На чем основана его криптостойкость?
4. Что такое цифровая подпись?
5. Как можно использовать алгоритм RSA для цифровой подписи? Подготовьте сообщение
а) «Стандарты шифрования разных стран»
б) «Шифрование с открытым ключом: за и против*
в) «Алгоритм Эль-Гамаля»
г) «Цифровая подпись в Российской Федерации»
Задачи
*1. Напишите программу, которая строит открытый и секретный ключи RSA для небольших множителей р и q.
*2. Напишите программу, которая шифрует и расшифровывает сообщения с помощью алгоритма при небольших значениях открытого и секретного ключей.
§81
Стеганография
При передаче сообщений можно не только применять шифрование, но и скрывать сам факт передачи сообщения.
О
Стеганография — это наука о скрытой передаче информации путём скрытия самого факта передачи информации.
Древнегреческий историк Геродот описывал, например, такой метод: на бритую голову раба записывалось сообщение, а когда его волосы отрастали, он отправлялся к получателю, который брил его голову и читал сообщение.
Классический метод стеганографии — симпатические (невидимые) чернила, которые проявляются только при определенных условиях (нагрев, освещение, химический проявитель). Например, текст, написанный молоком, можно прочитать при нагреве.
Стеганография
§81
Сейчас стеганография занимается скрытием информации в текстовых, графических, звуковых и видеофайлах с помощью программного «внедрения» в них нужных сообщений.
Простейшие способ — заменять младшие биты файла, в котором закодировано изображение. Причём это нужно сделать так, чтобы разница между исходным и полученным рисунками была неощутима для человека. Например, в чёрно-белом рисунке (256 оттенков серого) яркость каждого пикселя кодируется 8 битами. Если поменять 1-2 младших бита этого кода, «встроив» туда текстовое сообщение, фотография, в которой нет чётких границ, почти не изменится. При замене одного бита каждый байт исходного текстового сообщения хранится в младших битах кодов 8 пикселей. Например, пусть первые 8 пикселей рисунка имеют такие коды:
10101101 10010100 00101010 01010010 10101010 10101010 10101011 10101111
Чтобы закодировать в них код буквы изменить младшие биты кодов: «и» (llOOlOOOg), нужно
10101101 10010101 0010101001010010 10101014 10101010 10101010 loioiiiO
1 1 0 0 1 0 0 0
Получателю нужно взять эти младшие биты и «собрать» их вместе в один байт.
Для звуков используются другие методы стеганографии, основанные на добавлении в запись коротких условных сигналов, которые обозначают 1 и О и не воспринимаются человеком на слух. Возможна также замена одного фрагмента звука на другой.
Для подтверждения авторства и охраны авторских прав на изображения, видео и звуковые файлы применяют цифровые водяные знаки — внедрённую в файл информацию об авторе. Они получили своё название от старых водяных знаков на деньгах и документах. Для того чтобы установить авторство фотографии, достаточно расшифровать скрытую информацию, записанную с помощью водяного знака.
Иногда цифровые водяные знаки делают видимыми (текст или логотип компании на фотографии или на каждом кадре видеофильма). На многих сайтах, занимающихся продажей цифровых фотографий, видимые водяные знаки размещены на фотографиях, предназначенных для предварительного просмотра.
Информационная безопасность
Вопросы и задания
1. Что такое стеганография?
2. Какие методы стеганографии существовали до изобретения компьютеров?
3. Как можно добавить текст в закодированное изображение?
4. На чем основаны методы стеганографии для звуковых данных и видеоданных?
5. Что такое цифровые водяные знаки? Зачем они используются?
Подготовьте сообщение
«Водяные знаки в цифровую эпоху»
§82
Безопасность в Интернете
Угрозы безопасности
Если компьютер подключён к Интернету, появляются дополнительные угрозы безопасности. Атаку через сеть могут проводить злоумышленники и боты (программы-роботы), находящиеся в других городах и странах. Можно выделить три основные цели злоумышленников:
• использование вашего компьютера для взлома других компьютеров, атак на сайты, рассылки спама, подбора паролей и т. п.;
• кража секретной информации — данных о банковских картах, имён и паролей для входа на почтовые серверы, в социальные сети, платёжные системы;
• мошенничество — хищение чужого имущества путём обмана.
Первые две угрозы связаны, главным образом, с вредоносными программами: вирусами, червями и «троянцами», которые позволяют злоумышленнику управлять компьютером через сеть и получать с него данные.
Мошенничество процветает потому, что многие пользователи Интернета очень доверчивы и неосторожны. Классический пример мошенничества — так называемые нигерийские письма, приходящие по электронной почте. Пользователя от имени какого-то бывшего высокопоставленного лица просят принять участие в переводе крупных денежных сумм за границу, обещая выплачивать большие проценты. Если получатель соглашается, мошенники постепенно выманивают у него деньги.
Безопасность в Интернете
§82
Фишинг (англ, phishing, искажение слова fishing — рыбная ловля) — это выманивание паролей. Для этого чаще всего используются сообщения электронной почты, рассылаемые якобы от имени администраторов банков, платёжных систем, почтовых служб, социальных сетей. В сообщении говорится, что ваш счёт (или учётная запись) заблокирован, и даётся ссылка на сайт, который внешне выглядит как настоящий, но расположен по другому адресу (это можно проверить в адресной строке браузера). Неосторожный пользователь вводит своё кодовое имя и пароль, с помощью которых мошенник получает доступ к данным или банковскому счёту.
Антивирусы и последние версии браузеров содержат специальные модули для обнаружения подозрительных сайтов {«анти-фишинг») и предупреждают о заходе на такой сайт. Кроме того, нужно помнить, что администраторы сервисов никогда не просят пользователя сообщить свой пароль по электронной почте.
Мошенничество может быть связано и с вредоносными программами. В 2010 г. несколько миллионов компьютеров в России было заражено троянской программой Winlock, которая блокировала компьютер и требовала отправить платное SMS-сообщение для снятия блокировки.
Правила личной безопасности
Вредоносные программы, распространяющиеся через Интернет, представляют серьёзную угрозу безопасности данных. Нужно помнить, что многих проблем можно избежать, если работать в Интернете только из-под ограниченной учётной записи (без прав администратора). Кроме того, желательно своевременно обновлять программное обеспечение; особенно важно устанавливать «заплатки», связанные с безопасностью.
Чтобы ваши пароли не украли, лучше не запоминать их в браузере (иногда они хранятся в открытом виде и могут быть украдены троянской программой). Заходя под своим именем в закрытую зону сайта с другого компьютера, нужно отмечать флажок Чужой компьютер, иначе тот, кто после вас откроет эту страницу на вашем компьютере, сможет получить доступ к вашим данным.
На многих сайтах предусмотрена возможность восстановления пароля по секретному вопросу. Этот вопрос нужно выбирать так, чтобы никто другой не знал ответа на него и, самое важное, не мог его выведать. Например, ответы на вопросы «Как звали вашу первую собаку?», «Какое ваше любимое блюдо?» и т. п. часто можно найти на персональных страничках авторов в социальных
Информационная безопасность
сетях (в заметках, подписях к фотографиям и т. п.)- Если мама автора имеет свою страничку, на ней, скорее всего, можно найти её девичью фамилию, поэтому вопрос «Какова девичья фамилия вашей матери?» тоже лучше не использовать.
Нужно понимать, что, размещая какую-то информацию в Интернете, вы делаете её доступной для широкого круга лиц, включая работодателей, милицию, официальные органы и даже преступников. Возможны ситуации, когда эта информация (личные данные, фотографии, высказывания на форумах и в блогах) может быть использована против вас, даже если она находится в закрытом разделе сайта.
Для передачи информации, которую необходимо сохранить в тайне, лучше применять шифрование (например, упаковать данные в архив с паролем).
Наибольший уровень безопасности обеспечивается при денежных расчётах через Интернет: вместо протокола HTTP используют защищенный протокол HTTPS (англ. Hypertext Transfer Protocol Secure — безопасный HTTP), который предусматривает шифрование данных (например, с помощью алгоритма RSA). Поэтому нужно проверять, чтобы адрес на странице ввода пароля в таких системах начинался с https://, а не с https://.
Современные молодые люди часто общаются в чатах, форумах и т. п., в том числе с теми, кого они не знают лично. Продолжение такого виртуального (компьютерного, электронного) знакомства в реальной жизни весьма опасно, потому что нередко участники чатов и форумов представляются не теми, кем они являются на самом деле.
Вопросы и задания
1. Какие угрозы безопасности существуют при подключении к Интернету?
2. Какие схемы интернет-мошенничества вам известны?
3. Какие меры безопасности нужно соблюдать при работе в
Интернете?
4. Как обеспечивается безопасность обмена данными при денежных
расчётах в Интернете?
Подготовьте сообщение
а) «Нигерийские письма»
б) «Фишинг»
в) «Безопасность финансовых расчётов в Интернете»
Безопасность в Интернете
§82
Практические работы к главе 10
Работа № 73 Работа № 74 Работа № 75
Работа № 76
«Использование антивирусных программ» «Простые алгоритмы пхифрования данных» «Современные алгоритмы шифрования и хэширования»
«Использование стеганографии»
ЭОР к главе 10 на сайте ФЦИОР (http//fcior.edu.ru)
• Организация защиты при работе в сети
• Компьютерные вирусы и антивирусные программы Методы и средства защиты программных продуктов
• Сетевые и интернет-технологии. Компьютерная безопасность
• Информационная безопасность
Самое важное в главе 10
• Информационная безопасность — это защищённость информации от любых действий, в результате которых может быть искажена или утеряна информация либо нарушена её конфиденциальность, а владельцам или пользователям информации нанесён недопустимый ущерб.
• Основные угрозы информационной безопасности — выход оборудования из строя, неправомерный доступ к информации, вредоносные программы.
• Слабое звено любой системы информационной защиты — это человек.
• Шифрование — это преобразование открытой информации в зашифрованную, недоступную для понимания посторонних.
• Существуют системы шифрования с открытым ключом, при использовании которых все данные могут передаваться по незащищённому каналу связи.
• Цифровая подпись — это набор символов, который получен в результате шифрования сообщения с помощью личного секретного кода отправителя.
Навигационные значки
Уважаемые ученики] В работе с книгой вам помогут навигационные значки:
О
о
о
— важное утверждение или определение.
— вопросы и задания к параграфу.
— дополнительное разъяснение.
— задания для подготовки к итоговой аттестации.
— к каждой главе учебника рекомендуются:
1) электронные образовательные ресурсы (ЭОР) с сайта Федерального центра образовательных ресурсов (ФЦИОР):
https://fcior.edu.ru
Доступ к ЭОР из каталога ФЦИОР:
https://fcior.edu.ru/catalog/meta/4/mc/discipline%
2000/mi/4.06/p/page.html.
Ресурсы размещены в алфавитном порядке, согласно названиям учебных тем;
2) практические работы на методическом сайте издательства lbz.metodist.ru в авторской мастерской К. Ю. Полякова и Е. А. Еремина.
— Проектное или исследовательское задание.
В ходе выполнения проекта (исследования) вы можете:
• подготовить набор полезных ссылок с использованием веб-ресурсов;
• подготовить небольшое выступление с использованием презентации (5-7 мин.);
• оформить доклад и поместить его на сайт школьной конференции;
• подтвердить полученные результаты расчётами и графиками (диаграммами);
• подготовить видеоролик;
• разместить материалы проекта (исследования) в коллекции обучающих модулей по предмету на сайте школы.
Для заметок
Для заметок
'%! Г i J.W»
rgii’i-i'i
i -
. * 1
W^'l>
' .r‘t .
<^y ^ . ..- .
I V.