Пример блок-схемы алгоритма вычисления факториала числа N

Перечень вопросов к экзамену по дисциплине Информатика

1. Экономическая информация. Свойства и виды экономической информации

2. Количество информации, содержащееся в одном символе заданного алфавита. Неопределённость и избыточность естественного языка L

3. Кодирование информации. Примеры кодов.

4. Общая схема передачи дискретной информации. Типы канальных ошибок

5. Сжатие данных. Степень сжатия. Программы-архиваторы

6. Метод сжатия Шеннона-Фано

7. Методология подготовки и решения задачи на компьютере

8. Этапы решения задачи на компьютере

9. Понятие и свойство алгоритма

10. Формы представления алгоритма. Обозначения, используемые в блок- схемах

11. Виды алгоритмов. Примеры блок-схем для каждого вида алгоритма

12. Словесная форма представления алгоритма. Примеры.

13. Графическая форма представления алгоритма. Примеры.

14. Форма представления алгоритма. Псевдокод. Примеры.

15. Программная форма алгоритма. Примеры.

16. Доказательство правильности работы алгоритма

17. Линейные алгоритмы и их свойства. Примеры линейных алгоритмов

18. Алгоритмы с разветвлениями и их свойства. Примеры таких алгоритмов

19. Циклические алгоритмы и их свойства. Примеры таких алгоритмов

20. Итерационные циклы. Примеры

21. Вложенные циклы. Примеры

22. Составные данные однородной структуры. Примеры

23. Одномерные и двумерные массивы. Типы массивов, примеры

24. Представление массивов в памяти компьютера. Примеры

25. Организация ввода /вывода элементов массива. Примеры

26. Последовательность Фибоначчи и ее свойства. Решение задач на числах Фибоначчи

27. Решение задач с использованием рабочей ячейки

28. Общая характеристика языков программирования

29. Классификация языков программирования

30. Языки высокого уровня и их основные преимущества

31. Алфавит, синтаксис, семантика языка программирования

32. Трансляторы и компиляторы языков программирования

33. Основные компоненты алгоритмического языка

34. Основные понятия, используемые в языках высокого уровня (идентификаторы, операции, данные, выражения)

35. Типы выражений (арифметические, логические, строковые типы). Примеры

36. Операторы (команды) языка высокого уровня

37. Основные понятия языка VBA

38. Инструкции. Примеры

39. Имена и идентификаторы. Примеры

40. Типы данных языка VBA. Примеры

41. Время жизни переменной. Примеры

42. Описания языка VBA. Примеры

43. Инструкция DIM. Примеры

44. Описания переменных в языке VBA. Примеры

45. Библиотека стандартных функций VBA. Примеры

46. Операции и функции для данных логического типа. Примеры

47. Операции и функции для строковых данных. Примеры

48. Операторы языка VBA. Примеры

49. Ввод и вывод данных языке VBA. Примеры

50. Операторы присваивания. Примеры

51. Особенности программ на языке программирования VBA

52. Основные компоненты интегрированной среды разработки VBA

53. Структура окна редактирования кода

54. Константа и переменные VBA. Объявление констант и переменных

55. Программирование линейных алгоритмов. Примеры

56. Программирование разветвляющихся алгоритмов. Операторы типа IF. Примеры

57. Операции отношения. Логические операции. Примеры

58. Программирование разветвляющихся алгоритмов с помощью оператора Case. Примеры

59. Программирование цикла с известным числом повторений

60. Программирование с неизвестным числом повторений с помощью оператора цикла типа While

61. Программирование с неизвестным числом повторений с помощью оператора цикла типа Until

62. Досрочное прерывание цикла. Прерывание бесконечного цикла

63. Обработка массивов. Решение задач. Примеры

64. Отладка и тестирование программ. Выявление синтаксических ошибок транслятором.

Вопрос 1

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

Информация может существовать в виде:

* текстов, рисунков, чертежей, фотографий;

* световых или звуковых сигналов;

* радиоволн;

* электрических и нервных импульсов;

* магнитных записей;

* жестов и мимики;

* запахов и вкусовых ощущений;

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

* и т.д. (приведите примеры других видов существования информации).

Свойства информации (с точки зрения бытового подхода к определению информации):

* релевантность - способность информации соответствовать нуждам (запросам) потребителя;

* полнота - свойство информации исчерпывающе (для данного потребителя) характеризовать отображаемый объект или процесс;

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

* достоверность - свойство информации не иметь скрытых ошибок. Достоверная информация со временем может стать недостоверной, если устареет и перестанет отражать истинное положение дел;

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

* защищенность - свойство, характеризующее невозможность несанкционированного использования или изменения информации;

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

Вопрос 2

1 бит - минимальная единица измерения информации, при вероятностном подходе к измерению информации, принятом в теории информации, это количество информации, уменьшающее неопределенность знаний в 2 раза.

