Тема 15 : Этапы решения задач на компьютере (углубленный)

 

Тема 15 : Этапы решения задач на компьютере

https://profspo.ru/old-viewer?publicationType=books&publicationId=132236

Глава 8 §51 стр 126-131

https://profspo.ru/reader/book/132235 Глава 4  §27,28 стр 211-223

 

В решении любой задачи с помощью компьютера можно выделить несколько этапов. 

1. Постановка задачи. Нужно чётко определить, что в задаче дано (исходные данные) и что нужно найти (результаты).

2. Формализация. На этом этапе строится модель, которая включает только существенные данные, влияющие на решение задачи. Например, при моделировании полёта брошенного в воду камня нужно решить, учитываем ли мы притяжение Земли, сопротивление воздуха и влияние Луны. Затем модель записывается с помощью формального языка, например в виде математических формул или уравнений, связывающих исходные данные и результаты.

Далее мы можем использовать готовое программное обеспечение или составить свою собственную программу. Рассмотрим второй вариант.

3. Построение алгоритма, с помощью которого на основе модели по исходным данным вычисляется результат.

 4. Составление программы на языке программирования.

 5. Тестирование и отладка программы. Цель тестирования — найти как можно больше ошибок в программе. Для этого используют тесты — специально подобранные наборы исходных данных, для которых известен правильный результат.

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

6. Выполнение расчётов. В отличие от тестирования на этом этапе мы выполняем расчёты для тех исходных данных, для которых результаты неизвестны. 

7. Анализ результатов. После завершения расчётов нужно проверить, не противоречат ли результаты теории и здравому смыслу. Например, время движения автомобиля не может быть отрицательным. Если такие противоречия обнаружены, нужно искать ошибку в модели, алгоритме или программе. Ключевой этап в этой последовательности — построение алгоритма.

Алгоритм — это точное описание последовательности действий некоторого исполнителя.

Основные свойства алгоритма:

• дискретность — алгоритм состоит из отдельных команд, каждая из которых выполняется ограниченное (не бесконечное) время;

• понятность — алгоритм содержит только команды, входящие в систему команд исполнителя, для которого он пред-назначен;

• определённость — при каждом выполнении алгоритма с од-ними и теми же исходными данными должен быть получен один и тот же результат.

 

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

 

 

Анализ алгоритмов

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

Часто мы не создаём алгоритмы сами, а используем готовые. В таких случаях полезно выполнять анализ алгоритмов, например, выяснив:

• какие исходные данные нужно подать на вход алгоритма, чтобы получить нужный результат;

• какие результаты могут быть получены при заданных исходных данных.

Рассмотрим несколько примеров.

Задача1. По каналу связи передаются трёхзначные целые числа. Для каждой пары таких чисел строится контрольная сумма, позволяющая обнаруживать ошибки при передаче:

а)записывается сумма старших разрядов передаваемых чисел; к ней справа дописывается сумма средних разрядов, а за-тем слева — сумма младших разрядов тех же чисел;

б)контрольная сумма — это три цифры полученного числа: число тысяч, число сотен и число десятков. Пример: передаются числа 768 и 156. Поразрядные суммы — 8,11,14. После шага

а) получаем число N = 14811, контрольная сумма — 481.Найдите минимальное и максимальное значения, которые может принимать контрольная сумма.

Решение. Поскольку числа трёхзначные, все они находятся на отрезке [100; 999]. Очевидно, что сумма значений двух любых десятичных цифр не меньше 0 и не больше 18. Минимальное число (N), которое может быть получено после шага а), равно 20 (при обработке чисел 100 и 100), а максимальное — 181818 (для чисел 999 и 999). Отсюда сразу следует, что минимальное значение контрольной суммы — 2

Определим максимальное значение контрольной суммы. Допустим, что контрольная сумма равна 999. Это значит, что число N имеет вид «..999.», где точка обозначает десятичную цифру, возможно — 0. Сумма значений двух цифр не может быть больше 18, поэтому есть только один вариант разбиения такого числа на поразрядные суммы: 9|9|9x, где x — какая-то цифра. Но этот вариант невозможен — сумма средних разрядов не может быть больше 18, поэтому максимальное значение контрольной суммы— 991. Такая контрольная сумма получается, например, для чисел 259 и 760

Задача2. Для условия задачи 1 приведите примеры данных, при которых контрольная сумма равна 106.

Решение. Если контрольная сумма равна 106, то число N может быть записано в виде «..106.». Возникает вопрос — как разбить это число на 3 поразрядные суммы? Поскольку вторая справа цифра — 6, а двузначная сумма значений двух цифр не может начинаться с 6, есть только один вариант: 10|6|x, где x — неизвестная однозначная сумма средних разрядов чисел. Поэтому нужно найти два трёхзначных числа, у которых сумма старших разрядов равна 6, сумма младших разрядов равна 10, а сумма средних разрядов меньше 10. Это могут быть, например, пары 209 и 491 или 138 и 522

Мы увидели, что для нашей контрольной суммы может возникнуть коллизия — ситуация, когда при разных данных контрольная сумма одинакова. Коллизии возникают практически всегда, ведь у нас есть всего 990 теоретически возможных значения контрольной суммы (от 2 до 991), на которые «отображаются» 900·900 вариантов пар передаваемых чисел (напомним, что все числа — трёхзначные, на отрезке [100,999])

Задача3. Для условия задачи 1 определите, сколько существует пар чисел, для которых контрольная сумма равна 421.

Решение. Если контрольная сумма равна 421, то число N может быть записано в виде «..421.». Сумма старших разрядов не может быть равна ни 42, ни 21, поэтому такое число может быть разбито на отдельные суммы только так: «.4|2|1.». Это значит, что сумма старших разрядов равна 2, сумма младших разрядов равна 4 или 14, а сумма средних может принимать любые значения от 10 до 18.

Подсчитаем, сколько есть возможных вариантов составления каждой из возможных сумм. Сумму 2 в старших разрядах мож-но получить только как 1+1. Для суммы 4 имеем 5 вариантов: 0+4, 1+3, 2+2, 3+1 и 4+0. Для суммы 10 минимальное из двух слагаемых равно 1, получается всего 9 вариантов: от 1+9 до 9+1. Рассуждая так же, для суммы 14 получаем 5 вариантов (от 5+9 до 9+5), а для суммы 18 — один вариант (9+9). Таким образом, существует 5+5=10 вариантов различных пар младших разрядов и 9+8+7+6+5+4+3+2+1=45 различных подходящих пар средних разрядов. Общее количество подходящих пар равно 1·45·10=450

 

 

 

 

Тема 12: Системы счисления. Перевод чисел из одной системы счисления в другую (углубленный)

 

Тема 12: Системы счисления. Перевод чисел из одной системы счисления в другую

 

При программировании мы часто сталкиваемся с необходимостью перевода чисел между системами счисления, по основанию: 2, 4, 8, 16 и 10.

Основание системы счисления указывает какое количество цифр используется в этой системе для написания чисел:

·         Привычная нам система счисления по основанию 10 (десятичная система счисления) использует 10 цифр: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. После 9 идёт не цифра, а число 10, состоящее из двух цифр: 1 и 0. Таким образом, мы записываем любые числа, используя указанные цифры в определённой последовательности.

·         Система счисления по основанию 2 (двоичная система счисления) использует 2 цифры: 0, 1.

·         Система счисления по основанию 4 (четверичная система счисления) использует 4 цифры: 0, 1, 2, 3.

·         Система счисления по основанию 8 (восьмеричная система счисления) использует 8 цифр: 0, 1, 2, 3, 4, 5, 6, 7.

·         Система счисления по основанию 16 (шестнадцатеричная система счисления) использует 16 цифр: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F. В данном случае, буквы ABCDEF являются цифрами. Цифра A шестнадцатеричной системы, равна числу 10 десятичной системы, цифра B равна числу 11 десятичной системы, ... , цифра F равна числу 15 десятичной системы.

Можно использовать любую систему счисления, например по основанию 12 (счет дюжинами), но наиболее популярными при программировании, являются: десятичная, шестнадцатеричная и двоичная, системы счисления.

Все выше перечисленные системы счисления относятся к позиционным системам. Значение числа зависит не только от того из каких цифр оно состоит, но и в какой последовательности они записаны. Например число 1234 не равно числу 4321.

 

 

 

 

 

 

 

Тема 11: Представление информации в компьютере. Двоичное кодирование. Равномерные и неравномерные коды. Декодирование сообщений, записанных с помощью неравномерных кодов (углубленный)

 

Тема 11: Представление информации в компьютере. Двоичное кодирование. Равномерные и неравномерные коды. Декодирование сообщений, записанных с помощью неравномерных кодов

Уч. https://profspo.ru/reader/book/132235

блог https://www.blogger.com/blog/settings/5176340769831596958

 

 

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

Знак — это заменитель какого-то объекта, который вызывает в сознании человека образ этого объекта. Например, знак напоминает горнолыжника, такой знак называется пиктограммой.

Символ — это знак, о значении которого люди договорились, наприме𠫧» — это символ параграфа, а — символ рубля. Если значение символов неизвестно, мы не сможем понять смысл сообщения, записанного с их помощью. Поэтому многие древние тексты до сих пор не расшифрованы.

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

Знаковая система определяется алфавитом (набором используемых знаков) и правилами выполнения операций с этими знаками.

 

Знакомые всем знаковые системы — это естественные языки, с помощью которых люди общаются в быту (русский, английский, китайский и др.). В естественных языках кроме правил есть и исключения. Кроме того, одно и то же слово может иметь различный смысл в зависимости от контекста, т. е. отрывка текста, в котором оно употребляется.

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

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

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

Информация передаётся в закодированном виде с помощью сигналов. Согласно определению, сигнал — это изменение свойств носителя, которое используется для передачи информации. Изменение выбранного свойства (например, силы тока, напряжения, освещённости) во времени можно описать в виде функции. Далее такую функцию тоже будем называть сигналом, как это принято в электронике и вычислительной технике.

В устройствах как радиоприёмник и микрофон, изменение электрического сигнала может произойти в любой момент и быть любым (в пределах допустимого диапазона). Такие сигналы называют аналоговыми.

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

Аналоговый сигнал — это сигнал, который в любой момент времени может принимать любые значения в заданном диапазоне

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

•                    изменяются только в отдельные моменты времени (дискретность по времени);

•                    принимают только несколько возможных значений (дискретность по уровню).

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

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

Равномерное и неравномерное кодирование

Алфавит — это набор знаков, который используется в языке.

Мощность алфавита — это количество знаков в алфавите.

Равномерный код — это код, в котором все кодовые слова имеют одинаковую длину.

Неравномерный код — это код, в котором кодовые слова имеют различную длину.

Двоичное кодирование — это кодирование с помощью двух знаков.

1 бит — это одна двоичная цифра (один знак сообщения, записанного в двоичном коде).

 

Равномерное кодирование

Если алфавит языка состоит из M знаков (имеет мощность M), то количество различных сообщений длиной L знаков вычисляется как

N = M^L.

Двоичный код — это сообщение, использующее алфавит из двух знаков (0 и 1), поэтому для двоичного кода эта формула запишется в виде

N = 2^L.

Неравномерное кодирование

При неравномерном кодировании коды различных знаков могут иметь разную длину. Это делается для того, чтобы сократить длину сообщения, используя сведения о частотах  встречаемости различных знаков. Знаки, которые встречаются в сообщениях чаще других (например, для текстов на русском языке — это пробел и буквы «О», «Е» и «А»), получают более короткие коды, а редко встречающиеся знаки — более длинные.

 

Правило умножения: N = M1 · M2 · ... ·ML, где Mk — это возможное количество вариантов выбора знака в позиции k сообщения.

Правило сложения: N = Nk + Nk+1 + ... + Nm, где Nq ( q = k, …, m) — это количество различных сообщений длиной q.

 

Декодирование

Условие Фано

В некоторых случаях даже при использовании неравномерного кода не требуется вводить символ-разделитель. Для этого достаточно выполнения условия Фано: ни одно кодовое слово не совпадает с началом другого кодового слова. Такой код называют префиксным

Сообщения, записанные с помощью равномерного кода, всегда

декодируются однозначно.

• Для того чтобы сообщение, закодированное с помощью неравномерного кода, можно было однозначно декодировать, достаточно выполнения условия Фано: ни одно кодовое слово не является началом другого кодового слова. Такой код называют префиксным.

• Условие Фано выполняется тогда и только тогда, когда в дереве, построенном по кодовой таблице, все вершины-знаки являются листьям