Одним из главных принципов уникальной «системы Физтеха», заложенной в основу образования в МФТИ, является тщательный отбор одаренных и склонных к творческой работе представителей молодежи. Абитуриентами Физтеха становятся самые талантливые и высокообразованные выпускники школ всей России и десятков стран мира.

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

Адрес e-mail:

Основы информатики

ПРОГРАММА

по курсу: ОСНОВЫ ИНФОРМАТИКИ (АЛГОРИТМЫ И АЛГОРИТМИЧЕСКИЕ ЯЗЫКИ) по направлению: 511600 Факультеты: ФОПФ, ФМБФ Кафедра: ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ Kypc: I Семестр: 1 Лекции:   34 часа Семинарские занятия:   34 часа Лабораторные занятия: 34 часа ВСЕГО : 102 часа

Программу составил:

чл.– корреспондент РАН, профессор В.П. Иванников, к.ф.– м.н., доцент В.М. Абрамов д.ф.– м.н., профессор В.Я. Митницкий

Программа обсуждена на заседании кафедры вычислительной математики 13 апреля 2001 г.

Заведующий кафедрой                     проф. А.С. Холодов


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

Алгоритмическая сложность. Связь понятия алгоритма с понятием функции.

Характеристика алгоритмических языков и их исполнителей. Понятие трансляции.

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

Язык программирования. Общие характеристики языков программирования. Алфавит, имена, служебные слова, стандартные имена, числа, текстовые константы, разделители. Структура программы на Паскале. Заголовок программы. Блок.

Типы данных, их классификация. Переменные и константы. Скалярные типы данных и операции над ними, старшинство операций, стандартные функции. Выражения и правила их вычисления. Оператор присваивания. Перечисляемые  и ограниченные типы данных.

Простые и сложные операторы. Пустой, составной, условный операторы и оператор перехода. Метки. Оператор варианта.

Файлы. Стандартные процедуры и функции ввода – вывода.

Операторы цикла. Программирование рекуррентных соотношений. Составные типы данных. Массивы.

Описание процедуры и оператор процедуры. Формальные и фактические параметры. Способы передачи параметров. Локализация имен, разрешение коллизий. Функции, побочные эффекты.

Итерации и рекурсии.

Комбинированный тип. Оператор присоединения. Множества. Ссылочный тип данных. Динамические переменные.

Структура данных. Абстрактные структуры: графы, деревья, таблицы. Отношения. Отображение абстрактных структур данных на структуры хранения: векторная память, списки. Стеки и очереди.

Таблицы. Последовательные таблицы. Деревья сравнений. Перемешанные таблицы. Оценки алгоритмической сложности. Классические алгоритмы. Этапы разработки программ.

 

СПИСОК ЛИТЕРАТУРЫ

Любимский Э.З., Мартынюк В.В., Трифонов Н.П. Программирование. М.: Наука, 1980. Минский М. Вычисления и автоматы, М.: Мир, 1971. Вирт И., Йенсен К. Паскаль. Руководство для пользователя и описание языка. М.: Финансы и статистика, 1989. Абрамов В.Г., Трифонов Н.П., Трифонова Г.Н. Введение в язык Паскаль. М.: Наука, 1988. Вирт Н. Агоритмы+структура данных = программа. М.: Мир, 1985. Кнут Д. Искусство программирования. Основные алгоритмы. Т.1. Сортировка и поиск. Т.2. М.: Наука, 1985. Сибуя М., Ямомото Т. Алгоритмы обработки данных. Мир, 1985. Столяров Л.Н., Абрамов В.М. Начала информатики. От задачи к программе. М.: МФТИ. 1991г. Корухова Л.С., Шура-Бура М.Р. Введение в алгоритмы. М.: Изд. отд. фак. ВмиК МГУ, 1997 г.
Если вы заметили в тексте ошибку, выделите её и нажмите Ctrl+Enter.

© 2001-2016 Московский физико-технический институт
(государственный университет)

Техподдержка сайта

МФТИ в социальных сетях

soc-vk soc-fb soc-tw soc-li soc-li
Яндекс.Метрика