Учебно- методический комплекс учебной дисциплины дпп. 04"Теоретические основы информатики" подготовки бакалавра по направлению 050200 «Физико-математическое образование» Работа принята в фонд учебно-методического управления пи юфу

Вид материала

Учебно-методический комплекс

Содержание Содержание лабораторных занятий Методические рекомендации для преподавателей Методические рекомендации для студентов Контрольные вопросы и задания для самостоятельной работы по теме: «Элементы теории информации» Контрольные вопросы и задания для самостоятельной работы по теме: «Понятие алгоритма и рекурсивный подход в программировании» N меток. Построить такое же количество меток справа от имеющихся через одну пустую. е) на ленте находятся два числа N While ... do

Подобный материал:

• Учебно-методический комплекс учебной дисциплины ен. В. 01 по выбору (информатика) «Программирование, 553.96kb.
• Учебно-методический комплекс учебной дисциплины сдм. 02 «программирование» подготовки, 879.43kb.
• Магистерская программа «Языковое образование (русский язык)» умк принят в фонд учебно-методического, 541.81kb.
• Учебно-методический комплекс дпп ф. 03. Старославянский язык Специальность 050301 Русский, 2969.23kb.
• Учебно-методический комплекс дпп. Ф. 01. Теория языка Специальность 050301 Русский, 889.66kb.
• Учебно-методический комплекс дисциплины теоретические основы современного языкознания, 858.32kb.
• Программа вступительного экзамена в магистратуру по направлению 050200 «Физико-математическое, 500.22kb.
• Учебно-методический комплекс курса по выбору (опд) Направление подготовки 050202., 311kb.
• Контрольная работа по дисциплине «Теоретические основы информатики» направление 050200., 66.3kb.
• Учебно-методический комплекс опд. Ф. 04 Теория и методика обучения русскому языку Специальность, 658.5kb.

^ СОДЕРЖАНИЕ ЛАБОРАТОРНЫХ ЗАНЯТИЙ

Лабораторная работа № 1

Информация, информатика и информационные процессы в обществе

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

Лабораторная работа № 2

ЭВМ как универсальное средство обработки информации

Студенты учатся работать с числами, принадлежащими множеству чисел с плавающей запятой. Знакомятся с машинной арифметикой. Пишут программу для вычисления машинного е. Решают задачи на перевод чисел из одной системы в другую, например из арабской в римскую, представляют числа в нормированном виде и др.

Лабораторная работа № 3

Понятие алгоритма и его характерные черты. Способы представления алгоритмов

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

Лабораторная работа № 4 - 6

Рекурсивный подход в программировании

Студентам предлагается составить программу вычисления значения функции Аккермана, написать программу для решения СЛАУ методом простых итераций. Решение задач на кодирование и декодирование информации.

Лабораторная работа № 7, 8

Алгоритмы оптимизации на сетях и графах

В данной лабораторной работе предлагается студентам в программе решение СЛАУ методом простых итераций оценить полученный результат при помощи относительной погрешности и оценить сходимость метода.

Решают задачи по реализации алгоритмов оптимизации на сетях и графах.


^ МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ДЛЯ ПРЕПОДАВАТЕЛЕЙ

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

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

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

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

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

^ МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ДЛЯ СТУДЕНТОВ

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

^ Контрольные вопросы и задания для самостоятельной работы по теме: «Элементы теории информации»

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

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

3. Приведите примеры неоднозначного и однозначного соответствия между сообщением и содержащейся в нем информацией.

4. Почему хранение информации нельзя считать информационным процессом?

5. В чем состоит различие понятий «приемник сообщения» и «приемник информации»?

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

7. Приведите примеры знаков-символов. Могут ли символы образовывать алфавит?

8. В шестнадцатеричной системе счисления используются цифры А, В, С, D, Е, F. Следует ли эти знаки считать символами?

9. В тексте данной главы разграничиваются понятия «знак», «буква», «символ». Как соотносится с ними понятие «цифра»?

10. В чем состоит смысл и значение теоремы отсчетов?

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

12. Как следует понимать термины «оцифровка изображения» и «оцифровка звука»? Какими устройствами производятся данные операции?

13. Приведите примеры преобразований типа D₁ → D₂, при которых информация, содержащаяся в исходном сообщении, может не сохраняться.

