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

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

Адрес e-mail:

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

 

 

ПРОГРАММА

  • по курсу: ОСНОВЫ ИНФОРМАТИКИ (АЛГОРИТМЫ И АЛГОРИТМИЧЕСКИЕ ЯЗЫКИ). Продвинутый курс
  • по направлению: 010900 «Прикладные математика и физика»
  • Факультеты: ФРТК, ФОПФ, ФАКИ, ФМБФ, ФФКЭ, ФАЛТ, ФУПМ
  • Кафедра: информатики
  • Kypc: I
  • Семестр: 1
  • Трудоемкость: базовая часть - 3 зач. ед.; вариативная часть - 2 зач. ед., в т.ч. по выбору студента - 1 зач. ед.:
  • Лекции:   34 часа
  • Семинарские занятия:   34 часа
  • Лабораторные занятия: 34 часа
  • ВСЕГО : 102 часа

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

академик РАН В. П. Иванников,
доцент, к.ф.-м.н. А. В. Ворожцов

Программа обсуждена на заседании кафедрыинформатики 21 мая 2010 г.

Заведующий кафедрой                    д.ф.-м.н., профессор И. Б. Петров

 

Скачать версию с программой и заданиями (PDF, 231 Кб)

 

Введение в теорию алгоритмов.

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

Алгоритмические языки.

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

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

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

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

Файлы. Стандартные функции ввода-вывода. Простые и сложные операторы. Пустой, составной, услов-
ный операторы. Оператор варианта. Оператор перехода.

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

Составные типы данных. Массивы.

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

Ссылочный тип данных. Методы выделения памяти: статический, динамический и автоматический.

Алгоритмы и структуры данных.

Абстрактные структуры данных: стек, очередь, очередь с приоритетом,

ассоциативный массив. Отображение абстрактных структур данных на структуры хранения: массивы, списки, деревья. Различные реализации ассоциативного массива: двоичные деревья поиска (АВЛ-деревья, красно-чёрные деревья), перемешанные таблицы (с прямой и открытой адресацией, использование техники двойного хэширования при открытой адресации). Оценки алгоритмической сложности операций поиска, добавления и удаления элемента.

Классические алгоритмы: перебор с возвратом, жадные алгоритмы, динамическое программирование.

Этапы разработки программ.

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

 

Учебно-методическое и информационное обеспечение дисциплины

Основная литература

1. Воролщов А. В., Винокуров Н. А. Практика и теория программирования. - М.: Физматкнига, 2008.
2. Керниган Б. У., Ритчи Д. М. Язык программирования С. - 2-е издание. - М.: Издательский дом «Вильяме», 2006.

Дополнительная литература

1. Кормен Т. X., Лейзерсон Ч. И., Ривест Р. Л., Штагич К. Алгоритмы: построение и анализ.- 2-е изд. - М.: Издательский дом «Вильяме», 2006.
2. Шилдт Г. Полный справочник по С. - М.: Издательский дом «Вильямс», 2005.
3. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. - М.: Издательский дом «Вильяме», 2000.
4. Вирт Н. Алгоритмы и структуры данных. - СПб.: Невский Диалект. 2005.
5. Седжвик Р. Фундаментальные алгоритмы на С. - СПб.:ООО «ДиаСофтЮП», 2003.
6. Митницкий В. Я. Элементы теории алгоритмов и язык программирования С. - М.: МФТИ, 2001.

Пособия и методические указания

1. Прут В. В. Введение. Целые и рациональные числа: методические указания к практикуму по курсу Основы информатики. -М.: МФТИ, 2002.
2 Прут В. В. Матрицы. Геометрия. Фракталы. Игры: методические указания к практикуму по курсу Основы информатики. -М.: МФТИ, 2002.
3. Прут В. В. Математическая логика. Теория алгоритмов. Рекурсия. Сортировка. Графы: методические указания к практикуму по курсу Основы информатики. - М.: МФТИ, 2002.

Электронные ресурсы

1. http://cs.mipt.ru
2. http://acm.mipt.ru

Если вы заметили в тексте ошибку, выделите её и нажмите Ctrl+Enter.

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

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

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

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