Правила составления схем алгоритмов.блок схема алгоритма и её преимуществе.

1.Каждый блок имеет единственную точку входа кроме блока пуска который не имеет входа.

2.Каждый безусловный блок имеет единственную точку выхода кроме блока конца который не имеет ни одной точки выхода

3.Условный блок имеет 2 или 3 выхода

4.Выход условного блока можно пометить условиями-да, нет

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

6.Линия, исходящая из входной точки не может ветвиться на несколько направлений

7.Кажд.блок нуеруется, кроме начала и конца.рис и табл. В распечатке пример.

Блок-схемы полезны тем, что обеспечивают легкую «читаемость» алгоритма. Однако это не всегда так: стоит попытаться нарисовать блок-схему для более-менее сложного алгоритма, как она разрастается до невероятных размеров и теряет все свое наглядное преимущество. Поэтому блок-схемы хороши в структурном программировании для описания коротких алгоритмов.

17) Подход к измерению информации. Мера Хартли и неопределенности.

 

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

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

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

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

Существуют различные подходы к определению количества информации. Наиболее часто используются следующие два способа измерения информации: объёмный и вероятностный.

Объёмный подход

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

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

Для удобства использования введены и более крупные, чем бит, единицы количества информации. Так, двоичное слово из восьми знаков содержит один байт информации, 1024 байта образуют килобайт (кбайт), 1024 килобайта – мегабайт (Мбайт), а 1024 мегабайта - гигабайт (Гбайт).

Энтропийный (вероятностный) подход

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

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

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

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

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

Прагматический подход. Эта мера определяет полезность информации (ценность) для достижения пользователем поставленной цели.

В основе всей теории информации лежит открытие, сделанное Р. Хартли в 1928 году, и состоящее в том, что информация допускает количественную оценку.

Подход Р. Хартли основан на фундаментальных теоретико–множественных, по существу комбинаторных основаниях, а также нескольких интуитивно ясных и вполне очевидных предположениях.

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

Мера Хартли:

I = Log₂N = n*log₂q

Где q – глубина сообщений, n – длина сообщений

Мера неопределенности (Шеннона):

H = ∑ Pi log₂Pi

i=1

где P₂ = 50% = 1, Pilog₂ = 1

 

18) Представление чисел в различных системах счисления.

 

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

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

б) Для перевода дробной части числа ее умножают на основание системы счисления, фиксируя при этом целые части полученных произведений. Целые части в дальнейшем умножении не участвуют. Умножение производиться до получения 0 в дробной части произведения или до заданной точности вычисления.

в) Ответ записывают в виде сложения переведенной целой и переведенной дробной части числа.

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

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

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

 

ТАБЛИЦА СООТВЕТСТВИЯ ЧИСЕЛ В РАЗЛИЧНЫХ СИСТЕМАХ СЧИСЛЕНИЯ.

10-ая система счисления	2-ая система счисления	8-ая система счисления	16-ая система счисления
			A
			B
			C
			D
			E
			F

 

 

19) Представление данных в ПК

Целые числа. Как мы уже знаем, этот тип информации является дискретным и преобразуется для хранения в компьютере довольно просто: достаточно перевести число в двоичную систему счисления. Некоторые особенности будет иметь кодирование целых отрицательных чисел, но мы их рассмотрим в вопросе, связанном с представлением числовой информации.

Вещественные числа. В отличие от целых, вещественные числа являются непрерывными. Следствием из этого является возможность дальнейшего деления любого сколь угодно малого числа, что приводит, вообще говоря, к бесконечному числу разрядов в изображении числа (вспомните 1/3! ). Для того, чтобы в ЭВМ как-то представить числа в виде конечного набора двоичных цифр, приходится ограничиваться определенной точностью и младшие разряды просто игнорировать. Отсюда могут возникать некоторые принципиальные проблемы, например, при сравнении двух вещественных значений на равенство. Хорошо известен, например, следующий " счетный" эффект. Возьмем отрезок от 0 до 1 и разделим его на N равных частей, например, на 1000; тогда величина каждой части h=1/N. Выполним по отрезку ровно N шагов, вычисляя каждый раз значение аргумента по формуле X=X+h. По идее, последнее значение X=Nh должно равняться единице, однако на практике точного равенства, как правило, не будет, а значение X будет чуть-чуть меньше. Учтите на будущее этот парадокс и всячески старайтесь избегать сравнения вещественных чисел на равенство.

Символы. Это еще одна дискретная величина, поскольку компьютер оперирует с определенным ограниченным набором символов. Такой набор вполне можно назвать алфавитом машины, а в алфавите все символы имеют свои фиксированные позиции. Отсюда основная идея хранения символов в памяти ЭВМ состоит в замене каждого из них номером в алфавите, т.е. числом.

