Задания к лабораторной работе

Задано сообщение, состоящее из букв алфавита {a, b, c, d, e, f, g, h, i}.

1. Найти количество информации приходящейся на 1 символ сообщения по вероятностному и объемному подходам.

2. Построить для данного алфавита равномерный код.

3. Построить код Шеннона – Фано.

4. Построить код Хаффмана.

5. Найти избыточность построенных кодов

Варианты

1. aaaabbbbbbccdddddddeeeeeffggghhi

2. adadbbfbabccdfdfaddebiieffbghhi

3. aaaaaabbbbbbccdddddeeeeeffggghhi

4. abcdeffbbbccdddddddeeeeeffggghii

5. . iiaaffaabbccdddddddaeeeeffggghbb

6. aaaaaaabbbbbbccccdddeefffggghhi

7. iiaabbbbbbccdddddddeeeeeffggghhfa

8. iaaabbbibbccdidddddeeieeffggghha

9. baaabfbbbbbcdddddddebeeeffgahiih

10. aaaaaabbbbccdddddddeeeeffffgghhi

11. aabbbbbbccdddddddeeeeeffggghhiiiii

12. aaaaffaaabbcccdddddeediiffggghhi

13. faaabbfbbbccdfdddddeefeeffggghhif

14. caaabbcbbbccdddcdddeeceeffggghhic

15. baaabbcbbbccddbddddeebeeffggghhibi

16. .iaaibbbibbccdddidddeeieeffgighhii

Лабораторная работа 4 Проектирование конечного автомата

Время выполнения — 4 часа (+2).

Задания к лабораторной работе

1. Для заданного конечного автомата построить:

• Граф переходов

• Таблицу переходов и выходов

• Закодированную таблицу реализации КА

• *Программную реализацию в виде блок-схемы и на одном из языков программирования.

• ** Схему аппаратной реализации

Примечание. Задания со звездочками являются не обязательными.

Варианты:

1. Пульт дистанционного управления магнитофоном

2. Пульт дистанционного управления телевизором

3. Стиральная машина – автомат

4. Микроволновая печь

5. Автомат газ-вода

6. Лифт

7. Электронные часы

8. Простейший микрокалькулятор

9. Сотовый телефон (на примере одного режима)

10. Манипулятор «мышь»

11. Магнитофон

12. Телевизор

13. Музыкальный автомат

14. Светофор

15. Модель поведения «экзаменатора»

16. Система голосования

Лабораторная работа 5 Машина Поста

Время выполнения — 4 часа (+4).

Задания к лабораторной работе

Разработать алгоритм для машины Поста и реализовать его с помощью эмулятора.

Вариант 1

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

Вариант 2

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

Вариант 3

На информационной ленте машины Поста расположено N массивов меток, отделенных друг от друга свободной ячейкой. Каретка находится над крайней левой меткой первого массива. Определить количество массивов.

Вариант 4

Игра Баше. В игре участвуют двое (человек и машина Поста). Написать программу, по которой всегда будет выигрывать машина Поста. Суть игры заключается в следующем: имеется 21 предмет. Первым ходит человек. Каждый из играющих может брать 1,2,3 или 4 предмета. Проигрывает тот, кто берет последний предмет.

Вариант 5

Число k представляется на ленте машины Поста k+1 идущими подряд метками. Одна метка соответствует нулю. Составить программу прибавления 1 к произвольному числу k. Каретка расположена над одной из меток, принадлежащих заданному числу k.

Вариант 6

Составить программу сложения 2-х целых неотрицательных чисел a и b, расположенных на ленте машины Поста. Каретка расположена над одной из меток, принадлежащих числу a. Число b находится правее числа a через несколько пустых секций.

Вариант 7

Составить программу сложения произвольного количества целых неотрицательных чисел, записанных на ленте машины Поста на расстоянии одной пустой секции друг от друга. Каретка находится над крайней левой меткой левого числа.

Вариант 8

На ленте машины Поста расположен массив из N меток. Составить программу, действуя по которой машина выяснит, делится ли число на 3. Если да, то после массива через одну пустую секцию поставить метку V.

Вариант 9

Число k представлено на ленте машины Поста k+1 идущими подряд метками. Найти остаток от деления целого неотрицательного числа k на 3, если известно , что каретка находится справа от заданного числа.

Вариант 10

Составить программу нахождения разности двух неотрицательных целых чисел a и b, находящихся на ленте машины Поста. Каретка находится над левой меткой левого числа. Неизвестно, какое число больше: a или b.

Вариант 11

На ленте машины Поста расположен массив из 2*N отмеченных секций. Составить программу, по которой машина Поста раздвинет на расстояние в 1 секцию две половины данного массива.

Вариант 12