14. Почему для представления дискретных сообщений в качестве базового выбирается двоичный алфавит?

15. Почему компьютер является универсальным устройством по обработке информации?

16. В чем состоит и как проявляется несимметричность непрерывной и дискретной форм представления информации?

17. Почему в определении энтропии как меры неопределенности выбрана логарифмическая зависимость между Н и n? Почему выбран log₂ ?

18. Какова энтропия следующих опытов:

(a) бросок монеты;

(b) бросок игральной кости;

(c) вытаскивание наугад одной игральной карты из 36;

(d) бросок двух игральных костей.

19. Алфавит русского языка содержит 34 буквы (с пробелом), английского - 27. Если считать появление всех букв в тексте одинаковым, то как соотносятся неопределенности, связанные с угадыванием случайно выбранной буквы текста?

20. Опыт имеет два исхода. Докажите, что энтропия такого опыта максимальна, если вероятности исходов будут обе равны 0,5.

21. Докажите, что для двух опытов справедливо соотношение: H(α) + Н_α(β) = Н(β) + Н_β(α).

22. Опыты а и р состоят в последовательном извлечении без возврата двух шаров из ящика, в котором изначально находились п белых шаров и т черных. Найдите, Н(α), H(β), Н_α(β) и Н_β(α).

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

(a) бросок игральной кости;

(b) бросок 2-х монет;

(c) вытаскивание наугад одной игральной карты из 36;

(d) бросок двух игральных костей.

24. Мы отгадываем задуманное кем-то двузначное число.

(a) Какое количество информации требуется для отгадывания всего числа?

(b) Какова оптимальная последовательность вопросов при отгадывании? Каково их минимальное число?

(c) Изменится ли требуемое количество информации, если будем отгадывать не все число сразу, а по очереди: сначала 1-ю цифру числа, затем - 2-ю?

(d) Одинакова ли информация, необходимая для отгадывания 1-ой и 2-ой цифр?

25. Докажите, что I(а,Р) = I(Р,а).

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

27. Возможно ли, чтобы бинарный ответ содержал меньше 1 бита информации?

28. Какое количество информации содержит каждый из ответов на вопрос, если всего их 3 и все они равновероятны? А если равновероятных ответов n?

29. Источник порождает множество шестизнаковых сообщений, каждое из которых содержит 1 знак «*». 2 знака «%» и 3 знака «!». Какое количество информации содержится в каждом (одном) из таких сообщений?

30. С какой буквой русского алфавита «а» или «б» связано больше информации? Найдите эту информацию.

31. Средняя длина слова в русском языке 5,3 буквы, в английском - 4,5. Найдите вероятности появления в соответствующих текстах пробелов. Какое количество информации связано с пробелом в обоих языках?

32. Дайте объяснение тому, что количество информации на знак алфавита выражается нецелым числом.

33. Что такое «шенноновские сообщения»? Почему теория информации имеет дело именно с такими сообщениями?

34. Почему используется «избыточный» язык?

35. Одинакова ли на Ваш взгляд избыточность литературных и деловых текстов? Почему?


Контрольные вопросы и задания для самостоятельной работы по теме: «Компьютер как универсальное средство обработки информации»

1. Для чего при представлении данных в 'компьютере необходима
   их типизация?
   
2. Возможно ли изменение (преобразования) типа одиночной переменной? Приведите примеры.
   
3. Разнесите понятия: «переменная», «значение переменной», «имя переменной», «тип переменной». На каких этапах хранения и обработки данных эти понятия определены?
   
4. Чем обусловлена необходимость структурирования данных?
   
5. Приведите примеры практических задач, при решении которых целесообразно использовать массивы, записи, таблицы.
   
6. Приведите примеры иерархической организации данных.
   
7. Приведите примеры отношений между данными, представленных с помощью неориентированных и ориентированных графов.
   
8. В чем преимущества и недостатки последовательных и связных списков в ОЗУ?
   
9. Разнесите понятия: логическая запись, физическая запись, файл при хранении данных на ВЗУ.
   
10. С какой целью производится форматирование дискового магнитного носителя?
    
11. Как связан тип доступа к данным со способом их хранения?
    
12. Почему на дисковых носителях невозможен произвольный доступ к данным?
    
