ГОУ ВПО Славянский-на-Кубани государственный педагогический институт

УТВЕРЖДЕНО

На заседании кафедры

Информатики и МПИ

Протокол №____________

"___"_____________ 2010 г.

Зав. кафедрой ___________

ПРОГРАММА

Государственного экзамена

по дисциплинам

«Информатика, теория и методика обучения информатике»

Специальность 050201 «Математика» с доп. спец. 050202 «Информатика»

Специальность 050202 «Информатика»

Славянск-на-Кубани

Г.

I. Программирование, программное обеспечение ЭВМ, информационные системы

Языки программирования: обзор, классификация, примеры. Среда программирования, её основные функции и компоненты. Интерпретаторы и компиляторы. Отладка, тестирование и трансляция программ. Язык программирования: понятие оператора, программы, программы линейного типа. Алгоритмизация решения задачи. Блок-схемы алгоритмов. Стандартные алгоритмические конструкции.

Основные типы языков программирования: процедурные, функциональные, реляционные, объектно-ориентированные. Языки высокого уровня и машинные языки. Примеры языков. Среда программирования (на примере среды Турбо-Паскаля и Delphi) – состав (многооконная система, редактор, меню, панели инструментов), назначение элементов среды. Понятие о трансляции программ, интерпретаторы и компиляторы. Понятия отладки и тестовой проверки программы. Понятие алгоритма и алгоритмизации задачи. Необходимые и сравнительные свойства алгоритмов (дискретность, детерминированость, конечность и результативность, рекурсивность, массовость). Стандартные алгоритмические схемы: линейная, циклическая, разветвляющаяся. Язык Блок-схем описания алгоритмов – стандартные конструкции и операторы. Примеры блок-схем алгоритмов линейной, разветвляющей и циклической структуры. Понятие программирования. Операторы, идентификаторы и структура программы процедурных языков программирования. Линейная структура программы.

Язык Turbo Pascal: структура программы, простой и составной оператор. Операторы переходов: условный оператор, оператор выбора (переключения).