На ленте машины Поста расположен массив из 2*N–1 меток. Составить программу отыскания средней метки массива и стирания ее.

Вариант 13

На ленте машины Поста расположены два массива. Составить программу стирания большего из этих массивов.

Вариант 14

На информационной ленте машины Поста находятся два массива в M и N меток. Составить программу выяснения, одинаковы ли массивы по длине.

Вариант 15

Задача В.А.Успенского. На информационной ленте либо вправо, либо влево от секции, над которой расположена каретка, находится массив меток. Расстояние до массива выражается конечным числом. Необходимо составить программу, работая по которой машина Поста найдет этот массив и установит каретку на начало этого массива.

Вариант 16

На ленте машины Поста находится n массивов меток, после последнего массива на расстоянии более 3-х пустых секций находится 1 метка. Массивы разделены 3-я пустыми ячейками. Количество меток в массивах не может быть меньше 2-х. Произвести обработку массивов следующим образом: если количество меток в массиве кратно 3, то стереть метки в данном массиве через одну, иначе массив стереть полностью. Каретка находится над крайней левой меткой первого массива.

Лабораторная работа 6 Математическая логика

Выполнить тест в обучающей среде по матлогике

Лабораторная работа 7 Введение в Excel

Время выполнения — 4 часа (+2).

Задания к лабораторной работе

С помощью Excel выполнить следующие задания:

1. Построить график функции y = f(x) на заданном отрезке [a,b]

2. Затабулировать функцию двух переменных Z = F(x,y) и изобразить ее поверхность

3. Разработать игру

Вариант 1

1. f(x) = x*Sin(x*x)

2. F(x,y) = x*y*Sin(x+y)

3. Игра «Угадай число»

Вариант 2

4. f(x) = x + x Sin(x)

5. F(x,y) =(x + y)*Sin(x*y)

6. Игра «Баше»

Вариант 3

7. f(x) = x*Cos(x*x)

8. F(x,y) = x*y*Cos(x+y)

9. Игра «Угадай число»

Вариант 4

10. f(x) = exp(x)*Cos(x)

11. F(x,y) =(x + y)*Cos(x*y)

12. Игра «Баше»

Вариант 5

13. f(x) = x*tg(x*x)

14. F(x,y) = x*y*tg(x+y)

15. Игра «Угадай число»

Вариант 6

16. f(x) = Sin(x)*tg(x)

17. F(x,y) =(x + y)*tg(x*y)

18. Игра «Баше»

Вариант 7

19. f(x) = x*Cos(x) + exp(x)

20. F(x,y) = x*y*Cos(x) +y*Sin(x)

21. Игра «Угадай число»

Вариант 8

22. f(x) = exp(Sin(x))

23. F(x,y) =xSin(y)+Cos(x*y)

24. Игра «Баше»

Вариант 9

25. f(x) = x*x*Sin(x)

26. F(x,y) y*Sin(x+y)+x*x

27. Игра «Угадай число»

Вариант 10

28. f(x) = x - x tg(x)

29. F(x,y) =Cos(x + y)*Sin(x*y)

30. Игра «Баше»

Вариант 11

31. f(x) = x*Cos(x)-tg(x)

32. F(x,y) = x* Cos(x+y) + y*Sin(x)

33. Игра «Угадай число»

Вариант 12

34. f(x) = exp(x)+Cos(x)

35. F(x,y) =(x * y)*Cos(x/y)

36. Игра «Баше»

Вариант 13

37. f(x) = x/tg(x*x)

38. F(x,y) = x*Cos(y)*tg(x+y)

39. Игра «Угадай число»

Вариант 14

40. f(x) = ArcSin(x)*tg(x)

41. F(x,y) =(x + y)*arctg(x*y)

42. Игра «Баше»

Вариант 15

43. f(x) = x*ArcCos(x)

44. F(x,y) = (x+y)*Cos(x) +y*Sin(x)

45. Игра «Угадай число»

Вариант 16

46. f(x) = Cos(x*x)/x

47. F(x,y) =x Cos(x+y)+ exp(y)

48. Игра «Баше»

Лабораторная работа 8 Алгоритмизация и программирование. Искусственный интеллект и компьютерное моделирование

Время выполнения — 4 часа (+6).

Задания к лабораторной работе

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

2. Составить синтаксические диаграммы для элементов языка Бейсик

3. Разработать алгоритм имитационного моделирования задачи

Примечание. Алгоритмы реализовать с помощью Excel.

Вариант 1

1. А, Б, В, Г, Д

2. Составной оператор

3. Модель очереди в магазине

Вариант 2.

1. Е, Ж, З, И, К

2. Идентификатор

3. Модель ожидания автобуса на остановке

Вариант 3

1. Л, М, Н, О, П