Помимо такого очевидного достоинства, как компактность хранения, замена символа его номером имеет и определенные недостатки. В частности, текст может быть правильно воспроизведен на другом компьютере только в том случае, если алфавиты обоих компьютеров совпадают. И если для латинских букв, на которые существует единый стандарт, это совсем не жесткое требование, то с русскими текстами дело обстоит заметно хуже. Достаточно сказать, что даже в пределах одного компьютера кодировка русских букв в операционных системах MS-DOS и Windows различна. Несколько утешает тот факт, что задача перекодировки текста является очень простой, и, если правильно указать исходную и требуемую кодировку, прекрасно решается автоматически.

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

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

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

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

Звук. Звуковая информация также является величиной непрерывной, и, следовательно, для ввода в ЭВМ нуждается в дискретизации. Причем дискретизация должна производится как по времени, так и по величине интенсивности звука. Первый процесс означает, что замеры интенсивности должны производится не непрерывно, а через определенные промежутки времени, а второй – что интенсивность звука, которая в природе может принимать какие угодно значения, должна быть " подтянута" (" округлена" ) к ближайшему из стандартного набора фиксированных значений. При такой процедуре мы снова получаем последовательность целых чисел, которые и сохраняются в памяти ЭВМ. Таким образом, и в случае звука информацию удается описать определенным образом сформированной последовательностью чисел, что автоматически решает проблему кодирования.

 

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

А) из 10 в любую

- умножить исходную дробь в десятичной системе счисления на основание новой системы счисления, выделить целую часть – она будет первой цифрой новой дроби; отбросить целую часть

- для оставшейся дробной части операцию с выделением целой и дробных частей повторять пока в дробной части не окажется 0 или не будет достигнута желаемая точность конечного числа; появляющиеся при этом целые будут цифрами новой дроби

- записать дробь в виде последовательности цифр и после 0 с разделителем в порядке получения пункта 1 или 2

Б) из любого основания в 10

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

Пример 3.10. Выполнить перевод из двоичной системы счисления в десятичную числа 0, 11012. Имеем:

0, 11012 = 1*2^-1 + 1*2^-2 + 0*2^-3 +1*2^-4 = 0, 5 + 0, 25 + 0 + 0, 0625 = 0, 8125.

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

Таким образом, 0, 11012 = 0, 8125.

 

21) Алгоритм перевода целых чисел из одной системы счисления в другую.

 

А) из 10 основания в другое

Любая позиционная система счисления характеризуется основанием

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

X_10→ X_q

Пример:

25_10→ X₃

X = 221₃

Б) из любого основания в 10

102₃→ X₁₀

X = (3⁰*2)+(3²*1)+(3¹+0) = 2+9 = 11₁₀

 

 

22) Система счисления. Позиционные и непозиционные системы.

 

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

Делятся на:

- позиционные

- непозиционные

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

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

Примеры: десятичная, двоичная, шестнадцатиричная.

 

23) Основные логические операции.

 

1. Отрицание (инверсия), от латинского inversio -переворачиваю:

соответствует частице НЕ, словосочетанию НЕВЕРНО, ЧТО;

обозначение: не A, A, -A;

таблица истинности:

вход	выход
А	В

Инверсия логической переменной истинна, если сама переменная ложна, и, наоборот, инверсия ложна, если переменная истинна.

пример: A = {На улице идет снег}.

A={Не верно, что на улице идет снег}

A={На улице не идет снег};

логическая схема (инвертор):

2. Логическое сложение (дизъюнкция), от латинского disjunctio - различаю:

соответствует союзу ИЛИ;

обозначение: +, или, or, V;

таблица истинности:

выход	вход
А	В	С (F)

 

Дизъюнкция ложна тогда и только тогда, когда оба высказывания ложны.

пример: F={На улице светит солнце или дует сильный ветер};

логическая схема (дизъюнктор)

3. Логическое умножение (конъюкция), от латинского conjunctio -связываю:

соответствует союзу И

(в естественном языке: и А, и В

как А, так и В

А вместе с В

А, не смотря на В

А, в то время как В);

обозначение: Ч, •, &, и, ^, and;

таблица истинности:

вход	выход
А	В	С (F)

Конъюкция истинна тогда и только тогда, когда оба высказывания истинны.

Например: F={На улице светит солнце и дует сильный ветер};

логическая схема (конъюктор):

4. Импликация (логическое следование), от латинского implicato - тесно связываю:

