bigpo.ru
добавить свой файл
1
  1. Пояснительная записка


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

Настоящий курс «Элементы компьютерных технологий» имеет цель дать ученикам 10-11 классов знания по основам информатики и программирования в рамках нижеприведенной программы. Курс посвящен изучению задач по математическим основам информатики (позиционные системы счисления и булева алгебра), а также по алгоритмизации и программированию. Основная часть задач последнего типа требует для своего успешного решения освоения около двух десятков алгоритмов, которые можно считать базовыми.


2. Описание содержания тем занятий

2.1. Позиционные системы счисления


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

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

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

Переводы в систему счисления с основанием, кратным двойке (2, 8, 16), наиболее эффективно выполнять при помощи триадно-тетрадного метода, суть которого заключается в независимом переводе триад (тетрад) в цифры требуемого 8-ричного (16-ричного) числа.

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

Умножение в позиционной системе счисления является достаточно сложным действием, поэтому более надежно умножение выполнять в 10- тичной системе с предварительным и завершающим переводом в исходную.

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

2.1. Булева алгебра


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

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

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


2.3. Решение задач по программированию


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

Стиль оформления задач может быть различным. Однако можно рекомендовать следующие разделы:

1. Исходные данные.

2. Требуемый результат.

3. Рабочие переменные.

4. Алгоритм.

5. Программа.

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

В разделе «Рабочие переменные» указываются наиболее важные вспомогательные переменные, описывающие необходимые промежуточные структуры данных.

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

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

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

В таблицах 1 – 3 приведены перечни таких базовых алгоритмов.

Таблица 1. Базовые алгоритмы обработки массивов




Наименование алгоритма

1

Суммирование элементов массива

2

Определение максимального (минимального) элемента и его порядкового номера в массиве

3

Отбор элементов, удовлетворяющих некоторому условию, в новый массив

4

Поиск заданного элемента в массиве

5

Сортировка элементов массива в порядке возрастания (убывания)

6

Формирование массива без повторений из массива, элементы в котором могут повторяться

7

Обработка двумерных массивов. Реализация описанных выше алгоритмов для строк, столбцов или диагоналей двумерного массива (матрицы)



Таблица 2. Базовые алгоритмы обработки дат



Наименование алгоритма

1

Определить, является ли високосным заданный год

2

По дате (день, месяц и год) определить порядковый день года

3

По порядковому дню года определить его дату.

4

По дню недели одной даты определить день недели другой даты


Таблица 3. Базовые алгоритмы обработки текстов



Наименование алгоритма

1

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

2

Слова в строке разделены разделителями «пробел,;:.-!?». Сформировать массив слов

3

Задан текст в виде массива строк. Предложения в тексте завершаются одним из символов «.!?». Сформировать массив предложений

4

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

5

Дан текст в виде массива строк. Отформатировать текст на заданную длину строки с выравниванием и по левому, и по правому краю и равномерным распределением пробелов между словами строк там, где они были в исходном тексте

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

Вспомогательные алгоритмы обработки массивов

1.

Произведение элементов массива.

2.

Суммирование элементов массива, удовлетворяющих некоторому условию.

3.

Подсчет количества элементов массива, удовлетворяющих некоторому условию.




  1. Программа курса

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

2 ч.

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

2 ч.

  1. Комбинированных задачи на системы счисления

4 ч.

  1. Контрольная работа № 1

2 ч.

  1. Булевские выражения и таблицы истинности

4 ч.

  1. Контрольная работа № 2

2 ч.

  1. Структура простой программы на языке Паскаль. Организация ввода-вывода информации.

4 ч

  1. Линейные и разветвляющиеся алгоритмы

4 ч

  1. Циклические алгоритмы

2 ч

  1. Одномерные массивы

2 ч

  1. Алгоритмы вычисления сумм, произведений, вычисление наибольших и наименьших элементов массивов

4 ч

  1. Линейные таблицы. Вложенные циклы.

4 ч

  1. Алгоритмы сортировки массивов

2 ч

  1. Контрольная работа № 3

2 ч

  1. Работа с датами

4 ч

  1. Контрольная работа № 4.

2 ч

  1. Формирование массивов без повторений

4 ч

  1. Решение задач

4 ч

  1. Контрольная работа № 5

2 ч

  1. Символьный тип данных.

4 ч

  1. Алгоритмы выделения слов из строк

2 ч

  1. Решение задач.

6 ч.

  1. Контрольная работа № 6

2 ч



ЛИТЕРАТУРА



  1. Гришагин В.А., Карпенко С.Н. Контрольные задания по информатике для учащихся подготовительных курсов. – Н. Новгород: ННГУ, 2002. – 80 с.

  2. Барышева И.В., Городецкий С.Ю., Громницкий В.С., Малыженков В.И., Маркина М.В. Задачи по информатике./ По материалам выпускных экзаменов подготовительного факультета и вступительных экзаменов в ННГУ в 2004 году. – Н. Новгород: ННГУ, 2004. – 60 с.

  3. Барышева И.В., Громницкий В.С., Малыженков В.И., Маркина М.В. Информатика./ По материалам выпускных экзаменов подготовительного факультета и вступительных испытаний в ННГУ в 2005 году. – Н. Новгород: ННГУ, 2005. – 54 с.

  4. Барышева И.В., Городецкий С.Ю., Громницкий В.С., Малыженков В.И., Маркина М.В. Информатика./ По материалам выпускных экзаменов подготовительного факультета и вступительных испытаний в ННГУ в 2006 году. – Н. Новгород: ННГУ, 2006. – 68 с.

  5. Информатика и ИКТ. Подготовка к ЕГЭ/ под ред. проф. Макаровой Н.В. Спб. Питер. 2008.

  6. Единый государственный экзамен по информатике и ИКТ. Демонстрационный вариант 2009.