Структура программы Турбо Паскале. Назначение основных разделов (Program, Use, Label, Type, Const, Var, разделов подпрограмм и основной программы. Простой и составной оператор в Турбо-Паскале. Операторные скобки begin … end. Разделители в Турбо-Паскале: точка, точка с запятой, двоеточие, две точки, кавычки, скобки. Операторы переходов: IF. THEN... ELSE,. CASE...OF... END, GOTO … . Метки и их использование. Условный и безусловный переход. Организация проверки условий с помощью операторов перехода. Оператор выбора и его структура. Применение оператора выбора для структурной организации программы.

Типы данных в системе программирования Turbo Pascal: простые и составные типы данных. Константы и переменные. Запись математических выражений. Базовые математические операции и стандартные математические функции. Символьный и строковый тип данных. Логические выражения и операции отношения. Булевый тип данных. Обработка символов и строк в Turbo Pascal.

Описание (задание) типов данных. Стандартные типы данных в Турбо-Паскале: Integer, Byte, Word, Longint, Real, Double, Extended, Boolean, Char. Структурированные (составные) типы данных: понятие о строках, массивах, множествах, записях.

Константы и переменные в Турбо-Паскале. Задание констант и переменных. Стандартные константы. Инициализация переменных. Математические выражения. Запись математических выражений. Типы математических операций в Турбо Паскале, приоритет операций. Совместимость типов, правило совместимости типов данных. Стандартные математические функции (abs(x), ln(x), exp(x), sqrt(x), sqr(x), sin(x), cos(x), arctan(x), trunc(x), .frac(x), int(x), Pi, random, random(i)). Символьные и строковые величины. Функции, работающие с символами: chr(...), ord(...), pred(...), succ(...), #. Код символа и кодовая таблица ПЭВМ. Строка как массив символов, длина строки. Функции, работающие со строками: length(...), copy(...), str(...), val(...), pos(...), insert(...), delete(...). Операция конкатенации. Построение логических выражений и логические операции (AND, OR, NOT, XOR). Логические операции отношения (<, >, >=, <=, <>, =). Различие между оператором присваивания и логического сравнения. Логический тип данных. Сравнение нечисловых типов данных (знаков, строк, множеств).

Основные алгоритмы обработки данных. Поиск заданного элемента массива методом перебора. Бинарный поиск. Поиск максимального и минимального элемента массива. Сортировка данных. Простая и быстрая сортировка. Сортировка массива методом «пузырька».

Поиск в упорядоченном и неупорядоченном массиве. Последовательный поиск (метод перебора) и его алгоритм. Оптимизация алгоритма поиска, алгоритм бинарного поиска. Сравнение эффективности алгоритмов поиска. Алгоритм нахождения максимального (минимального) элемента массива данных. Задачи сортировки данных. Алгоритмы сортировки данных (медленная и быстрая сортировка). Примеры методов сортировки. Сравнение эффективности алгоритмов сортировки. Сортировка массива данных методом «пузырька».

Организация работ с процедурами и функциями пользователя в языке программирования Turbo Pascal. Передача параметров. Рекурсия и ее использование.

Необходимость организации процедур. Описание процедуры: заголовок, параметры, тело процедуры. Локальные и глобальные переменные. Формальные переменные и фактические значения. Передача данных. Параметры-значения и параметры-переменные. Типизированные и не типизированные параметры. Вызов и использование процедур. Необходимость организации функций пользователя и их отличие от процедур. Описание функции: заголовок, параметры, тело процедуры, итоговый результат. Вызов и использование функций. Понятие рекурсии, рекурсивный вызов процедур и функций. Использование рекурсии в программировании.

Файлы данных в языке Object Pascal: открытие, запись, чтение, закрытие. Текстовые, типизированные, нетипизированные файлы. Прямой и последовательный доступ к файлам.

Понятие файла. Типы файлов (текстовые, типизированные, не типизированные, последовательного и прямого доступа). Открытие (инициализация) файла, создание файла, запись данных в файл, чтение из файла данных, закрытие файла. Буфер файла – назначение, организация и контроль. Описание процедур и функций Assign, Close, Rewrite, Reset, Append, Read(ln), Write(ln). Определение типа файла с помощью файловой переменной. Использование файлов в программировании. Поиск данных в файлах. Описание процедур и функций FilePos, Seek, Eof, Eoln. Ввод числовых и строковых переменных, операторы Read, Readln и их действие. Ввод данных из файла. Вывод числовых и строковых выражений, операторы Write, Writeln и их действие. Вывод данных в файл.

Объектно-ориентированное программирование – общая характеристика и сравнительный анализ. Объект и класс. Базовые принципы ООП – инкапсуляция, полиморфизм и наследование. Понятие класса в языке Object Pascal. Структура класса: поля, методы, свойства. Доступ к структурным элементам класса. Иерархия наследования классов. Конструктор и деструктор класса.

Понятие Объектно-ориентированного программирования. Связь ООП с историей развития программирования. Понятие объекта и класса. Принцип инкапсуляции, его роль и методы реализации. Полиморфизм объектов и методы его реализации. Наследование классов, построение иерархического дерева наследования классов. Роль и методы реализации наследования классов. Классы в языке Object Pascal – назначение, структура, основные разделы. Назначение разделов Published, Public, Private, Protected. Поля класса – назначение, описание, методы доступа. Методы класса - назначение, описание, вызов метода. Конструктор и деструктор. Динамический характер объектов. Наследование классов. Перегрузка методов. Свойства класса - назначение, описание, методы доступа. Чтение и запись содержимого свойства.

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

Понятие визуального программирования. Среда Delphi – форма, меню, инспектор объектов, палитра компонентов (назначение и содержание). Интерактивный режим работы и использование манипулятора мышь. Настройка свойств формы: размер, местоположение, цвет, шрифт, заголовок, системное меню, граница. Проект, форма-модуль, компонент. Панель палитры компонентов – использование стандартных компонентов. Создание, компиляция, запуск и сохранения проекта/приложения. Понятие событийно-управляемой программы. Событие – его виды и программирование обработки событий. Работа с клавиатурой и манипулятором мышь. Вкладка Events инспектора объектов. Создание процедуры обработки события. Стандартные варианты событий. Организация диалога – ввода/вывода данных с помощью стандартных компонентов. Работа с компонентами Edit, Memo, ReachEdit. Функции преобразования типов StrToInt, StrToFloat, IntToStr, FloatToStr.

Организация интерфейса программы в среде визуального программирования Delphi. Меню пользователя, управляющие элементы (кнопки, списки, флажки). Использование компонентов StringGrid, OleContainer и WebBrowser. Внедрение OLE-объектов в программу Delphi. Подключение файлов формата HTML.

Понятие интерфейса программы. Особенности интерфейса проекта Delphi – работа с формой, меню пользователя, управляющими элементами (кнопки, списки, флажки). Создание и подключение 2-й формы. Использование стандартных компонентов интерфейса - Mainmenu, Popmenu, Label, Button, Panel, ListBox, RadioGroup, Image и т.д.. Назначение и виды технологии OLE. Представление данных в табличной форме с помощью компонента StringGrid. Установка числа и размера строк и столбцов таблицы. Редактирование таблицы с помощью свойства Cells. Подключение файлов приложений MS OFFICE и HTML формата. Стандартные компоненты OleContainer и WebBrowser - назначение, подключение и настройка компонентов.

Использование компонентов стандартных диалогов для программирования в среде Delphi. Диалоги работы с файлами, цветами, шрифтами, поиска и замены. Работа с компонентами – редакторами. Ввод текста, редактирование и работа с текстовыми файлами.

Понятие стандартного диалога. Основные виды диалогов – работа с файлами, цветами, шрифтами, диалоги поиска и замены. Подключение, активация и работа стандартных компонентов диалога – OpenDialog, SaveDialog, OpenPictureDialog, SavePictureDialog, FontDialog, и т.д.. Компоненты редакторы – однострочные (Edit, MaskEdit), многострочные – Memo, ReachEdit. Ввод, редактирование теста. Понятие о формате RTF. Компонент RichEdit – назначение и его основные свойства. Форматирование текста с помощью свойства Paragraph. Работа с текстовыми файлами – загрузка, редактирование и сохранение. Основы работы с классом TStrings.

Программирование графики в среде визуального программирования Delphi. Компоненты вывода и построения графических изображений. Методы класса холста TCanvas. Построение основных графических примитивов и графика функции.

Понятие растрового графического изображения. Пиксели, разрешение и цветовые возможности экранов. Графический драйвер. Система графических координат. Класс холста TCanvas и его возможности. Методы и свойства класса TCanvas – построение графических примитивов – линий, прямоугольников, эллипсов, дуг (Arc, Draw, Ellipse, LineTo, Pie, Rectangle, Polyline, Moveto, FloodFill и т.д.). Вывод текста и использование штриховки. Работа с объектами классов TPen и TBrush, установка цветов, стилей, размеров. Построение простейшего графика функции – построение осей, задание массива точек класса TPoint, построение ломаной по точкам методом Polyline. Понятие о масштабировании графика функции.

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

Понятие реляционной базы данных. Алиас, имя и тип базы данных. Стандартные компоненты для работы с базой данных Table, DataSource, DBGrid, DBNavigator. Подключение, просмотр и редактирование базы данных. Методы класса Ttable: навигации (next, prior, first, last), редактирования (delete, insert, createtable, deletetable, emptytable, post). Фильтры базы данных. Создание и подключение фильтра, свойства класса Ttable – Filter, Filtred.

Разработка и модификация структуры базы данных, настройка BDE с помощью системы Database Desktop.

Назначение системы BDE. Запуск и среда системы Database Desktop. Создание базы данных – создание и редактирование структуры, ввод и редактирование данных. Настройка BDE в системе Database Desktop – работа с Alias Manager. Стандартные типы данных для полей базы данных типа Paradox, ограничения для полей – ограничения значений. Индексирование баз данных, создание вторичных индексов. Подключение индекса – свойство IndexName класса Ttable.

Компьютерная графика. Пакеты растровой и векторной графики.

Виды компьютерной графики (векторная, растровая, фрактальная, трехмерная), графические форматы. Хранение графической информации. Разрешение: экрана, принтера, изображения; понятие растра, пикселя. Цветовые модели (RGB, CMYK и др,). Графические редакторы. Работа с редактором векторной графики OO.o Draw: панели инструментов, создание объектов, обработка готовых изображений, управление трехмерными объектами, группировка и объединение объектов. Создание объемных изображений.

Операционные системы как средство распределения и управления ресурсами ЭВМ.

Понятие ОС, назначение, виды ОС (однопользовательские и многопользовательские, однозадачные и многозадачные, сетевые и несетевые), примеры. Историческое развитие систем управления ресурсами ЭВМ - программирование в кодах, язык ассемблера, развитие ОС. Основные линии ОС – Windows, MacOs, OS/2, Unix\Linux. Режимы работы ОС: разделения времени, фоновый режим, режим реального времени. Основные подсистемы ОС – система загрузки, система ввода-вывода, командный процессор, файловая система, система прерываний, драйверы, утилиты, система внешнего интерфейса. Команды ОС – внутренние (командного процессора, работа с командной строкой) и внешние – утилиты (команды работы с дисками, с файлами, с каталогами, команды управления системой). Создание и исполнение командных bat файлов. Привести примеры.

Понятие файловой системы.

Понятие файла, имя и расширение файла, понятие каталога и пути к файлу, операции над файлами (открытие, копирование, перемещение, объединение, удаление, закрытие и т.д.). Типы файлов (прямого и последовательного доступа). FAT таблица размещения файлов. Понятие о системах FAT16, FAT32, NTFS. Понятие о разметке и форматировании диска. Работа с файловыми менеджерами на примере - Total Comander или Проводник Windows. Командная строка, команды работы с файлами и каталогами. Создание ярлыка.

Общие сведения о операционной системе Windows. Загрузка операционной системы. Особенности настройки Windows и установки приложений.

Общие сведения о семействе ОС Windows. Процессы загрузки ОС. Основные структурные компоненты (BIOS, загрузчик системы, драйверы устройств, утилиты). Базовые возможности и характеристики Windows, графический интерфейс, кодовая таблица ANSI, обмен данными между приложениями, технология внедрения и связывания объектов OLE. Настройка графического интерфейса и ОС, инсталляция приложений. Основные возможности работы в графическом интерфейсе: рабочий стол, папки и ярлыки программ, мой компьютер, копирование, удаление, перенос элементов, панель управления, поиск файлов и папок. Справочная система. Создание ярлыка.

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

Прикладное программное обеспечение общего назначения: обзор и классификация (текстовые редакторы, издательские и графические системы, электронные таблицы, СУБД, интегрированные системы), ПО специального назначения (авторские, экспертные, гипертекстовые системы, системы мультимедиа), ПО профессионального уровня (АРМ, САПР, АСНИ, АСУ, АСУ ТП, педагогические комплексы, системы телекоммуникаций). Математические пакеты и организация вычислений (на примере среды MathCad). Объекты рабочего листа MathCad, строка состояния, редакторы, обеспечивающие работу пакета, последовательность обработки формул, трассировка ошибок, разделители страниц (плавающие/фиксированные концы страниц). Выравнивание областей, виды курсоров, работа с текстовыми и математическими областями, виды текстовых областей (собственный текст, импортированный), отделение областей, математические символы внутри текста. Вставка гиперссылок, создание ссылок в виде кнопок. Панели инструментов. Построение графиков. Решение систем уравнений при помощи оператора Solve. Упрощение выражений (Simplify). Разложение выражений (Expand). Разложение на множители (Factor). Приведение подобных слагаемых (Collect). Нахождение пределов, производной, суммы рядов, символьное и численное произведение ряда, вычисление интеграла, матрицы: сложение, умножение матриц, решение систем уравнений методом Крамера. Построение графиков функций, поверхностей.

Офисные пакеты: назначение, состав, возможности. Создание презентаций.

Состав и назначение пакетов Open Office (текстовый и табличный процессоры, СУБД, электронная почта система разработки презентаций). Интеграция офисных приложений, взаимообмен и дополнение различных видов представления информации. Требования к содержанию и внешнему виду презентаций. Разработка и демонстрация презентации. Назначение, структура презентации, методы ее представления. Настройка параметров презентации – управление временем, эффекты, анимация и т.д. Преобразование презентации в HTML формат. Использование гиперссылок и элементов управления в презентациях. Создание управляющих кнопок.

СУБДOpen OfficeBase. Понятие базы данных. Структура базы данных. Таблицы базы данных, понятия поля и записи. Понятие ключа, простой и составной ключ.

Создание, редактирование и форматирование таблиц базы данных. Работа с конструкторами и мастерами Создание ключевого поля. Индексирование записей БД. Связи между таблицами, виды связей, установка связей между таблицами.

СУБДOpen OfficeBase. Базы данных и СУБД. Виды запросов. Фильтрация и сортировка данных.

Редактирование и форматирование таблиц базы данных Понятие запроса. Типы запросов. Построение запросов с помощью мастера. Построение запросов в режиме дизайна (конструктора): окно дизайнера запросов. Параметры запроса. Вычисляемые поля. Фильтрация записей, виды фильтров. Сортировка записей.

СУБДOpen OfficeBase. Базы данных и СУБД. Понятие базы и СУБД. Создание формы для работы с БД. Создание отчетов.

Создание, форматирование и редактирование таблиц. Назначение экранных форм. Средства создания форм. Панель инструментов «Элементы управления». Кнопки перемещения по записям. Управление объектами (перемещение, изменение размеров, добавление, удаление). Создание управляющих кнопок (следующая запись, предыдущая запись и пр.). Создание панели навигации. Группировка объектов формы. Создание отчетов.

Системы обработки текста: назначение и основные возможности. Текстовый процессор. Работа и настройка среды текстового процессора. Создание, редактирование, печать и сохранение документов. Форматирование документов. Преобразование в HTML и другие форматы.

Понятие текстового процессора, виды (однострочные и многострочные редакторы, многооконные редакторы, системы, имеющие графические шрифты и интегрированные средства форматирования документов, издательские системы.). Среда пакета MS Word/OO.o Writer (палитра компонентов, окна, меню, строка состояния, настройка среды). Создание, сохранение, печать документа. Форматирование документа: форматирование шрифта, абзаца, страницы, раздела, документа, стиль документа, колонтитулы. Работа со списками, многоуровневый список. Работа с редактором формул Math. Преобразование документа в HTML и другие форматы. Создание оглавления. Создание гиперссылки.

Системы обработки текста: назначение и основные возможности. Вставка объектов других приложений. Работа с таблицами.

Работа с таблицами в текстовом процессоре, создание, заполнение, форматирование и редактирование таблиц. Скриншоты. Рисование – объемные изображения, взаимное расположение элементов рисунка. Вставка и редактирование объектов: рисунков, файлов других приложений, совместимость рисунка с текстом

Табличные процессоры: назначение и основные возможности. Работа и настройка среды табличного процессора. Создание, редактирование, печать и сохранение таблиц. Обработка математических данных. Построение графиков и диаграмм.

Понятие табличного процессора, его назначение и возможности. Среда табличного процессора – меню, панель инструментов, строка состояния. Понятие рабочего листа, рабочей книги. Настройки среды ЭТ. Режимы работы табличного процессора. Ячейка, ее адрес. Типы данных ячеек. Ссылки и формулы в электронной таблице (ЭТ). Создание таблицы, редактирование и форматирование, сохранение, печать: масштаб печати, порядок распечатки страниц. Вставка объектов в таблицу. Копирование ячеек. Специальные функции ЭТ. Обработка математических данных (сумма, среднее, произведение, таблица значений функции). Построение графика функции (построение графиков простейших функций sin(x), cos(x), ax²+b x+c, график двумерной функции). Построение диаграмм. Построение полусферы. Специальные возможности табличного процессора: зависимости формул, влияющие/зависимые ячейки; создание примечания, прогрессия.

Понятие информационной системы. Основные классы ИС. Области применения информационных систем. Требования, предъявляемые к информационным системам. Программные средства разработки ИС и жизненный цикл ИС.

Понятие информационной системы, ее назначение и возможности. Основные классы ИС и их назначение. Области применения ИС и особенности разработки ИС для каждой сферы применения. Требования, предъявляемые к информационным системам и возможности их реализации. Основные программные средства разработки ИС и их классификация. Жизненный цикл ИС – состав этапов и их назначение.

Исследование операций

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

Понятие стохастического моделирования. Понятие детерминированного процесса, случайного процесса, шума. Сущность метода Монте-Карло. Применение данного метода для вычисления интегралов, поиска экстремума, проверки равномерности распределения. Построение генераторов случайных чисел. Понятие псевдослучайных чисел. Различные виды генераторов: табличный, аппаратный и алгоритмический способ. Примеры алгоритмических генераторов (генератор Фон-Неймана, линейный генератор, генератор Таусворта). Закон распределения случайных величин. Генерация случайных величин распределенных по экспоненциальному, нормальному и произвольному закону распределения.

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

Потоки событий их параметры и классификация. Характеристика потоков - плотность, распределение, последействие, однородность, стационарность. Системы массового обслуживания - понятие, классификация, примеры. Графовая модель СМО. Вероятность перехода. Уравнения Колмогорова. Финальные вероятности. Основные характеристики СМО - длина очереди, время ожидания, число отказов, время обслуживания. Схема гибели и размножения.

Основные понятия теории игр. Чистые и смешанные стратегии игры. Седловая точка игры и ее поиск.

Классификация задач теории игр (игры с чистой и смешанной стратегией). Постановка задачи теории игр, матрица игры, исследование матрицы – проверка на наличие седловой точки. Решение задачи в смешанных стратегиях.

43 Транспортная задача: постановка задачи, поиск опорного плана, оптимизация решения.

Понятие и постановка транспортной задачи. Табличное представление задачи. Опорный план задачи. Методы получения опорного плана (северо-западного угла и предварительной оптимизации). Условие баланса. Решение транспортной задачи методом потенциалов Канторовича.

Рекурсивные функции.

Понятие рекурсивной функции. Базовые рекурсивные функции. Оператор суперпозиции. Оператор примитивной рекурсии. Оператор минимизации. Тезис Черча. Тезис Клини. Доказательство рекурсивности функций.

Основные задачи теории кодирования. Кодирование и декодирование. Теоремы Шеннона. Методы восстановления информации в канале с шумом. Коды Хэмминга. Понятие о компьютерной криптографии. Сложность алгоритма. Классы сложности алгоритмов. NP задачи.

Основные задачи теории кодирования: однозначное кодирование-декодирование, оптимальные коды и методы сжатия информации, самовосстанавливающиеся коды, криптографические задачи. Процессы кодирования и декодирования. Избыточность кодирования. Понятие о теоремах Шеннона (о существовании оптимального кода, о помехоустойчивых кодах). Восстановление потерянной информации в канале с шумом. Бит четности. Коды Хэмминга. Расстояние в коде Хэмминга. Понятие о компьютерной криптографии. Понятие сложности алгоритма. Оценка сложности алгоритма (асимптотические оценки О(n)). Классы сложности алгоритмов: полиномиальные и неполиномиальные алгоритмы. Не полиномиальные алгоритмы (NP задачи). Понятие о теореме полноты класса NP задач. Пример NP задачи (задача коммивояжера, задача разложения на простые сомножители и т.д.).

Информация и ее виды. Дискретная и непрерывная информация. Измерение информации. Вероятностный и объемный подход к измерению информации. Формулы Шеннона и Хартли. Сжатие информации. Основные алгоритмы сжатия информации.

Понятие информации и ее виды. Дискретная и непрерывная информация. Измерение информации. Вероятностный и объемный подход к измерению информации. Формулы Шеннона и Хартли вычисления объема информации. Сжатие информации. Основные алгоритмы сжатия информации (методы Шеннона-Фано, Хафмена и Лепел-Зива).