13. Выдвиньте причины, по которым становится целесообразным объединение блоков в кластеры при использовании Магнитных дисковых носителей.
    
14. Каковы функции FAT в организации размещения файлов на дисковом носителе?
    
15. Какими факторами определяется близость реального канала связи к идеальному?
    
16. Приведите примеры процессов, используемых для передачи информации, и связанных с ними сигналов помимо указанных в тексте.
    
17. Что произойдет при попытке передачи информации со скоростью, превышающей пропускную способность канала связи? Почему?
    
18. Оцените длину звукового файла, если требуется обеспечить телефонное качество звучания в течение 10 с, а на запись одного отсчета отводится 6 бит?
    
19. Человек может осмысленно читать со скоростью 15 знаков в секунду. Оцените пропускную способность зрительного канала в данном виде деятельности.
    
20. Оцените пропускную способность слухового канала радиста, принимающего сигналы азбуки Морзе, если известно, что для распознавания одного элементарного сигнала ему требуется 0,2 с.
    
21. При дискретизации аналогового сообщения число градаций при квантовании равно 64, а частота развертки по времени - 200 Гц. Какой пропускной способности требуется канал связи без шумов для передачи данной информации, если используется равномерное двоичное кодирование?
    
22. Для передачи телеграфных сообщений, представленных с помощью кода Бодо, используется канал без помех с пропускной способностью 1000 бит/с. Сколько знаков первичного алфавита можно передать за 1 с по данному каналу?
    
23. Почему происходит потеря информации при ее передаче по каналу с шумом?
    
24. Определите, на какую долю снижается пропускная способность канала с шумом по сравнению с идеальным каналом при двоичном кодировании, если вероятность появления ошибки передачи составляет: (а) 0,001; (b) 0,02; (с) 0,1; (d) 0,5; (е) 0,98. Поясните полученные результаты.
    
25. С помощью пакета Excel или MathCAD постройте график зависимости отношения CR/C от вероятности появления ошибки передачи р в канале с шумом.
    
26. Почему при передаче информации предпочтение отдается равномерному коду?
    
27. В чем смысловое отличие понятия «избыточность» для идеальных и реальных каналов передачи информации?
    
28. Почему оказывается невыгодной передача длинных кодовых цепочек с одним проверочным битом?
    
29. Будет ли установлен факт ошибки передачи, если эта ошибка содержится в самом контрольном бите? Обоснуйте.
    
30. Какое минимальное количество контрольных бит должно передаваться вместе с 16-ю информационными для обеспечения восстановимости информации, если вероятность искажения составляет: (а) 0,001; (b) 0,02; (с) 0,1; (d) 0,5; (е) 0,98? Какова реальная избыточность сообщения в каждом случае?
    
31. Получено машинное слово, закодированное с использованием кода Хемминга: 100010111100010110011. Устраните ошибку передачи.
    
32. В каких ситуациях код Хемминга не позволит локализовать и исправить ошибку передачи?
    
33. Почему параллельный способ не применяется для передачи информации на большие расстояния? Каким образом, в принципе, можно увеличить дальность параллельной передачи?
    
34. Сколько времени будет выводиться на экран дисплея картинка размером 300x400 пиксель при цветовом режиме 16 бит на цвет, если для обмена используется 32-разрядная шина, а частота тактового генератора составляет 166 МГц?
    
35. Почему при асинхронной последовательной передаче не требуется синхронизации работы источника и приемника?
    
36. Алфавит обитателей планеты Тау-Кита содержит следующий набор жестов: _. Предложите вариант равномерного двоичного кодирования этого алфавита, а также определите избыточность кода при последовательной передаче с одним битом четности.
    

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

^ Контрольные вопросы и задания для самостоятельной работы по теме: «Понятие алгоритма и рекурсивный подход в программировании»

1. С чем связана необходимость точного определения понятия «алгоритм»?
   
2. Можно ли считать алгоритмом: (а) правила правописания; (b) законы физики; (с) математические формулы; (d) статьи уголовного кодекса. Ответы обоснуйте.
   
3. На какие свойства алгоритма окажет влияние выбор того или иного исполнителя для решения одной и той же задачи?
   
4. Можно ли считать исполнителем алгоритма: (а) человека, ведущего запись текста под диктовку, (b) компьютер; (с) компьютерную программу, (d) дрессированное животное. Ответы обоснуйте.
   