Связь между единицами измерения информации:

** 1 байт = 8 бит,

* 1 Кб (килобайт) = 2ю (1024) байт = 213 бит;

* 1 Мб (мегабайт) = 210 (1024) Кб = = 2го (1048576) байт = 223 бит;

* 1 Гб (гигабайт) = 210Мб = 220 Кб = 230 байт = 233 бит;

* 1 Тб (терабайт) = 210 Гб = 220Мб = 230 Кб = = 240 байт = 243 бит.

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

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

Избыточность также бывает:

1) Структурная – дублирование каналов связи с определением принятой информации по мажоритарному принципу.

2) Временная – многократная передача данных, достоверность которых определяется либо по мажоритарному, либо по статистическому принципу.

3) Функциональная – передача данных с использованием обратной связи.

Если мы проводим статистически испытания и возможно k равновероятных исходов, то степень неопределенности результата отдельного испытания определяется величиной k. При k=1 исход испытания не является случайным, а при большом k предсказыть исход испытания становится проблематичным.

Характеристика степени неопределенности результата испытания должна быть функцией k и при k=1 обращаться в нуль, так как неопределенность в этом случае отсутствует.

Предположим, что имеется два независимых испытания А и Б и пусть А имеет k равновероятных исходов, при испытании Б возможны l равновероятных исходов. Тогда комбинированное испытание АБ будет иметь неопределенность равную сумме неопределенностей испытания А и Б, ведь неопределенность испытания АБ характеризуется числом возможных исходов k×l. Этот факт наводит на мысль, что степень неопределенности испытания при k равновероятных исходах должна характеризоваться log(k).

Кажый отдельный исход, имеющий вероятность 1/k, вносит неопределенность, равную (1/k)×log(k).

Если в исходный момент времени степень неопределенности характеризовалась величиной Е₁, а после реализации события А неопределенность стала равной Е₂, причем Е₁>Е₂, то можно считать, что мы получили количество информации, равное Е₁ - Е₂, сопряженное с событием А. Для каналов передачи данных транспортировка ложного сообщения или информации о величайшем открытии, характерищующегося тем же числом бит, требует идентичных ресурсов. Мы привыкли мерить количество информации числом бит. Безусловно это не вполне корректно. Ведь можно передать из одной точки в другую терабайт нулей, при этом вряд ли можно говорить о большом объеме переданной информации.

Если число букв в алфавите равно n, а количество используемых элементарных сигналов - m, то при любом методе кодирования среднее число элементарных сигналов на одну букву алфавита не может быть меньше {log(n)/log(m)}. Однако оно может быть сколь угодно близко к этому отношению. В простейшем случае, когда при передаче используется только два уровня сигнала, m=2, т.е. число бит на одну букву равно log(n)/log(2).

Часто встречающиеся символы содержат малое количество информации, а редко встречающиеся большее. Если i-й символ определяется в результате k_iальтернативных выборов, то вероятность его появления равна (1/2)^k_i. Соответственно для выбора символа, который встречается с вероятностью p_i, нужно k_i= log₂(1/p_i) выборов. Смотри раздел Статический алгоритм Хафмана.

Количество информации, содержащееся в символе, которое определяется частотой его появления, равно:

log₂(1/p_i)   [бит]

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

E называют средним количеством информации на символ или энтропией источника информации. Результатом отдельного альтернативного выбора может быть <0> или <1>. Тогда всякому символу соответствует некоторая последовательность <0> и <1>. Такая последовательность является кодировкой символа. Энтропия одной буквы русского языка равна прмерно Е₁≈4,35 бит.

Если при некотором кодировании символов i-ый символ имеет длину N_i, то средняя длина слов равна:

Если предположить, что набор символов можно поделить на равновероятные подмножества, то L=E. Следует иметь в виду, что на самом деле всегда E ≤ L (следствие теоремы кодирования Шеннона).

Разность L-E называется избыточностью кода, а 1-(E/L) - относительной избыточностью кода.

Так как на практике отдельные символы встречаются с разной вероятностью, то кодирование с постоянной длиной кодовых слов обычно является избыточным. Так все стандартные 8-битовые кодировки русского алфавита являются избыточными. Значение энтропии для русского языка ≤ 4,35. Для точной оценки энтропии следует учесть вероятности различных пар и троек символов. Такой учет из-за корреляционных зависимостей может понизить значение Е. Учет вероятности всевозможных групп символов может понизить Е почти до уровня ≈1 бит на символ.

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

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

Обычный способ определения энтропии текста базируется на модели Маркова для текста. При этом вероятность появления очередного символа предполагается независимой от предыдущего символа (что, разумеется не всегда верно).

Если мы имеем n-буквенный алфавит и используем m-ичныйое кодовое представление (m уровней сигнала, при m=2 получем двоичное представление), то для передачи одной буквы может требоваться ~log(n)/log(m) элементарных сигналов.