Коды Хемминга

Содержание

Слайд 2

Передается двоичная последовательность. В процессе передачи возможны ошибки:
1→ 0; 0→1.
Предполагается, что возникает

Передается двоичная последовательность. В процессе передачи возможны ошибки: 1→ 0; 0→1. Предполагается,
только одна ошибка.
Например 100111000011000→110111000011000. Как обнаружить ошибку? – добавить проверочные символы:

Мы видим, что невозможно исправить ошибку, поскольку множества ошибок совпадают.

Слайд 3

Добавим ещё один проверочный символ:
Кодирование
1→ 111→ {011,101,110}
0→ 000→ {100,010,001}
Декодирование
{011,101,110} →

Добавим ещё один проверочный символ: Кодирование 1→ 111→ {011,101,110} 0→ 000→ {100,010,001}
111 → 1
{100,010,001}→ 000 → 0

Таким образом по полученному ошибочному сообщению возможно обнаружить и
исправить одну ошибку.

Слайд 4

Алгоритм

Слово «алгоритм» появилось в результате искаженного перевода с арабского на европейские языки

Алгоритм Слово «алгоритм» появилось в результате искаженного перевода с арабского на европейские
имени узбекского ученого IX века Аль-Хорезми, который изложил правила арифметических действий над числами в позиционной десятичной системе. Эти правила и назвали алгоритмами (Альхорезми «имя»+ Аритмос «число»= алгоритм)

Слайд 5

«Алгори́тм — набор инструкций, описывающих порядок действий исполнителя для достижения результата решения

«Алгори́тм — набор инструкций, описывающих порядок действий исполнителя для достижения результата решения
задачи за конечное число действий, при любом наборе исходных данных.» Википедия

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

Слайд 6

Примеры алгоритмов

Пример 1 – нарезание апельсина на дольки:
Начало
достать нож;
нарезать апельсин на дольки

Примеры алгоритмов Пример 1 – нарезание апельсина на дольки: Начало достать нож;
(Именно апельсин, а не любой другой фрукт. За это отвечает ТОЧНОСТЬ);
достать тарелку;
выложить на тарелке;
подать к столу.
Конец
Пример 2 – Зная длины трех сторон треугольника, вычислить площадь и периметр треугольника.
Пусть a, b, c - длины сторон треугольника. Необходимо найти S - площадь треугольника, P - периметр.
Для нахождения площади можно воспользоваться формулой Герона:
Входные данные: a, b, c.
Выходные данные: S, P.

Слайд 7

Удобно представить графически:

Найдите неточность в схеме!

Удобно представить графически: Найдите неточность в схеме!

Слайд 8

Блок-схемы

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

Блок-схемы Блок-схемой называется наглядное графическое изображение алгоритма, когда отдельные его этапы изображаются
помощи различных геометрических фигур - блоков, а связи между этапами (последовательность выполнения этапов) указываются при помощи стрелок, соединяющих эти фигуры. Блоки сопровождаются надписями. Типичные действия алгоритма изображаются следующими геометрическими фигурами:
Блок начала-конца алгоритма. Надпись на блоке: "начало" ("конец").
Блок ввода-вывода данных . Надпись на блоке: слово "ввод" ("вывод" или "печать") и список вводимых (выводимых) переменных.

Начало

Конец

Слайд 9

Блок решения или арифметический (. Надпись на блоке: операция или группа операций.

Условный

Блок решения или арифметический (. Надпись на блоке: операция или группа операций.
блок. Надпись на блоке: условие. В результате проверки условия осуществляется выбор одного из возможных путей (ветвей) вычислительного процесса. Если условие выполняется, то следующим выполняется этап по ветви «Да", если условие не выполняется, то выполняется этап по ветви «Нет".

Условие

Да

Нет

Слайд 10

Блок-схема алгоритма решения квадратного уравнения

Нет

Да

Блок-схема алгоритма решения квадратного уравнения Нет Да

Слайд 11

Виды алгоритмов

Линейный алгоритм - это такой, в котором все операции выполняются последовательно

Виды алгоритмов Линейный алгоритм - это такой, в котором все операции выполняются последовательно одна за другой
одна за другой

Слайд 12

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

Алгоритмы разветвленной структуры применяются, когда в зависимости от некоторого условия необходимо выполнить
либо одно, либо другое действие. В блок-схемах разветвленные алгоритмы изображаются так:
Или так:
Вариант обозначения «Да» - «+»; «Нет» – «-».

Слайд 13

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

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

Слайд 14

Существуют другие уточнения понятия алгоритма

Машины Тьюринга

Существуют другие уточнения понятия алгоритма Машины Тьюринга

Слайд 15

Алгоритмы Маркова

Машины Поста

Алгоритмы Маркова Машины Поста

Слайд 16

Алан Тьюринг высказал предположение (известное как Тезис Чёрча — Тьюринга), что любой

Алан Тьюринг высказал предположение (известное как Тезис Чёрча — Тьюринга), что любой
алгоритм в интуитивном смысле этого слова может быть представлен эквивалентной машиной Тьюринга. Уточнение представления о вычислимости на основе понятия машины Тьюринга (и других эквивалентных ей понятий) открыло возможности для строгого доказательства алгоритмической неразрешимости различных массовых проблем (то есть проблем о нахождении единого метода решения некоторого класса задач, условия которых могут варьироваться в известных пределах). Простейшим примером алгоритмически неразрешимой массовой проблемы является так называемая проблема применимости алгоритма (называемая также проблемой остановки). Она состоит в следующем: требуется найти общий метод, который позволял бы для произвольной машины Тьюринга (заданной посредством своей программы) и произвольного начального состояния ленты этой машины определить, завершится ли работа машины за конечное число шагов, или же будет продолжаться неограниченно долго.
Имя файла: Коды-Хемминга.pptx
Количество просмотров: 81
Количество скачиваний: 0