5. Доказать, что примитивно-рекурсивными являются функции: (а) ху; (b) x^y; (с) n!
   
6. Каким образом связаны свойства алгоритма и особенности устройства алгоритмической машины?
   
7. Какие действия алгоритмической машины следует считать элементарными?
   
8. Решите следующие задачи, используя алгоритмическую машину Поста; во всех задачах в исходном состоянии обозревается крайняя левая ячейка:
   

a) на ленте находятся два числа N и Q, разделенные одной пустой ячейкой. Напишите программу нахождения суммы N + Q.

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

c) на ленте находятся два числа N и Q (N > Q), разделенные одной пустой ячейкой. Напишите программу нахождения разности N - Q.

d) на ленте ^ N меток. Построить такое же количество меток справа от имеющихся через одну пустую.

е) на ленте находятся два числа N и Q, разделенные одной пустой ячейкой. Напишите программу нахождения произведения NQ.

9. На каком-либо языке программирования высокого уровня разработайте программу эмуляции работы машины Поста.
   
10. Решите следующие задачи, используя алгоритмическую машину Тьюринга; во всех задачах в исходном состоянии обозревается крайняя левая ячейка:
    

a) Сложение двух чисел в унарной системе счисления (например, 1111+11).

b) Дано слово из знаков а и b произвольной длины (например, abb - bab), причем, заранее не известно, какой знак первый (а или b). Необходимо первый знак переместить в конец слова.

c) Добавление 1 к числу в произвольной заданной системе счисления.

d) Перевод целого числа из одной системы счисления в другую.

11. На каком-либо языке программирования высокого уровня разработайте программу эмуляции работы машины Тьюринга.
    

12. Найти значение функции S²(S¹, S¹) (т.е. результат подстановки функции непосредственного следования самой в себя).
    

13. Нормальный алгоритм имеет алфавит А = {а, b, с} и систему подстановок: ас → аа, aab → bc, bc → cab. Найти результат применения алгоритма к исходным словам: (1) cbcbba; (2) abccba; (3) accca.
    

14. На каком-либо языке программирования высокого уровня разработайте программу, обеспечивающую задание и выполнение нормальных алгоритмов Маркова.
    
15. Разработайте нормальные алгоритмы, обеспечивающие:
    

a) выполнение операции вычитания единицы из числа в троичной системе счисления;

b) выполнение операции добавления единицы к числу в двоичной системе счисления;

c) инверсию числа в двоичном алфавите;

d) преобразование док → тоска. Применить его к словам ток, дот.

16. Опишите формальную грамматику, порождающую множество целых двоичных чисел.
    

17. Что определяет следующая нотация Бекуса-Наура: <формула>::=<цифра>|{<формула><знак><формула>)
    

<знак>::= +| - | *

<цифра>::= 0|1|2|3|4|5|6|7|8|9

18. На каком-либо языке программирования напишите программу, функционирующую в соответствии с нотацией, приведенной в предыдущем
    задании.
    
19. С помощью синтаксических диаграмм опишите следующие конструкции языка PASCAL:
    

a) оператор цикла с предусловием ^ WHILE ... DO;

b) составной оператор;

c) оператор цикла с параметром FOR ... DO,

d) оператор выбора CASE.

20. Можно ли считать формальным исполнителем алгоритма следующие устройства:
    

a) кодовый замок;

b) графический редактор;

c) телефон с памятью для записи номеров;

d) принтер?

21. Постройте блок-схемы следующих структурных алгоритмов:
    

а) вычисление n! (ввод n);

b) суммирование цифр целого числа при произвольной его разрядности (ввод - целое число);

c) перевод целого числа в двоичную систему счисления (ввод - целое число);

d) вычисление значения функции sin(x) с заданной точностью е путем суммирования ее разложения в ряд Тейлора (ввод – аргумент х, точность вычисления е).

22. Запишите с помощью псевдокода алгоритмы, приведенные в задании 21.
    
23. Напишите программы на каком-либо языке программирования для алгоритмов задания 21.
    

24. В чем смысл и значение структурной теоремы для практики разработки алгоритмов? Возможно ли существование неструктурных алгоритмов? Если «да» - приведите примеры.