close

Вход

Забыли?

вход по аккаунту

файл - Основные образовательные программы

код для вставкиСкачать
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
«Глазовский государственный педагогический институт имени В.Г. Короленко»
ПРИНЯТО
на заседании Ученого совета института
УТВЕРЖДАЮ
Ректор ГГПИ
Протокол №___
______________ А.А. Мирошниченко
от «___»___________2011 г.
«____»______________2011 г.
КАФЕДРА ИНФОРМАТИКИ, ТЕОРИИ
И МЕТОДИКИ ОБУЧЕНИЯ ИНФОРМАТИКЕ
УЧЕБНАЯ ПРОГРАММА
ПО ДИСЦИПЛИНЕ
«ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ИНФОРМАТИКИ»
НАПРАВЛЕНИЕ ПОДГОТОВКИ:
050100.62 – ПЕДАГОГИЧЕСКОЕ ОБРАЗОВАНИЕ
ПРОФИЛЬ «ИНФОРМАТИКА»
Глазов 2011
1. Пояснительная записка
1.1. Цель, задачи и проектируемые результаты изучения дисциплины.
Цель дисциплины:
Освоение теоретического фундамента и математических методов для
построения и изучения моделей обработки, передачи и использования
информации.
Задачи дисциплины:
- формирование основных понятий теоретической информатики;
- получение знаний об основных видах информационных моделей и
научных подходах, изучающих их свойства;
- освоение математических методов, которые при этом используются.
Проектируемые результаты освоения дисциплины
В результате изучения дисциплины студент должен:
Знать: современные методики и технологии хранения, обработки и передачи
информации, в том числе и построенные на базе современных программных продуктов,
для обеспечения качества учебно-воспитательного процесса на конкретной
образовательной ступени конкретного образовательного учреждения.
Уметь: готов применять современные методики и технологии, в том числе и
информационные, для обеспечения качества учебно-воспитательного процесса на
конкретной образовательной ступени конкретного образовательного учреждения.
Владеть: владеет культурой мышления, способен к обобщению, анализу, восприятию
информации, постановке цели и выбору путей её достижения;
Формируемые компетенции: ОК-1, ОПК-3, ПК-2.
Студент:
ОК-1: владеет культурой мышления, способен к обобщению, анализу, восприятию
информации, постановке цели и выбору путей её достижения;
ОПК-3: владеет основами речевой профессиональной культуры;
ПК-2: готов применять современные методики и технологии, в том числе и
информационные, для обеспечения качества учебно-воспитательного процесса на
конкретной образовательной ступени конкретного образовательного учреждения.
Проектируемые дисциплинарные результаты сформированности компетенций
Студент:
Результат ОК-1: владеет знаниями, умениями и навыками, соответствующими
содержанию дисциплины «Теоретические основы информатики», формирующие культуру
мышления, способность к обобщению, анализу, восприятию информации, постановке
цели и выбору путей её достижения;
Результат ОПК-3: владеет терминологическим аппаратом дисциплины «Теоретические
основы информатики», определяющим основы речевой профессиональной культуры
педагога;
Результат ПК-2: владеет знаниями, умениями и навыками, соответствующими
содержанию дисциплины «Теоретические основы информатики», и готов применять их в
современных методиках и технологиях, в том числе и информационных, для обеспечения
качества учебно-воспитательного процесса на конкретной образовательной ступени
конкретного образовательного учреждения.
1.2. Объем дисциплины и виды учебной работы
Вид учебной работы по семестрам
Зачетные
единицы
4
Общая трудоемкость
Часы
144
Семестр 3
Трудоемкость
Аудиторные занятия (всего)
В том числе:
Лекции
Лабораторные работы
Практические занятия / Семинары
КСР
Другие виды аудиторной работы
Самостоятельная работа (всего)
В том числе:
Работа с рабочими тетрадями
Подготовка к коллоквиуму
Подготовка к «круглым столам»
Работа над презентационными
проектами по курсу
Вид промежуточной аттестации – экзамен
3
1,5
108
54
20
24
10
1,5
54
14
14
14
12
1
36
1.3. Требования к уровню освоения содержания дисциплины
а) Компетенции обучающегося, формируемые в результате освоения
дисциплины (в соответствие с номенклатурой компетенций пункта V
ФГОС ВПО по направлению подготовки);
Индекс
компетенции
по ФГОС
Содержание компетенции
Требования к уровням освоения
Знает
(З-1, З-2, З-3)
Умеет
(У-1, У-2, У-3)
Владеет
(В-1, В-2, В-3)
ОК-1
владеет культурой мышления,
способен к обобщению, анализу,
восприятию информации,
постановке цели и выбору путей её
достижения;
ОПК-3
владеет основами речевой
профессиональной культуры;
ПК-2
готов
применять
современные
методики и технологии, в том числе
и
информационные,
для
обеспечения
качества
учебновоспитательного
процесса
на
конкретной
образовательной
ступени
конкретного
образовательного учреждения.
знать
представление и
обработку чисел
в компьютере.
знать первую
теорему
Шеннона в
различных
интерпретациях
уметь составлять
математические
модели
вычисления
значений
функций,
решение
элементарных
уравнений и
неравенств;
уметь
использовать
формулы
Шеннона и
Хартли
владеть основами
теории
алгоритмов
- владеть
вопросами
обеспечения
надежности
передачи и
хранения
информации;
б) В результате освоения дисциплины обучающийся должен:
- уметь составлять математические модели вычисления значений
функций, решение элементарных уравнений и неравенств;
- иметь навыки вычислений по рекуррентным соотношениям;
- уметь подсчитывать вероятности элементарных событий;
- иметь представление об условной вероятности элементарного
события;
- иметь представление об устройстве компьютера.
- знать представление и обработку чисел в компьютере.
- иметь четкое представление о предмете и структуре курса
«Теоретические основы информатики»;
- владеть основами теории алгоритмов;
- иметь представление о машинах Поста и Тьюринга;
- знать основные свойства рекурсивных функций;
- знать методы оценки и виды информации;
- владеть понятием энтропии;
- иметь представление о статистических и объемных подходах к
определению количества информации;
- уметь использовать формулы Шеннона и Хартли;
- знать первую теорему Шеннона в различных интерпретациях;
- иметь представление о префисных кодах;
- уметь использовать коды Шеннона – Фано и Хаффмана для
конкретной задачи;
- иметь представление об особенностях различных методов
кодирования;
- знать особенности реализации вещественной компьютерной
арифметики;
- иметь представление о кодировании текстовой и графической
информации;
- знать особенности квантования цвета и цветовые модели RGB и
СМYК;
- знать схему передачи информации в линиях связи;
- владеть вопросами обеспечения надежности передачи и хранения
информации;
- иметь представление о структурных данных и особенностях
устройств хранения информации в ОЗУ и на внешних носителях;
- уметь производить вычисления по логическим формулам;
- уметь решать логические задачи;
- знать булевы функции и канонические формы логических формул;
Уровни освоения компетенций.
Ступеней уровней освоения компетенции − три.
Первый уровень пороговый. Он формируется из компоненты знать.
Оценивается как удовлетворительная оценка.
Второй уровень, продвинутый, он формируется из требований к
компоненте уметь. Оценивается «хорошо».
Третий уровень – высокий. Он формируется из компоненты иметь
навыки. Оценивается «отлично».
2. Содержание дисциплины по разделам (модулям)
Предполагается изучение дисциплины в рамках десяти разделов,
разделенных на три модуля: элементы теории информации, компьютер как
универсальное средство обработки информации, понятие алгоритма и
рекурсивный подход в программировании.
Таблица 2.
Содержание дисциплины по разделам
Модуль 1. Элементы теории информации
Раздел 1. Понятие информации
Содержание раздела: введение в предмет, место информатики в системе наук, социальные
основы информатики. Основы кибернетики. САУ и АСУ как системы реализации
кибернетической модели управления. Понятие модели и абстракции, использование метода
моделирования как основного метода исследования в современной информатике.
Раздел 2. Измерение информации
Содержание раздела: Единицы измерения информации, алфавитный подход к измерению
информации, содержательный подход к измерению информации. Более крупные единицы
измерения информации
Модуль 2. Компьютер как универсальное средство обработки информации
Раздел 3. Системы счисления
Содержание раздела: Позиционные и непозиционные системы счисления, вес цифры в числе,
реализация перевода из одной системы счисления в другую из 10-К, из К-10, из K-N.
Использование двоичной системы счисления для представления информации.
Раздел 4. Представление чисел в памяти компьютера
Содержание раздела: Использование обратного, прямого и дополнительного кода,
представление целых и вещественных чисел в памяти компьютера. Использование
дополнительного кода для реализации операции вычитания
Раздел 5. Кодирование информации
Содержание раздела: Представление текстовой, графической и звуковой информации.
Теоремы кодирования Шеннона. Условия Шеннона-Фано. Префиксное кодирование.
Модуль 3. Понятие алгоритма и рекурсивный подход в программировании
Раздел 6. Понятие алгоритма
Содержание раздела: Алгоритм, исполнитель, данные, свойства алгоритма. Представление
алгоритмов.
Раздел 7. Основные алгоритмические конструкции
Содержание раздела: Линейная конструкция, конструкция ветвления, конструкция цикла:
цикл с предусловием, цикл с постусловием, цикл с параметром.
Раздел 8. Формальные алгоритмы
Содержание раздела: Машина Тьюринга, Машина Поста, Алгорифмы Маркова.
Раздел 9. Рекурсивные алгоритмы
Содержание раздела: Понятие рекурсии. Комбинаторные алгоритмы, алгоритмы перебора,
алгоритмы на графах.
3. Методические рекомендации для преподавателя
Отличительной особенностью данного УМК является построение
содержания предмета по принципу укрупнения тематической единицы с
отведением на ее изучение большего количества аудиторных часов. Такой
подход позволяет каждому преподавателю, работающему по данной
программе, самостоятельно перераспределять время на изучение каждого
раздела темы и отработку умений на лабораторно-практических занятиях.
Лекционные занятия в содержательном аспекте должны ориентировать
студентов на восприятие научных основ предмета информатики, в
методическом - строится по принципу алгоритмов действий, что позволит
обучаемым на практических и самостоятельных занятиях точно выполнять
последовательность действий при работе с компьютерной техникой и
программным обеспечением. Поскольку многие студенты до поступления в
профессиональные педагогические учебные заведения не сталкивались с
современными
аппаратно-программными
средствами,
необходимо
теоретические формы обучения проводить с наглядной демонстрацией тех
компонентов, которые являются предметом изучения. Это повысит
эффективность процесса восприятия и осмысления учебной информации.
При организации лабораторно-практических занятий в первую очередь
следует обратить внимание на правила техники безопасности и выполнить
необходимые документальные формальности. Для надежности сохранения
информации, создаваемой студентами, рекомендуется закрепить за каждым
из них персональный компьютер в учебной лаборатории и на жестком диске
в папке Мои документы завести персональную папку с индивидуальным
именем. В дальнейшем требовать от лаборантов следить за сохранением
такого подхода и при самостоятельной работе.
На занятиях самостоятельной работы необходимо ставить перед
студентами такие задания, выполнение которых позволит лучше освоить те
умения работы с программными средствами, уделить внимание которым
невозможно в силу ограниченного количества аудиторных занятий, но
необходимость в них диктуется условиями предстоящей профессиональной
деятельности.
Для эффективной организации аттестации текущей успеваемости
рекомендуется использовать компьютерный вариант прилагаемых тестовых
заданий. Это не только снизить загруженность преподавателя, но и позволит
студентам практически осваивать возможности применения современных
информационных технологий в образовательном процессе.
4. Общие методические рекомендации для студентов
При изучении курса теоретические основы информатики студентам
необходимо в точности следовать указаниям преподавателя, поскольку им
придется работать с дорогостоящим оборудованием и программным
продуктом. Быть предельно внимательными при работе с программными
папками и файлами, не перемещать их и не удалять, так как это может
вызвать сбои в работе операционной системы и системных приложений. В
этом случае без рабочего места останется не только данный студент, но и
учащиеся других групп.
Контрольные вопросы и задания для самостоятельной работы по
модулю: «Элементы теории информации»
Приведите примеры терминов, имеющих несколько трактовок в
различных науках, технике, быту.
Приведите примеры процессов, используемых для передачи
информации, и связанных с ними сигналов, кроме указанных в лекциях.
Приведите примеры неоднозначного и однозначного соответствия
между сообщением и содержащейся в нем информацией.
Почему хранение информации нельзя считать информационным
процессом?
В чем состоит различие понятий «приемник сообщения» и «приемник
информации»?
Органы чувств человека ориентированы на восприятие аналоговой
информации. Означает ли это, что человек не может воспринимать
информацию дискретную?
Приведите примеры знаков-символов. Могут ли символы образовывать
алфавит?
В шестнадцатеричной системе счисления используются цифры А, В, С,
D, Е, F. Следует ли эти знаки считать символами?
В тексте данной главы разграничиваются понятия «знак», «буква»,
«символ». Как соотносится с ними понятие «цифра»?
В чем состоит смысл и значение теоремы отсчетов?
Какое количество отсчетов за 1 с необходимо производить цифровому
звукозаписывающему устройству, если требуется обеспечить качество
записи (а) телефона; (б) лазерного диска.
Как следует понимать термины «оцифровка изображения» и
«оцифровка звука»? Какими устройствами производятся данные операции?
Приведите примеры преобразований типа D1 → D2, при которых
информация, содержащаяся в исходном сообщении, может не сохраняться.
Почему для представления дискретных сообщений в качестве базового
выбирается двоичный алфавит?
Почему компьютер является универсальным устройством по обработке
информации?
В чем состоит и как проявляется несимметричность непрерывной и
дискретной форм представления информации?
Почему в определении энтропии как меры неопределенности выбрана
логарифмическая зависимость между Н и n? Почему выбран log2 ?
Какова энтропия следующих опытов:
a) бросок монеты;
b) бросок игральной кости;
c) вытаскивание наугад одной игральной карты из 36;
d) бросок двух игральных костей.
Алфавит русского языка содержит 34 буквы (с пробелом), английского
- 27. Если считать появление всех букв в тексте одинаковым, то как
соотносятся неопределенности, связанные с угадыванием случайно
выбранной буквы текста?
Опыт имеет два исхода. Докажите, что энтропия такого опыта
максимальна, если вероятности исходов будут обе равны 0,5.
Докажите, что для двух опытов справедливо соотношение: H(α) + Нα(β)
= Н(β) + Нβ(α).
Опыты а и р состоят в последовательном извлечении без возврата двух
шаров из ящика, в котором изначально находились п белых шаров и т
черных. Найдите, Н(α), H(β), Нα(β) и Нβ(α).
Какое количество информации связано с исходом следующих опытов:
a) бросок игральной кости;
b) бросок 2-х монет;
c) вытаскивание наугад одной игральной карты из 36;
d) бросок двух игральных костей.
Вопрос имеет два варианта ответа. Возможно ли, чтобы с каждым из
ответов была связано различное количество информации?
Возможно ли, чтобы бинарный ответ содержал меньше 1 бита
информации?
Какое количество информации содержит каждый из ответов на вопрос,
если всего их 3 и все они равновероятны? А если равновероятных ответов n?
Источник порождает множество шестизнаковых сообщений, каждое из
которых содержит 1 знак «*». 2 знака «%» и 3 знака «!». Какое количество
информации содержится в каждом (одном) из таких сообщений?
С какой буквой русского алфавита «а» или «б» связано больше
информации? Найдите эту информацию.
Средняя длина слова в русском языке 5,3 буквы, в английском - 4,5.
Найдите вероятности появления в соответствующих текстах пробелов. Какое
количество информации связано с пробелом в обоих языках?
Дайте объяснение тому, что количество информации на знак алфавита
выражается нецелым числом.
Что такое «шенноновские сообщения»? Почему теория информации
имеет дело именно с такими сообщениями?
Почему используется «избыточный» язык?
Одинакова ли на Ваш взгляд избыточность литературных и деловых
текстов? Почему?
Контрольные вопросы и задания для самостоятельной работы по теме:
«Компьютер как универсальное средство обработки информации»
Для чего при представлении данных в 'компьютере необходима
их типизация?
Возможно ли изменение (преобразования) типа одиночной
переменной? Приведите примеры.
Разнесите понятия: «переменная», «значение переменной», «имя
переменной», «тип переменной». На каких этапах хранения и обработки
данных эти понятия определены?
Чем обусловлена необходимость структурирования данных?
Приведите примеры практических задач, при решении которых
целесообразно использовать массивы, записи, таблицы.
Приведите примеры иерархической организации данных.
Приведите примеры отношений между данными, представленных с
помощью неориентированных и ориентированных графов.
В чем преимущества и недостатки последовательных и связных
списков в ОЗУ?
Разнесите понятия: логическая запись, физическая запись, файл при
хранении данных на ВЗУ.
С какой целью производится форматирование дискового магнитного
носителя?
Как связан тип доступа к данным со способом их хранения?
Почему на дисковых носителях невозможен произвольный доступ к
данным?
Выдвиньте причины, по которым становится целесообразным
объединение блоков в кластеры при использовании Магнитных дисковых
носителей.
Каковы функции FAT в организации размещения файлов на дисковом
носителе?
Какими факторами определяется близость реального канала связи к
идеальному?
Приведите примеры процессов, используемых для передачи
информации, и связанных с ними сигналов помимо указанных в тексте.
Что произойдет при попытке передачи информации со скоростью,
превышающей пропускную способность канала связи? Почему?
Оцените длину звукового файла, если требуется обеспечить
телефонное качество звучания в течение 10 с, а на запись одного отсчета
отводится 6 бит?
Человек может осмысленно читать со скоростью 15 знаков в секунду.
Оцените пропускную способность зрительного канала в данном виде
деятельности.
Оцените пропускную способность слухового канала радиста,
принимающего сигналы азбуки Морзе, если известно, что для распознавания
одного элементарного сигнала ему требуется 0,2 с.
При дискретизации аналогового сообщения число градаций при
квантовании равно 64, а частота развертки по времени - 200 Гц. Какой
пропускной способности требуется канал связи без шумов для передачи
данной информации, если используется равномерное двоичное кодирование?
Для передачи телеграфных сообщений, представленных с помощью
кода Бодо, используется канал без помех с пропускной способностью 1000
бит/с. Сколько знаков первичного алфавита можно передать за 1 с по
данному каналу?
Почему происходит потеря информации при ее передаче по каналу с
шумом?
Определите, на какую долю снижается пропускная способность канала
с шумом по сравнению с идеальным каналом при двоичном кодировании,
если вероятность появления ошибки передачи составляет: (а) 0,001; (b) 0,02;
(с) 0,1; (d) 0,5; (е) 0,98. Поясните полученные результаты.
С помощью пакета Excel или MathCAD постройте график зависимости
отношения CR/C от вероятности появления ошибки передачи р в канале с
шумом.
Почему при передаче информации предпочтение отдается
равномерному коду?
В чем смысловое отличие понятия «избыточность» для идеальных и
реальных каналов передачи информации?
Почему оказывается невыгодной передача длинных кодовых цепочек с
одним проверочным битом?
Будет ли установлен факт ошибки передачи, если эта ошибка
содержится в самом контрольном бите? Обоснуйте.
Какое минимальное количество контрольных бит должно передаваться
вместе с 16-ю информационными для обеспечения восстановимости
информации, если вероятность искажения составляет: (а) 0,001; (b) 0,02; (с)
0,1; (d) 0,5; (е) 0,98? Какова реальная избыточность сообщения в каждом
случае?
Получено машинное слово, закодированное с использованием кода
Хемминга: 100010111100010110011. Устраните ошибку передачи.
В каких ситуациях код Хемминга не позволит локализовать и
исправить ошибку передачи?
Почему параллельный способ не применяется для передачи
информации на большие расстояния? Каким образом, в принципе, можно
увеличить дальность параллельной передачи?
Сколько времени будет выводиться на экран дисплея картинка
размером 300x400 пиксель при цветовом режиме 16 бит на цвет, если для
обмена используется 32-разрядная шина, а частота тактового генератора
составляет 166 МГц?
Почему при асинхронной последовательной передаче не требуется
синхронизации работы источника и приемника?
Алфавит обитателей планеты Тау-Кита содержит следующий набор
жестов:
. Предложите вариант равномерного
двоичного кодирования этого алфавита, а также определите избыточность
кода при последовательной передаче с одним битом четности.
Почему по телефонным линиям связи невозможно непосредственно
(без преобразования) передавать компьютерные сигналы?
Каковы функции модема при связи компьютеров по телефонным
линиям?
Оцените, сколько времени будет передаваться текст объемом в 1
страницу в кодировке ASC по модемной линии, если несущая частота
составляет 1200 Гц и передача производится асинхронно с одним стоповым
битом?
Контрольные вопросы и задания для самостоятельной работы по теме:
«Понятие алгоритма и рекурсивный подход в программировании»
С чем связана необходимость точного определения понятия
«алгоритм»?
Можно ли считать алгоритмом: (а) правила правописания; (b) законы
физики; (с) математические формулы; (d) статьи уголовного кодекса. Ответы
обоснуйте.
На какие свойства алгоритма окажет влияние выбор того или иного
исполнителя для решения одной и той же задачи?
Можно ли считать исполнителем алгоритма: (а) человека, ведущего
запись текста под диктовку, (b) компьютер; (с) компьютерную программу, (d)
дрессированное животное. Ответы обоснуйте.
Доказать, что примитивно-рекурсивными являются функции: (а) ху; (b)
y
x ; (с) n!
Каким образом связаны свойства алгоритма и особенности устройства
алгоритмической машины?
Какие действия алгоритмической машины следует считать
элементарными?
Решите следующие задачи, используя алгоритмическую машину Поста;
во всех задачах в исходном состоянии обозревается крайняя левая ячейка:
a) на ленте находятся два числа N и Q, разделенные одной пустой
ячейкой. Напишите программу нахождения суммы N + Q.
b) решите предыдущую задачу при условии, что исходные числа
разделены произвольным числом пустых ячеек.
c) на ленте находятся два числа N и Q (N > Q), разделенные одной
пустой ячейкой. Напишите программу нахождения разности N - Q.
d) на ленте N меток. Построить такое же количество меток справа от
имеющихся через одну пустую.
е) на ленте находятся два числа N и Q, разделенные одной пустой
ячейкой. Напишите программу нахождения произведения NQ.
На каком-либо языке программирования высокого уровня разработайте
программу эмуляции работы машины Поста.
Решите следующие задачи, используя алгоритмическую машину
Тьюринга; во всех задачах в исходном состоянии обозревается крайняя левая
ячейка:
a) Сложение двух чисел в унарной системе счисления (например,
1111+11).
b) Дано слово из знаков а и b произвольной длины (например, abb bab), причем, заранее не известно, какой знак первый (а или b). Необходимо
первый знак переместить в конец слова.
c) Добавление 1 к числу в произвольной заданной системе счисления.
d) Перевод целого числа из одной системы счисления в другую.
На каком-либо языке программирования высокого уровня разработайте
программу эмуляции работы машины Тьюринга.
Найти значение функции S2(S1, S1) (т.е. результат подстановки функции
непосредственного следования самой в себя).
Нормальный алгоритм имеет алфавит А = {а, b, с} и систему
подстановок: ас → аа, aab → bc, bc → cab. Найти результат применения
алгоритма к исходным словам: (1) cbcbba; (2) abccba; (3) accca.
На каком-либо языке программирования высокого уровня разработайте
программу, обеспечивающую задание и выполнение нормальных алгоритмов
Маркова.
Разработайте нормальные алгоритмы, обеспечивающие:
a) выполнение операции вычитания единицы из числа в троичной
системе счисления;
b) выполнение операции добавления единицы к числу в двоичной
системе счисления;
c) инверсию числа в двоичном алфавите;
d) преобразование док → тоска. Применить его к словам ток, дот.
Опишите формальную грамматику, порождающую множество целых
двоичных чисел.
Что
определяет
следующая
нотация
Бекуса-Наура:
<формула>::=<цифра>|{<формула><знак><формула>)
<знак>::= +| - | *
<цифра>::= 0|1|2|3|4|5|6|7|8|9
На каком-либо языке программирования напишите программу,
функционирующую в соответствии с нотацией, приведенной в предыдущем
задании.
С помощью синтаксических диаграмм опишите следующие
конструкции языка PASCAL:
a) оператор цикла с предусловием WHILE ... DO;
b) составной оператор;
c) оператор цикла с параметром FOR ... DO,
d) оператор выбора CASE.
Можно ли считать формальным исполнителем алгоритма следующие
устройства:
a) кодовый замок;
b) графический редактор;
c) телефон с памятью для записи номеров;
d) принтер?
Постройте блок-схемы следующих структурных алгоритмов:
а) вычисление n! (ввод n);
b) суммирование цифр целого числа при произвольной его разрядности
(ввод - целое число);
c) перевод целого числа в двоичную систему счисления (ввод - целое
число);
d) вычисление значения функции sin(x) с заданной точностью е путем
суммирования ее разложения в ряд Тейлора (ввод – аргумент х, точность
вычисления е).
В чем смысл и значение структурной теоремы для практики разработки
алгоритмов? Возможно ли существование неструктурных алгоритмов? Если
«да» - приведите примеры.
ТЕСТ для проверки уровня знаний по дисциплине
Тестовые задания направлены на выявление уровня теоретической
подготовки студентов по дисциплине «Теоретические основы информатики».
Каждое тестовое задание содержит по три варианта ответов, из которых
необходимо выбрать единственно верный. Каждый правильный ответ
оценивается в один бал, соответственно, неверный - даёт нуль баллов. После
прохождения всего теста подсчитывается общее число верных ответов.
1.
Информация - это
a)
одно из наиболее общих понятий науки, обозначающее
некоторые сведения, совокупность каких-либо данных, знаний и т.п.
b)
область знания, изучающая способы передачи опыта.
c)
характеристика способов взаимодействия отдельных элементов
компьютера.
2. Современные информационные технологии - это
a)
компьютер и его периферийные устройства.
машинизированные способы обработки, хранения, передачи и
использования информации в виде знаний.
c)
локальные и глобальные информационные сети.
3. Информатика - это
a)
наука о компьютерных системах и информационных сетях.
b)
наука о совокупности процессов получения, передачи, обработки,
хранения, представления и распространения информации.
c)
область знания о современных информационных технологиях
4. Персональный компьютер - это
а) устройство преобразования информации посредством выполнения
управляемой программой последовательности операций.
б) устройство для решения математических задач и применения в
обучении.
в) техническое средство, выполняющее строго заданный алгоритм
последовательности действий.
5. К устройствам ввода информации относятся:
а) системный блок, мышь, клавиатура, графопостроитель, микрофон.
б) клавиатура, CD ROM, мышь, стриммер, монитор.
в) мышь, шар, сенсорный экран, микрофон.
6. Мультимедиа - это
а) интерактивная технология, обеспечивающая работу с
неподвижными изображениями, видеоизображением, анимацией, текстом и
звуковым рядом.
б) технические средства, позволяющие вводить и выводить
статические и динамические графические образы.
в) программы операционной системы Windows, обеспечивающие
прослушивание и просмотр звуковых и видео файлов.
7. Алгоритм – это
a)
метод решения задачи, записанный по определённым правилам,
обеспечивающим однозначность его понимания и механического исполнения.
b)
способ решения задач, предусматривающий логическое
достижение желаемого результата.
c)
последовательное выполнение операций, представляющие
заданные действия в математической науке.
b)
8. Каким из перечисленных требований алгоритм не должен
удовлетворять:
a)
корректность и однозначность;
b)
общность и многообразие;
c)
наличие ввода исходных данных и эффективность.
9. В графическом алгоритме циклическое действие обозначается
a)
прямоугольником.
b)
ромбом.
c)
овалом.
10. Функция называется эффективно вычислимой, если
существует численный алгоритм, позволяющий вычислять
значения на компьютере.
b)
существует алгоритм, позволяющий вычислять ее значения.
c)
существует алгоритм минимизации поиска.
11. «Проблема распознавания выводимости алгоритмически не
разрешима» - так звучит:
a) теорема Черча;
b) постулат Маркова;
c) тезис Тьюринга.
12. Всякий алгоритм может быть задан посредством тьюринговой
функциональной схемы и реализован в соответствующей Машине Тьюринга.
– это
a)
теорема Тьюринга.
b)
алгоритм Тьюринга.
c)
тезис Тьюринга.
13. Процесс перестановки элементов массива в определенном порядке
— это
a)
сортировка;
b)
перестановка;
c)
поиск.
14. Множество — это
a)
набор однотипных элементов базового типа, каким-то образом
связанных друг с другом.
b)
последовательность символов, принадлежащих конечному
множеству символов, или алфавиту.
c)
типизированный файл.
15. Непустое конечное множество элементов, один из которых
называется корнем, а остальные делятся на несколько непересекающихся
подмножеств, каждое из которых является деревом - это
a) стек;
b) очередь;
c) дерево.
16. Для графа G = (V,E) такой граф H = (W,U), у которого множество
вершин W есть подмножество вершин графа G, W⊆ V, множество ребер/дуг U
есть подмножество множества ребер/дуг E,U ⊆ E, причем если (x, y)∈ E и x,
y∈W, то обязательно (x, y)∈ U - это
a)
подграф;
b)
часть дерева;
c)
матроид.
17. Дерево(Tree) – это
a)
граф Эйлера;
b)
частичный граф;
c)
связный граф без циклов.
18. Граф, вершинам которого приписаны метки, например номера 1, 2,
... , n или символы из какого-нибудь алфавита.
a)
частичный граф;
контур;
помеченный граф.
19 Математическая модель – это
а) формализованное описание системы с помощью некоторого
абстрактного языка.
б) математическое представление свойств системы через набор
математических символов.
в) описание физического объекта с помощью математического языка.
20. Моделирование – это
а) наделение объекта или явления специфическими свойствами,
позволяющими в дальнейшем исследовать эти свойства как свойства
модели.
б) придание модели различных динамических форм с целью изучения ее
свойств.
в) замещение исследуемого объекта его условным образом или другим
объектом и изучение свойств оригинала путем исследования свойств
модели.
21. Компьютерное моделирование – это
а) описание математической модели на языке программирования
высокого уровня.
б) математическое моделирование с использованием средств
вычислительной техники.
в) использование современных информационных технологий в процессе
математического моделирования.
22. Алгоритм комбинаторной оптимизации отыскания подмножества
максимального веса заданного множества, элементам которого приписаны
неотрицательные веса.
a)
сортировочный алгоритм;
b)
жадный алгоритм;
c)
алгоритм поиска.
23. Поиск по ключу элемента в информационном множестве.
a) перечисление;
b) ассоциативный поиск;
c) связность.
24. Множество, элементам которого ставятся во взаимно однозначное
соответствие так называемые ключи - информационные элементы без
внутренней структуры, называется именованным множеством (И.м.). Замена
прямого поиска по элементу поиском элемента по ключу, имеющему более
простую природу и связанному определенными отношениями с другими
ключами, позволяет сделать поиск (и другие операции над множеством)
более эффективным. Другая причина введения такого понятия как ключ
состоит в том, что содержательная трактовка элементов И.м. (в силу сложной
их природы) может зависеть от характера работы с И.м., и иногда возникает
необходимость в зависимости от трактовки сопоставлять элементам
a)
b)
c)
различные системы ключей. Как правило, ключи в И.м. вводятся таким
образом, что имеется простая процедура порождения ключа по
информационному элементу (например, в качестве ключей могут
рассматриваться некоторые части информационных элементов). Что
представляет собой множество ключей
a)
геометрический граф;
b)
подмножество;
c)
информационное множество.
Ключ к тесту
Правильные ответы: 1-a, 2-b, 3-b, 4-а, 5-в, 6-а, 7-а, 8-b, 9-b, 10-b, 11-a,
12-с, 13-a, 14-a, 15-с, 16-а, 17-b, 18-c, 19-а, 20-в, 21-б, 22-b, 23-b, 24-с.
Шкала оценки:
«отлично» - за 90-100% правильных ответов;
«хорошо» - за 75-90% правильных ответов;
«удовлетворительно» - за 50-75% правильных ответов;
«неудовлетворительно» - если < 50% правильных ответов.
5. Лабораторные работы
5.1. Лабораторная работа №1. Введение в предмет
Найти несколько определений в различных отраслях науки понятия
«информация».
Рассмотрите и опишите все информационные барьеры в развитии
общества и заполните таблицу.
Таблица 3.
Результаты выполнения лабораторной работы «Введение в предмет»
Информационный
барьер
Хранение
информации
Передача
информации
Скорость
передачи
информации
Обработка
информации
Носители
информации
Противоречие
Стоит заметить, что само выделение первобытных людей из мира
животных и формирование начальных обществ связано с их коммуникацией
в ходе решения совместных задач – охота, борьба со стихиями и пр., т.е. с
информационным обменом. В отношении коммуникации ситуация нисколько
не изменилась за прошедшие с тех пор тысячелетия – и сейчас любые
совместные действия, решение любой задачи, в котором участвует более
одного человека, требуют обмена информацией, представленной в понятной
всем участникам форме. Для характеристики информационного обеспечения
исторических эпох выделим несколько параметров:
•
организация передачи информации в пространстве, т.е.
распространение информации с целью обеспечения доступа к ней людей
(потребителей), удаленных друг от друга, в относительно небольшой
временной интервал;
•
организация передачи информации во времени, т.е. накопление и
хранение информации в интересах будущих потребителей;
•
организация обработки информации, т.е. преобразование
имеющейся информации с целью ее использования для решения задач
практики – управления, обучения, создания новой информации (наука и
искусство) и пр.
По
ходу
истории
человечества
улучшение
показателей,
характеризующих уровень развития перечисленных процессов, происходило
неравномерно, что повлекло возникновение и затем преодоление нескольких
информационных барьеров. Информационные барьеры образовывались в
результате противоречий между информационными запросами общества и
техническими возможностями их обеспечения. Эти барьеры оказывались
препятствием на пути прогресса общества, и потому, как и в случае барьеров
материальных или энергетических, человечество всегда находило способ их
преодоления.
Опишите историю возникновения информатики как самостоятельной
научной дисциплины.
5.2. Лабораторная работа №2. «Энтропия как мера неопределенности»
1. Какова энтропия следующих опытов:
• бросок монеты;
• бросок игральной кости;
• вытаскивание наугад одной игральной карты из 36;
• бросок двух игральных костей.
2. На соревнованиях по стрельбе на мишенях нанесены области с
очками 0-2-6-10. Стрелки A и B сделали по 100 выстрелов и показали
следующие результаты:
Очки
0
2
6
10
Число попаданий A
5
20
65
10
Число попаданий B
10
10
60
20
Определите, с результатом выстрела, которого из стрелков – A или B –
связана большая неопределенность.
3. В ящике имеются 2 белых шара и 4 черных шара. Из ящика
извлекают последовательно два шара, причем шар возвращают в ящик
обратно. Найти энтропию, связанную с первым и вторым извлечениями, а
также энтропию обоих извлечений.
4. Имеются две урны, содержащие по 20 шаров – 10 белых, 5 черных, 5
красных в первой и 8 белых, 8 черных и 4 красных во второй. Из каждой
урны вытаскивают по одному шару. Исход какого из этих двух опытов
следует считать более неопределенным?
5. Пусть из многолетних наблюдений за погодой известно, что для
определённого пункта вероятность того, что 15 июня будет идти дождь,
равна 0.4, а вероятность того, что в указанный день дождя не будет, равна
0,6. Пусть далее для этого же пункта вероятность того, что 15 ноября будет
идти дождь, равна 0,65, вероятность того, что 15 ноября будет идти снег,
равна 0,15 и вероятность того, что 15 ноября вовсе не будет осадков, равна
0,2. Если из всех характеристик погоды интересоваться лишь вопросом о
наличии и о характере осадков, то в какой из двух перечисленных дней
погоду в рассматриваемом пункте следует считать более определённой?
6. Имеется три урны, содержащие белые и черные шары, причем, в
первой урне 2 белых шара и 4 черных шара, во второй – 3 белых и 3 черных,
в третьей – 4 белых и 2 черных. Из одной из урн (неизвестно из какой) наугад
вынут шар. Какова энтропия того, что вынутый шар окажется белым, причем
из первой урны?
7. Алфавит русского языка содержит 34 буквы (с пробелом),
английского – 27. Если считать появление всех букв в тексте одинаковым, то,
как соотносятся неопределенности, связанные с угадыванием случайно
выбранной буквы текста?
8. Известно, что некоторой болезнью в среднем болеют 2 человека из
100. Для выявления больных используется определённая реакция, которая
всегда оказывается положительной в том случае, когда человек болен; если
же человек здоров, то она столь же часто бывает положительной, как и
отрицательной. Пусть опыт b состоит в определении того, болен или здоров
человек, а опыт a - в определении результата указанной реакции.
Спрашивается, какова будет энтропия Н (b) опыта b и условная энтропия
Нa(b) опыта b при условии осуществления a?
9. Пусть опыты a и b состоят в последовательном извлечении двух
шаров из урны, содержащей m чёрных и n - m белых шаров (a - извлечение
первого шара, b - извлечение второго шара). Чему равны энтропии Н(a) и
Н(b) опытов a и b и условные энтропии Нa(b) и Нb(a) тех же опытов? Решите
ту же задачу при условии, что опыт a состоит в извлечении k шаров из урны,
а опыт b - в последующем извлечении еще одного шара.
10. Докажите, что для двух опытов справедливо соотношение Н(a) +
Нa(b) = Нb(a) + Н(b).
11. Опыты a и b состоят из последовательного извлечения без возврата
двух шаров из ящика, в котором изначально находились n белых шаров и m
черных. Найдите Н(a), Н(b), Нa(b), Нb(a).
5.3. Лабораторная работа №3. «Энтропия и информация»
1. Игра "Угадай-ка – 6". Некто задумал целое число в интервале от 0 до
5. Наш опыт состоит в угадывании этого числа. На наши вопросы Некто
может отвечать лишь "Да" или "Нет". Какое количество информации мы
должны получить, чтобы узнать задуманное число, т.е. полностью снять
начальную неопределенность? Как правильно построить процесс
угадывания?
2. Пусть известно, что жители некоторого города А говорят правду, а
жители соседнего города Б всегда обманывают. Наблюдатель Н. знает, что он
находится в одном из двух городов, но не знает в каком именно. Путём
опроса встречного ему требуется определить, в каком городе живёт его
собеседник (жители А могут заходить в Б и наоборот), или то и другое
вместе. Спрашивается, каково наименьшее число вопросов, которые должен
задать Н. (на все вопросы Н. встречный отвечает лишь "Да" или "Нет")?
Сформулируйте эти вопросы.
3. Пусть имеются три города А, Б, и В, причём жители А во всех
случаях говорят правду, жители Б - только неправду, а жители В через раз
отвечают на вопросы верно и неверно. Наблюдатель Н. хочет выяснить, в
каком городе он находится и в каком городе живет встреченный им человек.
Сколько вопросов ему потребуется задать этому встречному, если на все
вопросы его собеседник отвечает лишь "да" или "нет"? Последовательность
вопросов придумайте самостоятельно.
4. Сколько вопросов надо задать, чтобы отгадать задуманное
собеседником целое положительное число, не превосходящее 10 (или100,
или 1000, или произвольного целого положительного числа), если
спрашиваемый на все вопросы отвечает лишь "да" или "нет"?
5. Некто задумал два (различных) числа, не превосходящих 100.
Сколько надо задать ему вопросов для того, чтобы определить эти числа,
если на каждый вопрос спрашиваемый отвечает лишь "да" или "нет"?
6. Имеется 25 монет одного достоинства; 24 из них имеют одинаковый
вес, а одна - фальшивая - несколько легче остальных. Спрашивается,
сколькими взвешиваниями на чашечных весах без гирь можно обнаружить
эту фальшивую монету?
7. Пусть опыт b состоит в извлечении одного шара из урны,
содержащей 5 чёрных и 10 белых шаров, опыт ak - в предварительном
извлечении из той же урны (без возвращения обратно) k шаров. Чему равна
энтропия опыта b и информация об этом опыте, содержащаяся в опытах a1,
a2, a13, и a14?
8. Пусть для некоторого пункта вероятность того, что 15 июня будет
идти дождь, равна 0,4, а вероятность того, что дождя не будет, равна 0,6.
Пусть далее для этого пункта вероятность дождя 15 октября равна 0,8, а
вероятность отсутствия дождя в этот день - всего 0,2. Предположим, что
определённый метод прогноза погоды 15 июня оказывается правильным в 3/5
всех тех случаев, в которых предсказывается дождь, и в 4/5 тех случаев, в
которых предсказывается отсутствие осадков; в применении же к погоде 15
октября этот метод оказывается правильным в 9/10 тех случаев, в которых
предсказывается дождь, и в половине случаев, в которых предсказывается
отсутствие дождя (сравнительно большой процент ошибок в последнем
случае естественно объясняется тем, что предсказывается маловероятное
событие, предугадать которое довольно трудно). Спрашивается, в какой из
двух указанных дней прогноз дает нам больше информации о реальной
погоде?
5.4. Лабораторная работа №4 «Информация и алфавит»
Задание: составьте программу на языке программирования Паскаль, с
помощью которой подсчитайте количество информации, приходящейся на
один символ в каждом тексте (вероятность каждого символа в тексте как
отношение количества одинаковых символов каждого значения ко всему
числу символов в тексте), сравните и сделайте вывод.
1. Подсчитать количество информации, приходящейся на один символ,
в следующем тексте экономического содержания:
Организационно-правовые формы предприятий в своей основе
определяют форму их собственности, то есть, кому принадлежит
предприятие, его основные фонды, оборотные средства, материальные и
денежные ресурсы. В зависимости от формы собственности в России в
настоящее время различают три основные формы предпринимательской
деятельности: частную, коллективную и контрактную.
2. Подсчитать количество информации, приходящейся на один символ,
в следующем тексте технического содержания:
Общая технологическая схема изготовления сплавного транзистора
напоминает схему изготовления диода, за исключением того, что в
полупроводниковую пластинку производят вплавение двух навесок примесей
с двух сторон. Вырезанные из монокристалла германия или кремния
пластинки шлифуют и травят до необходимой толщины.
3. Подсчитать количество информации, приходящейся на один символ,
в следующем тексте исторического содержания:
С конца пятнадцатого столетия в судьбах Восточной Европы
совершается переворот глубокого исторического значения. На сцену истории
Европы выступает новая крупная политическая сила – Московское
государство. Объединив под своей властью всю северо-восточную Русь,
Москва напряженно работает над закреплением добытых политических
результатов и во внутренних, и во внешних отношениях.
4. Подсчитать количество информации, приходящейся на один символ,
в следующем тексте естественнонаучного содержания:
Новые данные о физиологической потребности организма человека в
пищевых веществах и энергии, а также выяснение закономерностей
ассимиляции пищи в условиях нарушенного болезнью обмена веществ на
всех этапах метаболического конвейера позволили максимально
сбалансировать химический состав диет и их энергетическую ценность.
5. Подсчитать количество информации, приходящейся на один символ,
в следующем художественно-литературном тексте:
С любопытством стал я рассматривать сборище. Пугачев на первом
месте сидел, облокотясь на стол и подпирая черную бороду своим широким
кулаком. Черты лица его, правильные и довольно приятные, не изъявляли
ничего свирепого. Все обходились между собою как товарищи и не
оказывали никакого особенного предпочтения своему предводителю.
5.5. Лабораторная работа №5 «Количество информации»
Для равновероятных множеств при измерении количества информации
применяется формула Хартли.
Данная формула позволяет определять:
•
количество информации, если известно количество событий;
•
количество возможных событий, если известно количество
информации;
Например, при решении задачи, вопрос которой стоит так: “в доме 8
этажей, какое количество информации мы получим, узнав, что
интересующий нас Коля Иванов живет на втором этаже?”, нужно
воспользоваться формулой Хартли: I=log2(8)=3 бита.
Следовательно, для решения обратных задач, когда известна
неопределенность (H) или полученное в результате ее снятия количество
информации (I) и нужно определить какое количество равновероятных
альтернатив соответствует возникновению этой неопределенности,
используют обратную формулу Хартли, которая выглядит следующим
образом:
Практическое задание. Решите задачи.
При угадывании целого числа в диапазоне от 1 до К было получено 7
бит информации. Чему равно К?
Сообщение о том, что Петя живет во втором подъезде, несет 3 бита
информации. Сколько подъездов в доме?
После реализации одного из возможных событий получили количество
информации равное 15 бит. Какое количество возможных событий было
первоначально?
В коробке лежат 64 цветных карандаша. Сообщение о том, что достали
белый карандаш, несет 4 бита информации. Сколько белых карандашей было
в коробке?
В течение четверти ученик получил 20 оценок. Сообщение о том, что
он получил четверку, несет 2 бита информации. Сколько четверок ученик
получил за четверть?
В корзине лежат черные и белые шары. Среди них 18 черных шаров.
Сообщение о том, что достали белый шар, несет 2 бита информации. Сколько
всего шаров в корзине?
В закрытом ящике находится 32 карандаша, некоторые из них синего
цвета. Наугад вынимается один карандаш. Сообщение «этот карандаш – НЕ
синий» несёт 4 бита информации. Сколько синих карандашей в ящике?
В коробе грибника лежат грибы: белые, подосиновики и мухоморы.
Всего 32 гриба. Сообщение о том, что вынули мухомор, несет 4 бита
информации. Мухоморов в 3 раза меньше, чем белых. Сколько грибов
каждого типа?
5.6. Лабораторная работа №6 «Системы счисления»
Задание: На языке программирования Паскаль составить программу, с
помощью которой можно переводить целые числа из одной системы
счисления в другую систему счисления.
С помощью программы решить следующие задачи.
Пушкин родился в 24189 году. А Лермонтов на F16 лет позже. Сколько
лет было бы Пушкину и Лермонтову в 34728 году, если бы Мартынов и
Дантес промазали? Ответ представить в восьмеричной системе счисления.
Приближаясь к дереву со скоростью 228км. в час, велосипедист Артур
мечтает покатать на своем велосипеде красавицу Катю. Как долго продлятся
Артуровы мечты, если до дерева осталось 110012 метров?
Ответ записать в секундах.
Друзья составили про Петю задачу: наш друг Петя ест невкусную
макаронину 3C16км. В первый день он съел C16 часть всей макаронины, во
второй - F16 часть всей макаронины. Сколько километров невкусной
макаронины
съедено
Петей
за
два
дня?
Число километров записать в двоичной системе счисления!
Один третьеклассник может отлупить трех первоклассников, но уже
четыре первоклассника отлупят третьеклассника сами. Кто будет побеждать
сначала и кто победит, в конце концов, если лупить друг друга начнут 148
третьеклассников и 1100002 первоклассников, а потом на вопли о помощи
прибегут еще 105 первоклассников и 103 третьеклассников?
В красавца Васю безумно влюбилось 628 девочек. 248 девочек
побежали топиться в пруду, но их вытащили спасатели, и они влюбились в
спасателей. 11002 девочек пошли в аптеку покупать яд. Но вместо яда им
продали касторку, и они разочаровались в любви. 710 девочек разлюбили
Васю и безумно влюбились в красавца Сережу. Остальные девочки твердо
решили выйти замуж за красавца Васю, когда он вырастет. Сколько девочек
мечтает,
чтобы
красавец
Вася
скорее
вырос?
Ответ представить в троичной системе счисления.
5.7. Лабораторная работа №7. Представление информации в компьютере
Информация (числовая, текстовая, графическая, звуковая) хранится в
памяти компьютера в двоичном виде. Для представления чисел в памяти
компьютера используются форматы: формат с фиксированной точкой
(представляются целые числа) и формат с плавающей точкой
(представляются вещественные числа).
Компьютерное представление целых чисел со знаком и без знака
Диапазон значений целых чисел зависит от размера разрядной сетки,
используемой для их хранения. В к-разрядной сетке может храниться 2К
различных значений. Значит, в 16-разрядной сетке (2 байта) можно хранить 2
16
=65 536 различных значений. Для хранения целых чисел существуют
различные типы данных, отличающиеся друг от друга количеством разрядов
и наличием (или отсутствием) знакового разряда.
Так, в беззнаковых целых типах все разряды отводятся для записи
двоичного представления числа. Нижняя граница диапазона значений равна 0
а верхняя граница рассчитывается исходя из количества разрядов (к),
занимаемых элементами данного типа: 2К -1. Например, для 2-байтового типа
целого положительного числа (тип Word) диапазон значений составляет от 0
до 65 535.
Для получения внутреннего представления целого положительного
числа X, хранящегося в к-разрядном машинном слове следует:
Перевести число X в двоичную систему счисления.
Полученный результат дополнить слева незначащими нулями до к
разрядов.
Пример. Получить внутреннее представление целого числа 1607 в 2-х
байтовой ячейке (тип Integer).
160710 =110010001112. 2 байта = 16 бит, т.е. для представления числа
отведено 16 разрядов. Внутреннее представление данного числа в 2-х
байтовой ячейке - 0000 0110 0100 0111.
В знаковых целых типах крайний левый разряд отводится на запись
знака числа (0 - положительное, 1 - отрицательное), остальные разряды числа
заняты его двоичным представлением (младший разряд -правый бит).
Диапазон значений в раза меньше чем у беззнаковых и определяется от -2К"1
-1 до 2К"1 -1. Например, для 2-байтового типа целого числа (тип Integer)
диапазон значений составляет от -32 768 до 37 767.
Для получения внутреннего представления целого отрицательного
числа (-Х), хранящегося в к-разрядном машинном слове следует:
Получить внутреннее представление положительного числа X.
Получить обратный код этого числа заменой 0 на 1, а 1 на 0.
К полученному числу прибавить 1 (дополнительный код).
Пример. Получить внутреннее представление целого отрицательного
числа -1607 в 2-х байтовой ячейке.
Внутреннее представление положительного числа в 2-х байтовой
ячейке
0000
0110
0100
0111.
Обратный код
1111 1001 1011 1000.
Дополнительный код 1111 1001 1011 1001
и является внутренним представлением числа (-1607).
Компьютерное представление вещественных чисел
Вещественные числа в компьютере представляются в формате с
плавающей точкой (запятой), т.е. число записывается в виде:
X = + m х пр,
где m - мантисса числа; р - порядок; п - основание СС.
Например, число 10,783 можно записать как 1,0783х101 или как
0,0010783х104 или как 1078,Зх10-2 и т.д Положение запятой (точки) в
мантиссе определяется величиной порядка р. С изменением порядка р в
большую или меньшую сторону, запятая (точка) перемещается влево или
вправо, т.е. «плавает» в изображении числа.
В компьютерах используют нормализованное представление числа, т.е.
мантисса должна удовлетворять условию:
0,1n<m<1n;
т.е. мантисса должна быть меньше единицы и первая значащая цифра
не должна равняться нулю.
В памяти компьютера мантисса m хранится как целое число,
содержащее только значащие цифры ( 0 целых и запятая не хранятся!), т.е.
внутренне представление вещественного числа сводится к представлению
двух целых чисел: мантиссы и порядка.
Так, в 4-байтовой ячейке памяти вещественное числа будет
представлено в следующем виде:
Первый байт содержит машинный порядок, причем в старшем бите
хранится знак числа, а в оставшихся 7 битах - сам порядок. 27 = 128, т.е.
порядок изменяется от 0 до 127. Порядок может быть положительным или
отрицательным, то есть 128 значений делятся поровну: от -64 до 63.
Машинный порядок смещен относительно математического и имеет
только положительное значение. 2вязь между машинным порядком (Мр) и
математическим (р) определяется выражением:
Мр = р + 64
в 10CС
Мр = р + 1000000
в 2 СС
Десятичное число 64 выбрано потому, что смещение выбирается таким
образом, чтобы минимальное математическое значение порядка равнялось
нулю.
В байтах со 2 по 4 располагается двоичное представление мантиссы.
Для записи внутреннего представления вещественного числа следует:
Перевести модуль данного числа в двоичную систему счисления с кзначащими цифрами.
Нормализовать двоичное число.
Найти машинный порядок в двоичной системе счисления.
Учитывая знак числа, записать его представление в к-разрядном
машинном слове.
Пример. Получить внутреннее представление числа 250,1875 в 4-х
байтовой ячейке (тип Single). Один байт отводится для записи машинного
порядка, а три байта для записи мантиссы.
Переводим исходное число в двоичную систему с 24 (3 байта х 8 = 24
бита) значащими цифрами: 250,187510=1111 1010,0011 0000 0000 00002
Нормализуем полученное двоичное число: 0,1111 1010 0011 0000 0000
0000 х 1021000 . 102 = 210 - основание СС, а 10002 = 810- математический
порядок.
Найдем машинный порядок: Мр = 1 000 + 1 000 000 = 1 001 000.
Представление десятичного числа 250,1875 в 4-х байтовой ячейке с
учетом знака числа выглядит следующим образом:
Шестнадцатеричная запись числа: 48FA3000.
Пример. По шестнадцатеричной записи внутреннего представления
числа С9811000 восстановить само число.
1. Запишем двоичное представление данного числа в 4-байтовой
ячейке. 1100 1001 1000 0001 0001 0000 0000 00002
В 34-бите (знаковый бит) записана 1, значит число отрицательное.
Определим математический порядок:
р = 100 10012- 100 00002 = 10012 = 910
Нормализуем запись мантиссы с учетом знака числа: - 0,1000 0001 0001
0000 0000 0000 х 2101001 .
Число в двоичном представлении имеет вид: - 100000010,0012
Переведем двоичное число в десятичное:
- 100000010,0012 = -(1-28 + 1-21 + 1-2"3 ) =-(256 + 2 + 0,125) = -256,12510
Покажем преобразование действительного числа для представления его
в памяти ЭВМ на примере величины типа Double.
Как видно из таблицы, величина это типа занимает в памяти 8 байт. На
рисунке показано, как здесь представлены поля мантиссы и порядка:
S
Смещенный порядок
Мантисса
6
52
0
3
Можно заметить, что старший бит, отведенный под мантиссу, имеет
номер 51, т.е. мантисса занимает младшие 52 бита. Черта указывает здесь на
положение двоичной запятой. Перед запятой должен стоять бит целой части
мантиссы, но поскольку она всегда равна 1, здесь данный бит не требуется и
соответствующий разряд отсутствует в памяти (но он подразумевается).
Значение порядка хранится здесь не как целое число, представленное в
дополнительном коде. Для упрощения вычислений и сравнения
действительных чисел значение порядка в ЭВМ хранится в виде смещенного
числа, т.е. к настоящему значению порядка перед записью его в память
прибавляется смещение. Смещение выбирается так, чтобы минимальному
значению порядка соответствовал нуль. Например, для типа Double порядок
занимает 11 бит и имеет диапазон от 2–1023 до 21023, поэтому смещение равно
1023(10) = 1111111111(2). Наконец, бит с номером 63 указывает на знак числа.
Таким образом, из вышесказанного вытекает следующий алгоритм для
получения представления действительного числа в памяти ЭВМ:
1) перевести модуль данного числа в двоичную систему счисления;
2) нормализовать двоичное число, т.е. записать в виде M × 2p, где M —
мантисса (ее целая часть равна 1(2)) и p — порядок, записанный в десятичной
системе счисления;
3) прибавить к порядку смещение и перевести смещенный порядок в
двоичную систему счисления;
4) учитывая знак заданного числа (0 — положительное; 1 —
отрицательное), выписать его представление в памяти ЭВМ.
Пример. Запишем код числа –312,3125.
1) Двоичная запись модуля этого числа имеет вид 100111000,0101.
2) Имеем 100111000,0101 = 1,001110000101 × 28.
3) Получаем смещенный порядок 8 + 1023 = 1031. Далее имеем
1031(10) = 10000000111(2).
4) Окончательно
10000000
0011100001010000000000000000000000000000000000000000
52
0
111
3
Очевидно, что более компактно полученный код стоит записать
следующим образом: C073850000000000(16).
Другой пример иллюстрирует обратный переход от кода
действительного числа к самому числу.
Пример. Пусть дан код 3FEC600000000000(16) или
01111111
1100011000000000000000000000000000000000000000000000
52
0
110
3
1) Прежде всего замечаем, что это код положительного числа,
поскольку в разряде с номером 63 записан нуль. Получим порядок этого
числа: 01111111110(2) = 1022(10); 1022 – 1023 = –1.
2) Число имеет вид 1,1100011 × 2–1 или 0,11100011.
3) Переводом в десятичную систему счисления получаем 0,88671875.
5.8. Лабораторная работа № 8 «Представление текстовой информации в
компьютере»
Изучить теоретический материал – Игорь Бекман «Информация в
компьютере».
Написать программу на языке программирования Паскаль,
кодирующую введенное сообщение кодом ASCII.
Ниже приведен текст сообщения, представленного в кодах ASCII. В
этой кодировке на один символ приходится один байт, который в этом
упражнении представлен в шестнадцатеричной системе счисления.
Декодируйте этот текст.
68 65 78 61 64 65 63 69 6D 61 6C (вводить без пробелов!)
5.9. Лабораторная работа №9 «Машина Тьюринга»
Тренажёр «Машина Тьюринга» — это учебная модель универсального
исполнителя (абстрактной вычислительной машины), предложенного в 1936
году А. Тьюрингом для уточнения понятия алгоритма. Согласно тезису
Тьюринга, любой алгоритм может быть записан в виде программы для
машины Тьюринга. Доказано, что машина Тьюринга по своим возможностям
эквивалентна машине Поста и нормальным алгорифмам Маркова.
Рис. 1. Интерфейс программы для изучения машины Тьюринга
Машина Тьюринга состоит из каретки (считывающей и записывающей
головки) и бесконечной ленты, разбитой на ячейки. Каждая ячейка ленты
может содержать символ из некоторого алфавита A={a0,a1,…,aN}. Любой
алфавит содержит символ «пробел», который обозначается как a0 или Λ. При
вводе команд пробел заменяется знаком подчеркивания «_».
Машина Тьюринга — это автомат, который управляется таблицей.
Строки в таблице соответствуют символам выбранного алфавита A, а
столбцы — состояниям автомата Q={q0,q1,…,qM}. В начале работы машина
Тьюринга находится в состоянии q1. Состояние q0 — это конечное состояние:
попав в него, автомат заканчивает работу.
В каждой клетке таблицы, соответствующей некоторому символу ai и
некоторому состоянию qj, находится команда, состоящая из трех частей:
символ из алфавита A;
направление перемещения: > (вправо), < (влево) или . (на месте);
новое состояние автомата
В верхней части программы находится поле редактора, в которое
можно ввести условие задачи в свободной форме.
Лента перемещается влево и вправо с помощью кнопок,
расположенных слева и справа от нее. Двойным щелчком по ячейке ленты
(или щелчком правой кнопкой мыши) можно изменить ее содержимое.
С помощью меню Лента можно запомнить состояние ленты во
внутреннем буфере и восстановить ленту из буфера.
В поле Алфавит задаются символы выбранного алфавита. Пробел
добавляется к введенным символам автоматически.
В таблице в нижней части окна набирается программа. В первом
столбце записаны символы алфавита, он заполняется автоматически. В
первой строке перечисляются все возможные состояния. Добавить и удалить
столбцы таблицы (состояния) можно с помощью кнопок, расположенных над
таблицей.
При вводе команды в ячейку таблицы сначала нужно ввести новый
символ, затем направление перехода и номер состояния. Если символ
пропущен, по умолчанию он не изменяется. Если пропущен номер состояния,
по умолчанию состояние автомата не изменяется.
Справа в поле Комментарий можно вводить в произвольной форме
комментарии к решению. Чаще всего там объясняют, что означает каждое
состояние машины Тьюринга.
Программа может выполняться непрерывно (F9) или по шагам (F8).
Команда, которая сейчас будет выполняться, подсвечивается зеленым фоном.
Скорость выполнения регулируется с помощью меню Скорость.
Задачи для машины Тьюринга можно сохранять в файлах. Сохраняется
условие задачи, алфавит, программа, комментарии и начальное состояние
ленты. При загрузке задачи из файла и сохранении в файле состояние ленты
автоматически записывается в буфер.
5.10. Лабораторная работа №10 «Машина Поста»
Тренажёр «Машина Поста» — это учебная модель универсального
исполнителя (абстрактной вычислительной машины), основанного на
работах Э.Л. Поста по уточнению понятия алгоритма. Согласно тезису Поста,
любой алгоритм может быть записан в виде программы для машины Поста.
Доказано, что машина Поста по своим возможностям эквивалентна машине
Тьюринга и нормальным алгорифмам Маркова.
Рис. 2. Интерфейс программы для изучения машины Поста
Машина Поста состоит из каретки (считывающей и записывающей
головки) и бесконечной ленты, разбитой на ячейки. Каждая ячейка ленты
может быть либо пустой («0»), или содержать метку («1»).
Программа состоит из пронумерованных строк. В каждой строке
записывается одна из следующих команд:
> N переместить каретку вправо на 1 ячейку и перейти к строке с
номером N;
< N переместить каретку влево на 1 ячейку и перейти к строке с
номером N
0 N записать в текущую ячейку «0» (стереть метку) и перейти к строке
с номером N
1 N записать в текущую ячейку «1» (поставить метку) и перейти к
строке с номером N
? N, M если текущая ячейка содержит «0» (не отмечена), то перейти к
строке
с
номером
N,
иначе
перейти
к
строке
M
. остановить программу
Номер строки перехода в командах >, <, 0 и 1 можно не указывать, при
этом происходит переход к следующей строке.
Для завершения работы программы достаточно сделать переход на
строку 0, например, так:
? 25, 0 остановить программу, если текущая ячейка содержит «1»,
иначе перейти к строке 25.
Троичная машина Поста
В троичной машине Поста используется расширенный алфавит,
состоящий из трех символов: пробел, «0» и «1». Это позволяет
программировать задачи, в которых числа записаны в двоичной системе
счисления. Команды, отличающиеся от классического (двоичного) варианта
машины Поста:
X N записать в текущую ячейку пробел (стереть метку) и перейти к
строке с номером N
0 N записать в текущую ячейку «0» и перейти к строке с номером N
1 N записать в текущую ячейку «1»" и перейти к строке с номером N
Номер строки перехода может отсутствовать, при этом машина
переходит на следующую строку программы.
Команда ветвления содержит три метки, разделенные запятыми:
? N,M,L если текущая ячейка пустая, то перейти к строке с номером N,
иначе если текущая ячейка содержит «0», то перейти к строке с номером M,
иначе (если текущая ячейка содержит «1») перейти к строке L
В верхней части программы находится поле редактора, в которое
можно ввести условие задачи в свободной форме.
Лента перемещается влево и вправо с помощью кнопок,
расположенных слева и справа от нее. Двойным щелчком по ячейке ленты
можно изменить ее содержимое (в «классическом» варианте заменяется «0»
на «1» или наоборот, в троичной машине Поста символы «пробел», «0» и «1»
при последовательных двойных щелчках меняются циклически).
С помощью меню Лента можно запомнить состояние ленты во
внутреннем буфере и восстановить ленту из буфера.
С помощью меню Алфавит можно переключать режим работы
машины (двоичный или троичный алфавит). В классическом режиме меню
Вид позволяет настроить вид ленты (точки, отметки-галочки, двоичный код).
В таблице в нижней части окна набирается программа. В первом
столбце записаны номера строк, он заполняется автоматически. Во втором
столбце из списка выбирается нужная команда, а в третьем вводится номер
строки для перехода (если это необходимо). Для добавления команды во
втором столбце можно использовать всплывающее контекстное меню.
Четвертый столбец может содержать комментарий к каждой строчке
программы. Добавить и удалить строки таблицы можно с помощью кнопок,
расположенных слева от таблицы.
Программа может выполняться непрерывно (F9) или по шагам (F8).
Команда, которая сейчас будет выполняться, подсвечивается зеленым фоном.
Скорость выполнения регулируется с помощью меню Скорость.
Задачи для машины Поста можно сохранять в файлах. Сохраняется
условие задачи, программа, состояние ленты и вид отметок. При загрузке
задачи из файла и сохранении в файле начальное состояние ленты
автоматически записывается в буфер.
5.11. Лабораторная работа №11 «Нормальные алгорифмы Маркова»
Тренажёр «Нормальные алгорифмы Маркова» — это учебная модель
универсального исполнителя, предложенного в 1940-х годах А.А. Марковым
для уточнения понятия алгоритма. Марков предположил, что любой
алгоритм может быть записан в виде нормального «алгорифма» (учёный
считал, что правильно произносить это иностранное слово именно так).
Позднее было доказано, что нормальные алгорифмы Маркова эквивалентны
по своим возможностям другим универсальным исполнителям: машине
Тьюринга и машине Поста.
Нормальный алгорифм задает метод преобразования строк с помощью
системы подстановок. Каждая подстановка состоит из слова-образца и словазамены, разделенных цепочкой символов «->». На каждом шаге замены
подстановки просматриваются по порядку сверху вниз, и выполняется первая
из них, которая подошла: первое найденное слово-образец рабочей строки
заменяется на слово-замену.
Рис. 3. Интерфейс программы для изучения алгорифмов Маркова
Слова слева и справа от знака «->» могут быть (а могут и не быть)
заключены в апострофы или двойные кавычки. Следующие подстановки
равносильны и определяют замену буквы «а» на сочетание «бв»:
а -> бв
'а' -> 'бв'
"а" -> "бв"
'а' -> "бв"
Левая часть (слово-образец) может отсутствовать, в этом случае словозамена ставится в самое начало рабочего слова. Обычно такая замена должна
стоять последней в списке подстановок (иначе происходит зацикливание).
Правая часть подстановки тоже может отсутствовать (при стирании
образца).
Символ «.» после слова-замены обозначает терминальную
подстановку, после которой выполнение алгоритма заканчивается.
Например:
'а'
->
'б'. заменить «а» на «б» и остановить программу
* -> .
стереть знак «*» и остановить программу
В верхней части программы находится поле редактора, в которое
можно ввести условие задачи в свободной форме.
Система постановок, задающая нормальный алгорифм Маркова,
набирается в виде таблице в нижней части окна программы.
Программа может выполняться непрерывно (F9) или по шагам (F8).
Команда, которая сейчас будет выполняться, подсвечивается зеленым фоном.
Скорость выполнения регулируется с помощью меню Скорость.
Задачи можно сохранять в файлах и загружать из файлов. Сохраняется
условие задачи, исходное слово и система подстановок.
Протокол работы алгоритма, в котором показаны все последовательные
замены, вызывается при нажатии клавиш Ctrl+P.
6. Материально-техническое обеспечение дисциплины
- программный комплекс для изучения алгоритмов Машины Поста
- программный комплекс для изучения алгоритмов Машины Тьюринга
- программный комплекс для изучения алгорифмов Маркова
- программный комплекс Shemes для изучения основ алгоритмизации
7. Рекомендуемая основная литература
1.
Лыскова, В. Ю.. Логика в информатике [Текст] : методическое
пособие / В. Ю. Лыскова, Е. А. Ракитина.- М.: Лаборатория Базовых Знаний,
2001, 160 с.
2.
Стариченко, Б. Е.. Теоретические основы информатики [Текст] :
учеб. пособие для студ. вузов по спец. 030100-Информатика / Б. Е.
Стариченко.- М.: Горячая линия - Телеком, 2004, 312 с.
3.
Информатика. Базовый курс [Текст] : учеб. пособие для студ.
высш. технич. учеб. заведений / под ред. С. В.Симоновича.- СПб.: Питер,
2001, 640 с.
4.
Информатика [Текст] : учеб. для экон. спец. вузов / под ред. Н. В.
Макаровой.- М.: Финансы и статистика, 2003, 768 с.
5.
Могилев, А. В.. Информатика [Текст] : учеб.пособие для студ.
пед. вузов по спец." Информатика" / А. В. Могилев, Н. И. Пак, Е. К. Хеннер;
Под ред. Е. К. Хеннера.- М.: Академия, 2008, 848 с.
6.
Могилев, А. В.. Практикум по информатике [Текст] :
[учеб.пособие для студ. вузов] / А. В. Могилев, Н. И. Пак, Е. К. Хеннер; под
ред. Е. К. Хеннера.- М.: Академия, 2008, 608 с.
8. Рекомендуемая дополнительная литература
1.
Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ
вычислительных алгоритмов. - М.: Мир, 1979.
2.
Басакер Р., Саати Т. Конечные графы и сети. - М.: Наука, 1975.
3.
Беленькая Л.Х., Овчинникова С.Н. Методические указания:
вычислительная погрешность при расчетах на ЭВМ, ГРУ, 1994 г.
4.
Белов В.В., Воробьев Е.М., Шаталов В.Е. Теория графов. - М.:
Высш. шк., 1976.
5.
Березин И.С., Жидков Н.П. «Методы вычислений», 4.1. М. 1966 г.
6.
Берж К. Теория графов и ее применения. - М.: Изд-во иностр.
лит., 1962.
7.
Вербицкий В.М. Численные методы: линейная алгебра и
нелинейные уравнения. – М.: Высшая школа, 2000 г.
8.
Демидович Б.Н., Марон И.А. «Основы вычислительной
математики». М. 1978 г.
9.
Евстигнеев
В.А.
Применение
теории
графов
в
программировании. - М.: Наука, 1985.
10. Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы
обработки деревьев. - Новосибирск: Наука, 1994.
11. Ершов А.П. Введение в теоретическое программирование.
Беседы о методе. - М.: Наука, 2004.
12. Жуков М.Ю., Маркман Г.С. Лабораторные задания по методам
вычислений для III курса. ГРУ, 1979 г.
13. Зыков А.А. Основы теории графов. - М.: Наука, 1984.
14. Зыков А.А. Теория конечных графов. - Новосибирск: Наука,
1969.
15. Касьянов В.Н. Оптимизирующие преобразования программ. - М.:
Наука, 1988.
16. Касьянов В.Н., Потосин И.В. Методы построения трансляторов. Новосибирск: Наука, 1986.
17. Каханер Дэвир и др. Численные методы и программное
обеспечение. М. 1998 г.
18. Кнут Д. Искусство программирования для ЭВМ. Т. 3. Сортировка
и поиск. - М.: Мир, 2002.
19. Лавров И.А., Максимов Л.А. Задачи по теории множеств,
математической логике и теории алгоритмов. М. 1995 г.
20. Лихтарников Л.М., Сукачева Т.Г. Математическая логика, М.
1988 г.
21. Марчук Г.И., Кузнецов Ю.А. Итерационные методы и
квадратичные функционалы. – Новосибирск: Наука, 1972 г.
22. Мудров А.Е. Численные методы для ПЭВМ на языках Бейсик,
Фортран и Паскаль. – Томск: МП «Раско», 1992 г.
23. Рапитин В.И., Первушин В.Е. Практическое руководство по
методам вычислений с приложением программ для персонального
компьютера. М. 1989 г.
24. Самарский А.А. Введение в численные методы. - M. 1987 г.
25. Файнстейн В. А., Основы теории информации. – М.: ИЛ, 1960. –
233с.
1/--страниц
Пожаловаться на содержимое документа