Главная страница новости/обновления о создании страницы О кафедре общая информация история кафедры сотрудники Для студентов учебный план виды дисциплин рабочие программы расписания занятий задания для сам-х. работ конспекты лекций электронные учебники методические материалы Для абитуриентов методические пособия направления обучения о специальности Научная работа научные направления научные труды научные проекты диссертации научные связи	... информатика	Фото галерея общие фото личные фото Сервис... сделать домашней в избранное гостевая Ссылки Статистика посещений
	Примерная программа дисциплины ИНФОРМАТИКА (ВВЕДЕНИЕ В КОМПЬЮТЕРНЫЕ НАУКИ) Рекомендуется Минобразованием России для специальности (направления) подготовки 010200 Прикладная математика и информатика (510200 Прикладная математика и информатика) ЦЕЛЬ И ЗАДАЧИ КУРСА Цель курса - ввести в круг понятий и задач информатики, связанных с проблемами обработки данных с помощью вычислительных машин. Задача курса - дать представление об алгоритмизации, о формальном представлении алгоритмов, их сложности, привести примеры классических алгоритмов обработки данных, дать понятия о формальных языках задания для сам-х. работ алгоритмов, об ЭВМ, как исполнителях алгоритмов. ВВЕДЕНИЕ В ТЕОРИЮ АЛГОРИТМОВ Интуитивное понятие алгоритма. Свойства алгоритмов. Понятие об исполнителе алгоритма.Уточнение понятия алгоритма. Алгоритм как преобразование слов из заданного алфавита. Машина Тьюринга. Тезис Тьюринга и его обоснование. Нормальные алгоритмы Маркова. Принцип нормализации и его обоснование. Понятие об алгоритмической неразрешимости. РЕКУРСИВНЫЕ АЛГОРИТМЫ Понятие и применение рекурсивных алгоритмов при решении задач. Связь с математической индукцией; сравнение рекурсивных и итеративных алгоритмов. Анализ сложности алгоритмов. Понятие вычислительной сложности (по времени и памяти). И его применение для анализа алгоритмов. Асимптотические верхние и средние оценки для итеративных и рекурсивных алгоритмов; сравнение алгоритмов по времени и памяти. КЛАССЫ СЛОЖНОСТИ Обзор классов сложности (P и NP), верхние, средние и нижние оценки. P и NP классы сложности; разрешимые м неразрешимые задачи. NP-полнота. СОРТИРОВКА И ПОИСК О (n ) алгоритмы сортировки (например, выбором и вставкой); оценки сложности, лучшие и худшие случаи. О(n log n) алгоритмы сортировки (например, быстрая сортировка, метод слияния); оценка сложности; другие методы сортировки (метод Шелла и т.д.); сравнение алгоритмов сортировки. Последовательный и бинарный поиск, поиск в двоичном дереве; оценки сложности, лучшие и худшие случаи; хэширование, устранение коллизий. ФОРМАЛЬНЫЕ ЯЗЫКИ Понятие о формальных языках. Способы строгого описания формальных языков, понятие о метаязыках. Алфавит, синтаксис и семантика алгоритмического языка. Описание синтаксиса языка с помощью металингвистических формул и синтаксических диаграмм. СИСТЕМЫ УРАВНЕНИЙ Система уравнений первого порядка. Система уравнений высших порядков. Каноническая система уравнений высших порядков. Автономная система и ее свойства. Динамические системы, связь между фазовыми кривыми и интегральными кривыми, автономные динамические системы, фазовая плоскость, интегральные многообразия. Системы в симметрической форме. АРХИТЕКТУРА ЭВМ Типовая схема ЭВМ, принципы Фон-Неймана. Оперативная память: ячейка, адрес, бит, слово. Характеристики и единицы измерения памяти. Команды и данные. Центральный процессор ЭВМ: устройство управления и арифметико-логическое устройство. Регистры. Устройство ввода/вывода. Схема выполнения команд. Понятие такта работы. Понятие о структурных особенностях современных ЭВМ: прерывания, защита памяти, привилегированные команды, параллельная обработка данных. Основы программирования на вычислителях с параллельной и распределенной архитектурой; иллюстрация того, как параллелизм значительно ускоряет вычисления по сравнению с последовательными алгоритмами, простые параллельные алгоритмы. Методы автоматизации распараллеливания программ и векторизации циклов. Ярусно-параллельные формы. Методы гиперплоскостей, параллелепипедов и т.д. РАСПРЕДЕЛЕНИЕ ЧАСОВ КУРСА ПО ТЕМАМ И ВИДАМ РАБОТ № Наименование тем и разделов Всего (часов) Аудиторные занятия (часов) Самостоятельная работа (часов) 1 Введение в теорию Алгоритмов 15 10 5 2 Рекурсивные алгоритмы.Классы сложности 48 32 16 3 Сортировка и поиск.Компьютерная графика. 32 22 10 4 Формальные языки 24 16 18 5 Архитектура ЭВМ 24 16 8 = ИТОГО 143 96 47 Примечание:Во всех разделах таблицы указано минимальное число часов, необходимое для усвоения соответствующего раздела. Оставшиеся часы используются в рабочей программе для более глубокого изложения отдельных разделов курса. Форма итогового контроля - экзамен, зачет ЛИТЕРАТУРА Основная Вирт Н. Алгоритмы+структура данных=программа. Мир, 1985. Ларионов А.М., Майоров С.А., Новиков Г.И. Вычислительные комплексы, системы, сети. Л., Энергоатомиздат, 1987. Воеводин В.В. Математические модели и методы в параллельных процессах. М.: Наука, 1986. Хоггер К. Введение в логическое программирование. М.: Мир, 1988. Элементы теории графов и схем - составители В.Б.Алексеев, С.А.Ложкин. Методическое пособие. М.: МГУ, 1991. Трахтенгерц Э.А. Введение в теорию анализа и распараллеливания программ ЭВМ. М.: Наука, 1981. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Мир, 1999. Голдблатт Р. Логика времени и вычислимость. М.: Мир, 1993. Список дополнительной литературы устанавливается кафедрой. Программа составлена Советом по программированию факультета вычислительной математики и кибернетики Московского университета под общей редакцией чл.-корр. РАН Л.Н.Королева. Рецензент: профессор А.В.Миков (Пермский государственный университет).
Используйте Internet Explorer 5 Flash Player 5 WebMaster | PageMaker