2. Оператор цикла с параметром

3. Модель очереди клиентов в банк

Вариант 4

1. Р, С, Т, У, Ф

2. Оператор цикла с постусловием

3. Модель ожидания телефонного разговора

Вариант 5

1. Х, Ц, Ч, Ш, Ы

2. оператор цикла с предусловием

3. Модель очереди в магазине

Вариант 6

1. Ь, Ъ, Э, Ю, Я

2. Условный оператор

3. Модель ожидания автобуса на остановке

Вариант 7

1. А, В, И, Д, Г

2. оператор присваивания

3. Модель очереди клиентов в банк

Вариант 8.

1. А, Ж, Р, И, К

2. вещественное число

3. Модель ожидания телефонного разговора

Вариант 9

1. Л, Ф, Н, О, А

2. оператор

3. Модель очереди в магазине

Вариант 10

1. А, Ш, О, П, В

2. комментарий

3. Модель ожидания автобуса на остановке

Вариант 11

1. Х, Ц, Ч, Ш, В

2. неполный условный оператор

3. Модель очереди клиентов в банк

Вариант 12

1. А, Д, Э, Ю, Я

2. имя переменной

3. Модель ожидания телефонного разговора

Вариант13

1. Д, Б, Ф, Г, Д

2. описание одномерного массива

3. Модель очереди в магазине

Вариант 14.

1. Е, А, З, М, К

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

3. Модель ожидания автобуса на остановке

Вариант15

1. Ф, Б, А, Г, Д

2. описание одномерного массива

3. . Модель ожидания телефонного разговора

Вариант 16.

1. П, Н, З, М, К

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

3. Модель очереди в магазине

Указания к 3 заданию. Необходимо определить ряд частных задач, которые необходимо решить в процессе моделирования. Разработать блок-схему алгоритма и составить программу на одном из языков программирования или в среде Excel, затем провести расчеты и найти ответы на поставленные задачи.

Например, рассмотрим задачу ожидания пассажиром автобуса на остановке. Пусть интервал движения автобуса 10 мин. Время прихода пассажира на остановку – величина случайная и его время ожидания автобуса можно смоделировать генератором случайных чисел в интервале [0..10]. Каково среднее время ожидания автобуса за длительный период? Для решения задачи составим алгоритм, в котором предусмотрим цикл с параметром N - количества прихода пассажира на остановку. В этом цикле генерируем случайное число в интервале [0..10] (время ожидания автобуса) и запоминаем в массиве Time[1..N]. Затем можно найти среднее время ожидания путем нахождения среднего значения элементов массива - (Time[1] + …+Time[N])/N.

А каково среднее время ожидания транспорта, если на маршруте два автобуса с интервалами 10 и 8 мин.? Тогда в цикле генерируем два случайных числа в интервалах [0..10] и [0..8] соответственно. В массив Time[1..N] заносим минимальное из этих чисел (мы садимся на автобус, которой приходит на остановку первым!). Нетрудно смоделировать случай К подходящих транспортных средств.

Время ожидания автобуса влияет на количество пассажиров, скапливающихся на остановке. Это количество зависит от вероятности прихода пассажиров на остановку. Приход пассажиров на остановку также величина случайная и можно задавать их количество в единицу времени. Скажем в утренние часы 5 в минуту, а в не пиковое время 1 в минуту. Владельцам маршруток экономически выгодно знать напряженность перевозок и регулировать количество транспорта на маршрутах!

Пример имитационного моделирования.

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

Цель моделирования: Определить среднее время ожидания в очереди к прилавку и среднее время, проведенное продавцом в ожидании покупателя (магазин пуст).

Анализ объекта: На входе этой задачи случайный процесс прихода покупателей в магазин. Он является «марковским», т.е. промежутки между приходами любой последовательной пары покупателей – независимые случайные события, распределенные по некоторому закону. Реальный характер этого закона может быть установлен лишь путем многочисленных наблюдений; в качестве простейшей модельной функции плотности вероятности можно взять равновероятное распределение в диапазоне времени от 0 до некоторого T – максимально возможного промежутка между приходами двух последовательных покупателей. При этом распределении вероятность того, что между приходами двух покупателей пройдет 1 минута, 3 минуты или 8 минут одинакова (если T > 8).

Второй случайный процесс в этой задаче, никак не связанный с первым, сводится к последовательности случайных событий – длительностей обслуживания каждого из покупателей. Распределение вероятностей длительности обслуживания качественно имеет тот же вид, что и в предыдущем случае. Равномерно распределенные случайные числа – простейший случай. Располагая датчиком случайных чисел, генерирующим числа r  [0, 1], легко получить числа из произвольного интервала [a, b]:

X = a + (b - a) * r