Программа дисциплины «Информатика и программирование»

Вид материала

Программа дисциплины

Содержание Цель дисциплины Итоговый контроль Тема 2. Машины Тьюринга Тема 3. Нормальные алгорифмы Маркова Тема 7. Развитие понятия алгоритма Тема 8. Понятие сложности алгоритма и классы сложности задач Тема 10. Способы описания алгоритмических языков Раздел 3. РЕКУРСИВНЫЕ ДАННЫЕ И АЛГОРИТМЫ Тема 12. Операции над линейными списками Тема 13. Операции над бинарными деревьями Тема 14. Представление графов и операции над графами Тема 19. Внешние сортировки Тема 20. Поиск и хеширование Раздел 6. ЯЗЫКИ ПРОГРАММИРОВАНИЯ И МЕТОДЫ ТРАНСЛЯЦИИ Тема 22. Методы трансляции программ Тема 2. Основы программирования на языке Pascal (8 ч.) Тема 3. Тестирование и отладка программ (4 ч.) Тема 4. Методы разработки алгоритмов, рекурсия и итерация (8 ч.) Тема 5. Ввод/вывод и работа с файлами (4 ч.) Тема 7. Рекурсивные типы данных и динамическое распределение памяти (16 ч.) ... Полное содержание

Подобный материал:

• Программа дисциплины "Программирование" для направления, 488.76kb.
• Программа дисциплины по кафедре Прикладная математика т информатика алгоритмические, 564.02kb.
• Программа дисциплины «Введение в программирование»  для направления 080700 «Бизнес-информатика», 101.22kb.
• Рабочая программа дисциплины «Информатика и программирование» Направление подготовки, 282.17kb.
• Программа учебной дисциплины «Информатика и программирование» Программа дисциплины, 135.24kb.
• Рабочая программа для направления (специальности), 175.95kb.
• Программа дисциплины Информатика и программирование для направления 080700 «Бизнес-информатика», 272.37kb.
• Рабочая программа дисциплины информатика и программирование ен., 337.93kb.
• Рабочая программа дисциплины информатика направление ооп, 210.09kb.
• Рабочая программа по дисциплине "алгоритмизация и программирование" для специальности, 140.41kb.

Г О С У Д А Р С Т В Е Н Н Ы Й У Н И В Е Р С И Т Е Т

ВЫСШАЯ ШКОЛА ЭКОНОМИКИ
ПЕРМСКИЙ ФИЛИАЛ

Программа дисциплины

«Информатика и программирование»

для направления 080700.62 – Бизнес-информатика
(вторая ступень высшего профессионального образования)

Утверждена Учебно-методическим Советом ПФ ГУ-ВШЭ Председатель______________ Володина Г.Е. «_______»_________________________2009 г.

Одобрена на заседании кафедры информационных технологий в бизнесе Зав. кафедрой_______________Казаченко Т.А. «______»__________________________2009 г.

Пермь 2009

1. Обязательный минимум содержания дисциплины по ГОС
   

   ЕН.Ф.06	Информатика и программирование
   Основные этапы компьютерного решения задач; критерии качества программы; диалоговые программы; дружественность; постановка задачи и спецификация программы; способы записи алгоритма; программа на языке высокого уровня; стандартные типы данных; представление основных структур: итерации, ветвления, повторения; процедуры: построение и использование; типы данных, определяемые пользователем; записи; файлы; динамические структуры данных; списки: основные виды и способы реализации; программирование рекурсивных алгоритмов; способы конструирования программ; модульные программы; основы доказательства правильности; архитектура и возможности семейства языков высокого уровня. Нелинейные структуры данных: классификация; деревья: ориентированные, упорядоченные и бинарные; представление деревьев в памяти компьютера: последовательное и связанное размещение элементов; операции над деревьями; графы и их представление в компьютере; алгоритмы, оперирующие со структурами типа графа; задачи поиска; исчерпывающий поиск: перебор с возвратом, метод ветвей и границ, динамическое программирование; быстрый поиск: бинарный и последовательный поиски в массивах, хеширование; использование деревьев в задачах поиска: бинарные, случайные бинарные, оптимальные и сбалансированные деревья поиска; алгоритмы поиска на графах; задачи сортировки; внутренняя и внешняя сортировки; алгоритмы сортировки; анализ сложности и эффективности алгоритмов поиска и сортировки; файлы: организация и обработка, представление деревьями: B-деревья; теория сложности алгоритмов: NP-сложные и труднорешаемые задачи. Языки программирования и методы трансляции: основные понятия языков программирования; синтаксис, семантика, формальные способы описания языков программирования; типы данных, способы и механизмы управления данными; методы и основные этапы трансляции; конструкции распределенного и параллельного программирования.

2. Пояснительная записка
   

1. Авторы программы: Л.Н. Лядова (к.ф.-м.н., доцент), М.А. Плаксин (к.ф.-м.н., доцент)
   
2. Требования к студентам:
   

Приступая к изучению данной дисциплины, студент должен обладать знаниями информатики в объеме общеобразовательной школы.

3. Аннотация:
   

Программа составлена в соответствии с требованиями ГОС к обязательному минимуму содержания основной образовательной программы подготовки бакалавра бизнес-информатики.

Дисциплина «Информатика и программирование» относится к циклу «Общие математические и естественно-научные дисциплины».

Цель дисциплины – дать фундаментальную подготовку, необходимую для успешного освоения как общепрофессиональных, так и специальных дисциплин, изучение которых связано с применением средств информационно-коммуникационных технологий, созданием эффективных алгоритмов, разработкой программного обеспечения для различных предметных областей.

Задачи:

• познакомить студентов с базовыми понятиями информатики и современных информационных технологий;
  
• познакомить с теоретическими основами разработки эффективных алгоритмов и современными средствами разработки программ;
  
• дать навыки практического применения различных методов решения задач с помощью компьютеров;
  
• познакомить с основами организации современных компьютеров, базовыми принципами их функционирования.
  

Курс призван повысить общую эрудицию студентов, показать методы применения алгоритмического подхода в различных, в том числе гуманитарных, областях.

В курсе «Информатика и программирование» изучаются вопросы, касающиеся проблем, связанных с понятием алгоритма, сложности алгоритмов. Изучаются способы формализации алгоритмов, позволяющие изучать их свойства, рассматриваются основные методы разработки алгоритмов и приемы конструирования типов данных, их использования при разработке программ. Вводятся понятия формальных языков и грамматик, изучаются средства формального описания языков программирования, и их возможности для разработки эффективных программ. ЭВМ рассматривается как основной исполнитель алгоритма и как основное устройство хранения, обработки и передачи информации.

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

4. Учебная задача курса:
   

В результате изучения курса студент должен:

• Иметь представление:
  

• о месте информатики среди других дисциплин;
  
• об основных возможностях современных средств программирования;
  
• об организации вычислительного процесса и общих принципах функционирования компьютеров с традиционной архитектурой, а также основных направлениях развития архитектур современных вычислительных систем.
  

• Знать:
  

• основные понятья информатики;
  
• определение, свойства и средства формализации алгоритмов, исследования их свойств, оценки эффективности;
  
• основные управляющие структуры и способы описания алгоритмов;
  
• основные методы разработки алгоритмов, особенности их реализации;
  
• понятие типа данных, форматы представления данных при решении задач с помощью компьютера, а также средства конструирования новых типов на основе стандартных типов, используемых в языках программирования;
  
• основные алгоритмы сортировки и поиска;
  
• динамические типы данных и алгоритмы реализации основных операций над динамическими структурами данных;
  
• основы организации файлов, выполнения операций над файлами, возможности их использования при решении задач;
  
• способы формального описания языков и возможности современных систем программирования;
  
• основы прикладной архитектуры современных персональных компьютеров.
  

• Уметь:
  

• решать задачи, используя различные методы разработки алгоритмов и выбирая наиболее подходящие алгоритмы и средства их реализации в зависимости от постановки задачи;
  
• разрабатывать программы средней сложности на языке Pascal с использованием основных управляющих конструкций, стандартных типов и функций языка;
  
• анализировать алгоритмы и программы, оценивать эффективность алгоритмов и их реализации;
  

• Обладать навыками:
  

• разработки и анализа алгоритмов решения типовых задач, исследования их свойств;
  
• разработки программ средней сложности на языке Pascal, их тестирования и отладки;
  
• самостоятельного решения задач с помощью компьютеров.
  

Студенты после изучения курса должны уметь самостоятельно разрабатывать алгоритмы решения различных задач средней степени сложности, производить оценку временных затрат при выполнении алгоритмов независимо от свойств исполнителя (архитектуры компьютера и языков программирования), а также разрабатывать программы, реализующие алгоритмы, выбирая наиболее эффективные средства реализации. Требуется умение выбирать типы и конструировать структуры данных для решения задач для тех предметных областей, для которых разрабатываются алгоритмы. Студенты должны представлять, как происходит исполнение их программ на ЭВМ различной архитектуры.

5. Формы контроля:
   

• Текущий контроль: выполнение лабораторных работ сопровождается проведением контрольных опросов, согласно графику контрольных мероприятий выполняются домашние задания и контрольные работы.
  
• Итоговый контроль: зачет проводится в соответствии с учебным планом в конце второго модуля. Изучение дисциплины завершается сдачей экзамена. Итоговая оценка: складывается в соответствии с «Положением о рейтинге», принятом в ПФ ГУ-ВШЭ. Формы проведения определяются учебным планом.
  

3. Содержание программы
   

Темы лекций

Раздел 1. ОСНОВЫ АЛГОРИТМИЗАЦИИ

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

Интуитивное понятие алгоритма. Свойства алгоритмов. Понятие об исполнителе алгоритма. Уточнение понятия алгоритма. Способы записи алгоритмов.

Тема 2. Машины Тьюринга

Алгоритм как преобразование слов из заданного алфавита. Машина Тьюринга. Формат команды и программа машины Тьюринга. Способы записи программы: таблицы, диаграммы. Примеры. Композиция машин Тьюринга. Примеры. Тезис Тьюринга и его обоснование.

Тема 3. Нормальные алгорифмы Маркова

Нормальные алгоритмы Маркова. Формулы подстановки и схемы. Выполнение алгорифма. Примеры. Принцип нормализации и его обоснование.

Тема 4. Вычислимые функции

Понятие вычислимой функции. Суперпозиция, примитивная рекурсия, минимизация. Примеры.

Тема 5. Алгоритмическая неразрешимость

Понятие об алгоритмической неразрешимости. Доказательство существования алгоритмически неразрешимых задач. Примеры.

Тема 6. Методы разработки алгоритмов

Основные методы разработки алгоритмов. Рекурсия и математическая индукция. Реализация механизма рекурсии. Рекурсия и итерация. Реализация. Сравнение.

Тема 7. Развитие понятия алгоритма

Развитие понятия алгоритма: параллельное программирование и распределенные алгоритмы, объектно-ориентированный подход к разработке программ, методы искусственного интеллекта. Конструкции языков высокого уровня для организации ветвлений и циклов, конструкции распределенного и параллельного программирования.

Тема 8. Понятие сложности алгоритма и классы сложности задач

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

Разрешимые и неразрешимые задачи. Сложность задачи. Задачи полиномиальной и экспоненциальной сложности (труднорешаемые задачи). Сводимость и другие классы сложности. Класс задач NP, NP-сложные и NP-полные задачи. Примеры.

Раздел 2. ФОРМАЛЬНЫЕ ЯЗЫКИ И ГРАММАТИКИ

Тема 9. Формальные языки и понятие грамматики

Понятие о формальных языках. Основные понятия: алфавит, лексика, синтаксис и семантика, прагматика языка. Понятие грамматики. Классификация формальных языков.

Тема 10. Способы описания алгоритмических языков

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

Раздел 3. РЕКУРСИВНЫЕ ДАННЫЕ И АЛГОРИТМЫ

Тема 11. Рекурсивные данные

Конструирование типов. Понятие рекурсивно определенного типа данных и динамическое распределение памяти. Линейные списки, деревья, графы: определение и способы представления.

Тема 12. Операции над линейными списками

Создание списков, включение элементов в голову и конец списка, на указанное место. Просмотр списков. Поиск элемента в списке. Удаление элемента списка. Сравнение списков.

Тема 13. Операции над бинарными деревьями

Создание деревьев, включение элементов в бинарное древо. Просмотр деревьев и поиск элементов. Удаление элемента списка. Сравнение деревьев. Применение бинарных деревьев в программировании.

Тема 14. Представление графов и операции над графами

Способы представления графов. Сравнение. Создание графа (добавление вершин и дуг). Поиск вершины и дуги. Удаление вершин и дуг. Алгоритмы на графах.

Раздел 4. ФАЙЛЫ: ОРГАНИЗАЦИЯ И ОБРАБОТКА

Тема 15. Понятие файла

Понятие файла, способы организации файлов, физическая и логическая организация. Файловые системы, примеры.

Тема 16. Операции над файлами

Операции над файлами. Особенности работы с текстовыми и бинарными файлами. Примеры использования файлов.

Раздел 5. СОРТИРОВКА И ПОИСК

Тема 17. Основные понятия, задачи сортировки и поиска

Формулировка задач сортировки и поиска. Основные понятия. Связь между задачами.

Тема 18. Сортировка массивов

Основные подходы к разработке алгоритмов сортировки массивов, классификация алгоритмов сортировки. О(n) алгоритмы сортировки (например, выбором и вставкой); оценки сложности, лучшие и худшие случаи. О(n log n) алгоритмы сортировки (например, быстрая сортировка, метод слияния); оценка сложности; другие методы сортировки (метод Шелла и т.д.); сравнение алгоритмов сортировки.

Тема 19. Внешние сортировки

Понятие файла. Представление деревьями, В-деревья.

Особенности сортировки файлов. Общие подходы и основные методы сортировки файлов (двухпутевое слияние, фибоначчиева сортировка и пр.).

Тема 20. Поиск и хеширование

Подходы к решению задач поиска. Последовательный и бинарный поиск, оценки сложности, лучшие и худшие случаи. Поиск в массивах. Использование деревьев в решении задач поиска. Исчерпывающий поиск: перебор с возвратом, метод ветвей и границ, динамическое программирование.

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

Раздел 6. ЯЗЫКИ ПРОГРАММИРОВАНИЯ И МЕТОДЫ ТРАНСЛЯЦИИ

Тема 21. Языки программирования

Основные понятия и классификация языков программирования. Языки программирования высокого уровня и возможности современных систем программирования. Типы данных, способы и механизмы управления данными. Представление основных структур: итерации, ветвления, повторения. Процедуры и функции: построение и использование, способы передачи параметров. Модульное программирование. Конструкции распределенного и параллельного программирования. Состав систем программирования. Способы конструирования программ и этапы подготовки программ к выполнению.

Тема 22. Методы трансляции программ

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

4. Учебно-методическое обеспечение дисциплины
   

1. Литература:
   

Базовые учебники:

1. Королев Л.Н., Миков А.И. Информатика. Введение в компьютерные науки. М.: Высшая школа, 2009.
   

Основная:

1. Плаксин М.А. Тестирование и отладка программ – для профессионалов будущих и настоящих. М.: БИНОМ. Лаборатория базовых знаний, 2007.
   
2. Залогова Л.А. Разработка Паскаль-компилятора. М.: БИНОМ. Лаборатория базовых знаний, 2007.
   

Дополнительная:

1. Андреева Т.А. Программирование на языке Pascal: Учебное пособие. М.: 2006.-234 с.
   
2. Борисенко В.В. Основы программирования: Учебное пособие. М.: Интернет-университет информационных технологий; МГУ им. М. В. Ломоносова, 2005.-328 с.
   
3. Острейковский В.А. Информатика: Учебник для вузов М.: 2001.-511с.
   
4. Кнут Д.Э. Искусство программирования. (Классический труд. Исправленное и дополненное издание). В 3 х томах. М.: 2004.
   
5. Анисимов А.Е., Пупышев В.В. Сборник заданий по основаниям программирования: Учеб. пособие. М.: 2006. -348 с.
   
6. Пентус А.Е., Пентус М Р. Математическая теория формальных языков: Учеб. пособие / М.: 2006. -247 с.
   
7. Васильев П.П. Турбо Паскаль в примерах и задачах: Освой самостоятельно: Учеб.пособие. М.: Финансы и статистика, 2002. 496 с.
   
8. Конспект лекций по курсу «Информатика и программирование». М.: ГУ-ВШЭ.[Электронный ресурс]
   
9. Основы алгоритмизации и программирования. [Электронный ресурс]
   

2. Тематика заданий по различным формам текущего контроля:
   

Тематика контрольных работ:

1. Теоретические основы программирования.
   
2. Оценка сложности и способы записи алгоритмов.
   
3. Основные алгоритмы и структуры данных.
   

Перечень примерных заданий представлен в приложении.

Тематика домашних заданий:

1. Основы программирования на языке Pascal: массивы, строки, записи, рекурсия и итерация.
   
2. Рекурсивные типы данных и динамическое распределение памяти.
   
3. Сортировка и поиск.
   

Перечень примерных заданий представлен в приложении.

Перечень вопросов для самоконтроля студентов:

Перечень вопросов для самоконтроля студентов представлен в приложении.

Тематика практических занятий:

Примерный перечень заданий, выполняемых на практических занятиях приведен в приложении.

План практических занятий

Тема 1. Решение задач с помощью компьютера (2 ч.)

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

Тема 2. Основы программирования на языке Pascal (8 ч.)

Лексика языка. Описание синтаксиса языка. Стандартные типы данных. Операции и стандартные функции. Операторы и основные управляющие структуры: итерация, ветвление, повторение. Нисходящее программирование и пошаговая детализация и использование процедур и функции: построение, описание данных, глобальные и локальные переменные, способы передачи параметров. Блочная структура. Понятие типа данных. Классификация языков по типизации. Классификация типов данных. Идентичность типов. Идентичность типов в языке Pascal. Числовые типы. Тип Boolean. Тип Char и тип String. Типы данных, определяемые пользователем: перечисления, диапазоны, множества, массивы, записи, файлы. Типизированные константы. Реализация процедур и функций.

Тема 3. Тестирование и отладка программ (4 ч.)

Принципы тестирования. Полнота тестирования. Критерии черного ящика. Критерии белого ящика. МГТ. Ошибкоопасные ситуации при работе с файлами. Ошибкоопасные ситуации при обращении к данным. Ошибкоопасные ситуации при вычислениях. Ошибкоопасные ситуации при передаче управления и вызовах подпрограмм. Безмашинное тестирование. Оценка количества ошибок в программе. Мера доверия к миллсовой модели оценки количества ошибок в программе. Оценка количества необходимых тестов.

Отладка. Отладочные операторы. Методы поиска ошибки. Принципы отладки. Анализ обнаруженной ошибки. Отладочные средства. Нисходящее программирование и нисходящее тестирование.

Тема 4. Методы разработки алгоритмов, рекурсия и итерация (8 ч.)

Разработка рекурсивных процедур и функций. Вычисление факториала. Последовательность чисел Фибоначчи. Бинарный поиск и решение уравнений методом деления отрезка пополам. Использование процедурных типов.

Тема 5. Ввод/вывод и работа с файлами (4 ч.)

Ввод данных с клавиатуры. Вывод данных на экран.

Файлы. Виды файлов. Методы доступа.

Текстовые файлы. Файлы записей.

Триада для работы с файлом. Синхронизация. Буферизация. Блокирование. Двоичные файлы в Турбо-Паскале. Потоковые файлы в Турбо-Паскале.