соответствует речевому обороту ЕСЛИ....ТО

(в естественном языке: если А, то В

В, если А

В необходимо для А

А достаточно для В

А только тогда, когда В

В тогда, когда А

Все А есть В;

обозначение: →;

таблица истинности:

вход	выход
A	B	C

Импликация истинна всегда, за исключением случая, когда А истинно, а В ложно.

пример:

F=A→ B

5. Эквиваленция (равнозначность), от латинского aequivalens - равноценные:

соответствует речевым оборотам

ЭКВИВАЛЕНТНО:

необходимо и достаточно для

тогда и только тогда, когда;

обозначение: =, ↔;

таблица истинности:

вход	выход
A	B	A↔ B

 

Эквиваленция истинна тогда и только тогда, когда оба высказывания одновременно либо истинны, либо ложны.

пример: Я пойду гулять тогда и только тогда, когда выучу все уроки.

6. Cложение по модулю 2 (логи́ ческое сложе́ ние, исключа́ ющее «и́ ли», строгая дизъюнкция, XOR, поразрядное дополнение, побитовый комплемент)

Обозначение: A⊕ B

таблица истинности:

вход	выход
A	B	A⊕ B

 

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

Законы логики.

Равносильности формул логики высказываний часто называют законами логики.
Знание законов логики позволяет проверять правильность рассуждений и доказательств.
Нарушения этих законов приводят к логическим ошибкам и вытекающим из них противоречиям.
Перечислим наиболее важные из них:
1. Xº X Закон тождества
2. Закон противоречия
3. Закон исключенного третьего
4. Закон двойного отрицания
5. XÙ Xº X, XÚ Xº C Законы идемпотентности
6. C Ù U º U Ù C, C Ú U º U Ú C Законы коммутативности (переместительности)
7. ( C Ù U ) Ù Z º C Ù ( U Ù Z ), ( C Ú U ) Ú Z º C Ú ( U Ú Z ) - Законы ассоциативности (сочетательности)
8. C Ù ( U Ú Z ) º ( C Ù U ) Ú ( C Ù Z ), C Ú ( U Ù Z ) º ( C Ú U ) Ù ( C Ú Z ) - Законы дистрибутивности (распределительности)
9. , Законы де Моргана
10. XÙ 1º C, C Ú 0 º C
11. C Ù 0 º 0, C Ú 1 º 1
12. C Ù ( C Ú U ) º C, C Ú ( C Ù U ) º C Законы поглощения
13. ( C Ú U ) Ù ( Ú U ) º U, ( C Ù U ) Ú ( Ú U ) º U Законы склеивания

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

Закон противоречия говорит о том, что никакое предложение не может быть истинно одновременно со своим отрицанием.
“Это яблоко спелое” и “Это яблоко не спелое”.

Закон исключенного третьего говорит о том, что для каждого высказывания имеются лишь две возможности: это высказывание либо истинно либо ложно. Третьего не дано. “Сегодня я получу 5 либо не получу”. Истинно либо суждение, либо его отрицание.

Закон двойного отрицания. Отрицать отрицание какого-нибудь высказывания - то же, что утверждать это высказывание.
“ Неверно, что 2× 2¹ 4”

Законы идемпотентности. В алгебре логики нет показателей степеней и коэффициентов. Конъюнкция одинаковых “сомножителей” равносильна одному из них.

Законы коммутативности и ассоциативности. Конъюнкция и дизъюнкция аналогичны одноименным знакам умножения и сложения чисел.
В отличие от сложения и умножения чисел логическое сложение и умножение равноправны по отношению к дистрибутивности: не только конъюнкция дистрибутивна относительно дизъюнкции, но и дизъюнкция дистрибутивна относительно конъюнкции.

Смысл законов де Моргана (Август де Морган (1806-1871) - шотландский математик и логик) можно выразить в кратких словесных формулировках:
- отрицание логического произведения эквивалентно логической сумме отрицаний множителей.
- отрицание логической суммы эквивалентно логическому произведению отрицаний слагаемых.

Доказать законы логики можно:
1) с помощью таблиц истинности;
2) с помощью равносильностей.
Докажем законы склеивания и поглощения с помощью равносильностей:
1) ( C Ú U ) Ù ( Ú U ) º ( C + U ) × ( + U ) º C × + U × + U × U + C × U º U × + U + C × U º U × + +U ( 1 + C ) º U × + U º U ( + 1 ) º U (Закон склеивания)

2) C Ù ( C Ú U ) º C × C +C × U º C +C × U º C ( 1 + U ) º C (Закон поглощения)

⇐ Предыдущая12345Следующая ⇒

Поделиться: