Примеры заданий по информатике. Виды алгоритмов в информатике: примеры. Обозначения в блок-схеме

Основы решения линейных неоднородных дифференциальных уравнений второго порядка (ЛНДУ-2) с постоянными коэффициентами (ПК)

ЛНДУ 2-го порядка с постоянными коэффициентами $p$ и $q$ имеет вид $y""+p\cdot y"+q\cdot y=f\left(x\right)$, где $f\left(x\right)$ - непрерывная функция.

В отношении ЛНДУ 2-го с ПК справедливы два следующих утверждения.

Предположим, что некоторая функция $U$ является произвольным частным решением неоднородного дифференциального уравнения. Предположим также, что некоторая функция $Y$ является общим решением (ОР) соответствующего линейного однородного дифференциального уравнения (ЛОДУ) $y""+p\cdot y"+q\cdot y=0$. Тогда ОР ЛНДУ-2 равно сумме указанных частного и общего решений, то есть $y=U+Y$.

Если правая часть ЛНДУ 2-го порядка представляет собой сумму функций, то есть $f\left(x\right)=f_{1} \left(x\right)+f_{2} \left(x\right)+...+f_{r} \left(x\right)$, то сначала можно найти ЧР $U_{1} ,U_{2} ,...,U_{r} $, которые соответствуют каждой из функций $f_{1} \left(x\right),f_{2} \left(x\right),...,f_{r} \left(x\right)$, а уже после этого записать ЧР ЛНДУ-2 в виде $U=U_{1} +U_{2} +...+U_{r} $.

Решение ЛНДУ 2-го порядка с ПК

Очевидно, что вид того или иного ЧР $U$ данного ЛНДУ-2 зависит от конкретного вида его правой части $f\left(x\right)$. Простейшие случаи поиска ЧР ЛНДУ-2 сформулированы в виде четырех следующих правил.

Правило № 1.

Правая часть ЛНДУ-2 имеет вид $f\left(x\right)=P_{n} \left(x\right)$, где $P_{n} \left(x\right)=a_{0} \cdot x^{n} +a_{1} \cdot x^{n-1} +...+a_{n-1} \cdot x+a_{n} $, то есть называется многочленом степени $n$. Тогда его ЧР $U$ ищут в виде $U=Q_{n} \left(x\right)\cdot x^{r} $, где $Q_{n} \left(x\right)$ - другой многочлен той же степени, что и $P_{n} \left(x\right)$, а $r$ - количество корней характеристического уравнения соответствующего ЛОДУ-2, равных нулю. Коэффициенты многочлена $Q_{n} \left(x\right)$ находят методом неопределенных коэффициентов (НК).

Правило № 2.

Правая часть ЛНДУ-2 имеет вид $f\left(x\right)=e^{\alpha \cdot x} \cdot P_{n} \left(x\right)$, где $P_{n} \left(x\right)$ представляет собой многочлен степени $n$. Тогда его ЧР $U$ ищут в виде $U=Q_{n} \left(x\right)\cdot x^{r} \cdot e^{\alpha \cdot x} $, где $Q_{n} \left(x\right)$ - другой многочлен той же степени, что и $P_{n} \left(x\right)$, а $r$ - количество корней характеристического уравнения соответствующего ЛОДУ-2, равных $\alpha $. Коэффициенты многочлена $Q_{n} \left(x\right)$ находят методом НК.

Правило № 3.

Правая часть ЛНДУ-2 имеет вид $f\left(x\right)=a\cdot \cos \left(\beta \cdot x\right)+b\cdot \sin \left(\beta \cdot x\right)$, где $a$, $b$ и $\beta $ - известные числа. Тогда его ЧР $U$ ищут в виде $U=\left(A\cdot \cos \left(\beta \cdot x\right)+B\cdot \sin \left(\beta \cdot x\right)\right)\cdot x^{r} $, где $A$ и $B$ - неизвестные коэффициенты, а $r$ - количество корней характеристического уравнения соответствующего ЛОДУ-2, равных $i\cdot \beta $. Коэффициенты $A$ и $B$ находят методом НК.

Правило № 4.

Правая часть ЛНДУ-2 имеет вид $f\left(x\right)=e^{\alpha \cdot x} \cdot \left$, где $P_{n} \left(x\right)$ - многочлен степени $n$, а $P_{m} \left(x\right)$ - многочлен степени $m$. Тогда его ЧР $U$ ищут в виде $U=e^{\alpha \cdot x} \cdot \left\cdot x^{r} $, где $Q_{s} \left(x\right)$ и $R_{s} \left(x\right)$ - многочлены степени $s$, число $s$ - максимальное из двух чисел $n$ и $m$, а $r$ - количество корней характеристического уравнения соответствующего ЛОДУ-2, равных $\alpha +i\cdot \beta $. Коэффициенты многочленов $Q_{s} \left(x\right)$ и $R_{s} \left(x\right)$ находят методом НК.

Метод НК состоит в применении следующего правила. Для того чтобы найти неизвестные коэффициенты многочлена, которые входят в состав частного решения неоднородного дифференциального уравнения ЛНДУ-2, необходимо:

• подставить ЧР $U$, записанное в общем виде, в левую часть ЛНДУ-2;
• в левой части ЛНДУ-2 выполнить упрощения и сгруппировать члены с одинаковыми степенями $x$;
• в полученном тождестве приравнять коэффициенты при членах с одинаковыми степенями $x$ левой и правой частей;
• решить полученную систему линейных уравнений относительно неизвестных коэффициентов.

Пример 1

Задача: найти ОР ЛНДУ-2 $y""-3\cdot y"-18\cdot y=\left(36\cdot x+12\right)\cdot e^{3\cdot x} $. Найти также ЧР, удовлетворяющее начальным условиям $y=6$ при $x=0$ и $y"=1$ при $x=0$.

Записываем соответствующее ЛОДУ-2: $y""-3\cdot y"-18\cdot y=0$.

Характеристическое уравнение: $k^{2} -3\cdot k-18=0$. Корни характеристического уравнения: $k_{1} =-3$, $k_{2} =6$. Эти корни действительны и различны. Таким образом, ОР соответствующего ЛОДУ-2 имеет вид: $Y=C_{1} \cdot e^{-3\cdot x} +C_{2} \cdot e^{6\cdot x} $.

Правая часть данного ЛНДУ-2 имеет вид $\left(36\cdot x+12\right)\cdot e^{3\cdot x} $. В ней необходимо рассматривать коэффициент показателя степени экспоненты $\alpha =3$. Этот коэффициент не совпадает ни с одним из корней характеристического уравнения. Поэтому ЧР данного ЛНДУ-2 имеет вид $U=\left(A\cdot x+B\right)\cdot e^{3\cdot x} $.

Будем искать коэффициенты $A$, $B$ методом НК.

Находим первую производную ЧР:

$U"=\left(A\cdot x+B\right)^{{"} } \cdot e^{3\cdot x} +\left(A\cdot x+B\right)\cdot \left(e^{3\cdot x} \right)^{{"} } =$

$=A\cdot e^{3\cdot x} +\left(A\cdot x+B\right)\cdot 3\cdot e^{3\cdot x} =\left(A+3\cdot A\cdot x+3\cdot B\right)\cdot e^{3\cdot x} .$

Находим вторую производную ЧР:

$U""=\left(A+3\cdot A\cdot x+3\cdot B\right)^{{"} } \cdot e^{3\cdot x} +\left(A+3\cdot A\cdot x+3\cdot B\right)\cdot \left(e^{3\cdot x} \right)^{{"} } =$

$=3\cdot A\cdot e^{3\cdot x} +\left(A+3\cdot A\cdot x+3\cdot B\right)\cdot 3\cdot e^{3\cdot x} =\left(6\cdot A+9\cdot A\cdot x+9\cdot B\right)\cdot e^{3\cdot x} .$

Подставляем функции $U""$, $U"$ и $U$ вместо $y""$, $y"$ и $y$ в данное ЛНДУ-2 $y""-3\cdot y"-18\cdot y=\left(36\cdot x+12\right)\cdot e^{3\cdot x}. $ При этом, поскольку экспонента $e^{3\cdot x} $ входит как множитель во все составляющие, то её можно опустить. Получаем:

$6\cdot A+9\cdot A\cdot x+9\cdot B-3\cdot \left(A+3\cdot A\cdot x+3\cdot B\right)-18\cdot \left(A\cdot x+B\right)=36\cdot x+12.$

Выполняем действия в левой части полученного равенства:

$-18\cdot A\cdot x+3\cdot A-18\cdot B=36\cdot x+12.$

Применяем метод НК. Получаем систему линейных уравнений с двумя неизвестными:

$-18\cdot A=36;$

$3\cdot A-18\cdot B=12.$

Решение этой системы таково: $A=-2$, $B=-1$.

ЧР $U=\left(A\cdot x+B\right)\cdot e^{3\cdot x} $ для нашей задачи выглядит следующим образом: $U=\left(-2\cdot x-1\right)\cdot e^{3\cdot x} $.

ОР $y=Y+U$ для нашей задачи выглядит следующим образом: $y=C_{1} \cdot e^{-3\cdot x} +C_{2} \cdot e^{6\cdot x} +\left(-2\cdot x-1\right)\cdot e^{3\cdot x} $.

С целью поиска ЧР, удовлетворяющего заданным начальным условиям, находим производную $y"$ ОР:

$y"=-3\cdot C_{1} \cdot e^{-3\cdot x} +6\cdot C_{2} \cdot e^{6\cdot x} -2\cdot e^{3\cdot x} +\left(-2\cdot x-1\right)\cdot 3\cdot e^{3\cdot x} .$

Подставляем в $y$ и $y"$ начальные условия $y=6$ при $x=0$ и $y"=1$ при $x=0$:

$6=C_{1} +C_{2} -1; $

$1=-3\cdot C_{1} +6\cdot C_{2} -2-3=-3\cdot C_{1} +6\cdot C_{2} -5.$

Получили систему уравнений:

$C_{1} +C_{2} =7;$

$-3\cdot C_{1} +6\cdot C_{2} =6.$

Решаем её. Находим $C_{1} $ по формуле Крамера, а $C_{2} $ определяем из первого уравнения:

$C_{1} =\frac{\left|\begin{array}{cc} {7} & {1} \\ {6} & {6} \end{array}\right|}{\left|\begin{array}{cc} {1} & {1} \\ {-3} & {6} \end{array}\right|} =\frac{7\cdot 6-6\cdot 1}{1\cdot 6-\left(-3\right)\cdot 1} =\frac{36}{9} =4; C_{2} =7-C_{1} =7-4=3.$

Таким образом, ЧР данного дифференциального уравнения имеет вид: $y=4\cdot e^{-3\cdot x} +3\cdot e^{6\cdot x} +\left(-2\cdot x-1\right)\cdot e^{3\cdot x} $.

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

Понятие

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

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

Свойства

Прежде чем рассматривать в информатике, необходимо выяснить их основные свойства.

Среди основных свойств алгоритмов необходимо выделить следующие:

• Детерминированность, то есть определенность. Заключается в том, что любой алгоритм предполагает получение определенного результата при заданных исходных.
• Результативность. Означает, что при наличии ряда исходных данных после выполнения ряда шагов будет достигнут определенный, ожидаемый результат.
• Массовость. Написанный единожды алгоритм может использоваться для решения всех задач заданного типа.
• Дискретность. Она подразумевает, что любой алгоритм можно разбить на несколько этапов, каждый из которых имеет свое назначение.

Способы записи

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

1. Словестный.
2. Формульно-словестный.
3. Графический.
4. Язык алгоритма.

Наиболее часто изображают алгоритм в виде блок-схемы, используя специальные обозначения, зафиксированные ГОСТами.

Основные виды

Выделяют три основных схемы:

1. Линейный алгоритм.
2. Ветвящийся алгоритм, или разветвленный.
3. Циклический.

Линейный

Наиболее простым в информатике считается Он предполагает последовательность выполнения действий. Приведем наиболее простой пример алгоритма такого вида. Назовем его «Сбор в школу».

1. Встаем, когда звенит будильник.

2. Умываемся.

3. Чистим зубы.

4. Делаем зарядку.

5. Одеваемся.

6. Кушаем.

7. Обуваемся и идем в школу.

8. Конец алгоритма.

Разветвляющийся алгоритм

Рассматривая виды алгоритмов в информатике, нельзя не вспомнить о разветвляющейся структуре. Данный вид предполагает наличие условия, при котором в случае его выполнения действия выполняются в одном порядке, а в случае невыполнения - в другом.

Например, возьмем следующую ситуацию - переход дороги пешеходом.

1. Подходим к светофору.

2. Смотрим на сигнал светофора.

3. Он должен быть зеленым (это условие).

4. Если условие выполняется, мы переходим дорогу.

4.1 Если нет - ждем, пока загорится зеленый.

4.2 Переходим дорогу.

5. Конец алгоритма.

Циклический алгоритм

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

Возьмем простой пример. Если ряд чисел от 1 до 100. Нам необходимо найти все то есть те, которые делятся на единицу и себя. Назовем алгоритм «Простые числа».

1. Берем число 1.

2. Проверяем, меньше ли оно 100.

3. Если да, проверяем простое ли это число.

4. Если условие выполняется, записываем его.

5. Берем число 2.

6. Проверяем, меньше ли оно 100.

7. Проверяем, простое ли оно.

…. Берем число 8.

Проверяем, меньше ли оно 100.

Проверяем, простое ли число.

Нет, пропускаем его.

Берем число 9.

Таким образом перебираем все числа, до 100.

Как видите, шаги 1 - 4 будут повторяться некоторое число раз.

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

Другие варианты

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

Обозначения в блок-схеме

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

1. Начало и конец алгоритма записываются в овальной рамке.
2. Каждая команда фиксируется в прямоугольнике.
3. Условие прописывается в ромбе.
4. Все части алгоритма соединяются при помощи стрелок.

Выводы

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

Свойства информации

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

Объективность информации - Информация – это отображение окружающего мира, а он существует независимо от нашего сознания, знаний и мыслей о нем.

ПРИМЕРЫ:

1) Фома неверующий

2) Игра «Глухой телефон»

Информация достоверна , если она отражает истинное положение дел. Недостоверная информация может привести к неправильному пониманию или принятию неправильных решений.

ПРИМЕРЫ:

1) Пропущено занятие, подруга говорит, что ничего не задано.

2) Скачали информацию в Интернете

Информация полна , если ее достаточно для понимания и принятия решений. Неполнота информации сдерживает принятие решений или может повлечь ошибки.

ПРИМЕРЫ:

1) Пропущено занятие, подруга говорит, что задан только параграф и забывает про задачи.

2) На улице 20 0 С (не понятно + или -)

Актуальность (своевременность) – важность, необходимость для данного времени. Актуальную информацию важно иметь при работе в изменившихся условиях.

ПРИМЕРЫ:

1) Предупреждение накануне о контрольной работе

2) Прогноз погоды на завтра актуальнее прогноза на вчера

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

ПРИМЕРЫ:

1) В расписании уроков указаны занятия для всех классов, для вас ценна информация лишь о ваших уроках

2) Просмотрен документальный фильм про Петра 1. На уроке информатике он ценности не имеет, но на уроке истории - имеет.

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

ПРИМЕРЫ:

1) Дошкольник спрашивает у старшеклассника: "Как светит лампочка?". В ответ слышит: "Существует две теории света – волновая и корпускулярная. Согласно первой …".

2) Объяснять материал на китайском языке.

В следующих примерах определите свойства встречающейся информации:

q На следующий день учительница вывесила правильные решения всех задач…

q Идет контрольная работа по математике. Вы попросили у соседа решение задачи. Шпаргалка содержала полное и правильное решение, но... на японском языке.

q Один персидский царь, собираясь завоевать соседнее государство, обратился к оракулу с вопросом: “Что произойдет, если я со своим войском переправлюсь через пограничную реку?” Оракул ответил: “Государь, ты разрушишь великое царство”. Удовлетворившись таким предсказанием, завоеватель переправился со своим войском через реку и был разгромлен войском противной стороны. В гневе он обратился к оракулу, обвиняя того в обмане. На что оракул ответил: “Государь, а разве твое царство было не велико?”

Приведите примеры:

ь достоверной, но неактуальной информации;

ь актуальной, но недостоверной информации;

ь полной, достоверной, но бесполезной информации;

ь актуальной, но непонятной информации.

Задание 1.

Алфавит племени содержит всего 8 букв. Какое количество информации несет одна буква этого алфавита?

Решение.

Известен информационный объем теста и информационный «вес» одного символа в нем. Найдем объем одной страницы: 40648 бит. 20 Кбайт = 201024 байт = 2010248 бит. Найдем количество страниц: 2010248/(40648) = 8 (стр.) (Ответ № 4)

Ответ : 4.

Задание 3.

В пяти килобайтах:

Решение.

32Гб = 25 Гб = 25210 Мб = 25210 210 Кб =25210 210210 байт = 235 байт, что соответствует ответу №1.

Ответ : 1.

Задание 5.

Считая, что один символ кодируется одним байтом, подсчитать в байтах количество информации, содержащееся в фразе: “Терпение и труд все перетрут.”

Решение.

В фразе 29 символов (включая точку и пробелы), 1 символ несет 1 байт информации, значит фраза содержит 29 байт.

Ответ : 29.

Задание 6. ( А4 демоверсии 2004 г.)

Получено сообщение, информационный объём которого равен 32 битам. Чему равен этот объём в байтах?

Решение.

Предложенная строка содержит ровно 108 символов, включая кавычки, пробелы и знаки препинания. При кодировании каждого символа одним байтом на символ будет приходиться по 8 бит, поэтому объём этого предложения составит 108 байт или 108х8=864 бит, что соответствует ответу №2.

Ответ : 2.

Задание 8. (Задание А3 демоверсии 2004 г.)

Шахматная доска состоит из 64 полей: 8 столбцов и 8 строк. Какое минимальное количество бит потребуется для кодирования координат одного шахматного поля?

Решение.

Для того, чтобы различить 64 клетки шахматного поля потребуются 64 значения двоичного кода. Поскольку 64=26, то в двоичном коде потребуется шесть разрядов. Верный ответ№3.

Ответ : 3.

Задание 9.

Каждое показание счётчика, фиксируемое в памяти компьютера, занимает 10 бит. Записано 100 показаний этого датчика. Каков информационный объём снятых значений в байтах?

Решение.

10 бит100= 1000 бит, 1 байт = 8 бит, следовательно: 1000/8=125 байт. Значит, верный ответ №3.

Ответ : 3.

Задание 10.

В коробке 32 карандаша, все карандаши разного цвета. Наугад вытащили красный. Какое количество информации при этом было получено?

Решение.

Так как вытаскивание карандаша любого цвета из имеющихся в коробке 32 карандашей является равновероятным, то число возможных событий

N = 2I, 32 = 25, I = 5 бит.