Раздел 4. Основы информатики

4.1 Алгоритм и алгоритмическая система.

Понятие алгоритма. Свойства алгоритмов. Понятие алгоритмической системы. Основные этапы разработки алгоритмов. Приближенный алгоритм.

4.2 Формы представления алгоритмов. Графическое представление алгоритмов.

Формы представления алгоритмов: словесно-формульная запись, графическое представление, с помощью языков программирования и с использованием псевдоязыков. Алгоритмические языки. Понятие схемы. Понятие блока. Свойства записи алгоритма с помощью блок-схем. Условные и безусловные блоки. Основные блоки, их значение.

4.3 Формы представления алгоритмов. Понятие псевдокода. Школьный алгоритмический язык.

Формы представления алгоритмов: словесно-формульная запись, графическое представление, с помощью языков программирования и с использованием псевдоязыков. Алгоритмические языки. Понятие псевдокода. Школьный алгоритмический язык. Основные управляющие конструкции. Правила записи алгоритма на псевдокоде.

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

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

4.5 Структурная схема алгоритмов. Операционная схема структурированной схемы алгоритмов.

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

4.6 Машина Тьюринга.

Понятие машины Тьюринга. Устройство машины Тьюринга. Принцип работы машины Тьюринга. Конфигурация машины Тьюринга. Построение машины Тьюринга. Графическое представление команд машины Тьюринга. Пример реализации машины Тьюринга.

4.7 Машина Поста.

Понятие машины Поста. Устройство машины Поста. Принцип работы машины Поста. Конфигурация машины Поста. Пример реализации машины Поста.

4.8 Алгоритм Маркова.

Нормальный алгоритм Маркова. Способ задания нормального алгоритма Маркова. Универсальный алгоритм. Формализация понятия нормального алгоритма Маркова. Способы композиции нормальных алгоритмов.

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

Понятие рекурсии. Понятие частичной рекурсии. Рекурсивные функции.

Литература:

1. Давыдов В.Г.. Программирование и основы алгоритмизации. – М.: Высшая школа, 2005.

2. Информатика /Под ред. П.П. Беленького. – Ростов н/Д: Феникс, 2003.

2. Симонович С.В. Информатика, базовый курс. – СПб.: Питер, 2006. – 639 с.

3. Карпов Ю.Г. Основы построения трансляторов. – СПб: БХВ-Петербург, 2005.

Образец билета

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«Камчатский государственный университет имени Витуса Беринга»

2015-2016 учебный год

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

по направлению подготовки 010400.62 «Прикладная математика и информатика»

БИЛЕТ № 1

1. Моменты случайных величин.

2. Языки и цепочки символов. Способы задания языков. Понятие языка, алфавита. Терминальные, нетерминальные символы. Цепочка символов. Пустая цепочка. Способы задания языков.

3. Практическое задание по математике.

4. Практическое задание по информатике.

Заведующий кафедрой математики и физики А.С. Пережогин

Заведующий кафедрой информатики И.А. Кашутина

Образец задания

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«Камчатский государственный университет имени Витуса Беринга»

2015-2016 учебный год

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

по направлению подготовки 010400.62 «Прикладная математика и информатика»

БИЛЕТ № 1

Задача

· Написать программу для вычисления суммы N членов последовательности чисел F(i+1) = F(i) + F(i-1), где F(0)=0, F(1)=1.

· Найти собственные значения и собственные векторы линейного оператора и записать матрицу линейного оператора в базисе из собственных векторов:

Заведующий кафедрой математики и физики А.С. Пережогин

Заведующий кафедрой информатики И.А. Кашутина