Международный Институт XXI Века

�Алгоритмизация и Языки Программирования�

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

Москва -2005 г.

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

Авторы программы:

Программа разработана на кафедре информатики. Автор программы: к.т.н., снс, профессор Биллиг В.А

Требования к студентам:

Дисциплина базируется на знании студентов основ информатики в следующем объеме:

-         - знание понятий информатики;

-         знание приемов пользовательской работы в среде MS Office;

-         знание основ программирования на языке Visual Basic.

Аннотация

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

Курс предполагает практическую работу на языке C# в среде разработки Visual Studio .Net

Дисциплина изучается на втором курсе.

Цель изучения дисциплины:

�        дать студентам общее представление о понятиях языков программирования и объектно-ориентированной технологии разработки программных систем;

�        дать общее представление об алгоритмизации и сложности алгоритмов;

�        научить создавать программы в объектном стиле на языке C#;

�        научить работать в среде Visual Studio .Net;

�        научить классическим алгоритмам, предназначенным для работы со сложными структурами данных.  

Дисциплина рассчитана на 60 учебных часов, которые включают в себя лекционную часть (36 часов) и практическую работу в компьютерном зале           (36 часов), а также 50 часа самостоятельных занятий.

Учебная задача дисциплины.

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

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

�         об основных понятиях алгоритмизации и программирования;

знать:

�         основные алгоритмы

�         как создаются программные проекты,

уметь:

�         создавать программные проекты;

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

�         работы в программной среде Visual Studio .Net.

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

�          текущий контроль проводится на каждом практическом занятии;

�         промежуточный контроль: проверка домашних заданий, тестирование;

�         итоговый контроль: итоговый тест, зачет и экзамен по курсу.

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

II. Тематический расчет часов

III. Лекции

Все лекции даются студентам в электронном виде. Учебник [1] сейчас печатается и должен выйти в издательстве Интернет-Университет в октябре месяце 2005 года.

IV Вопросы к зачету и экзамену.

Каждая лекция заканчивается тестовыми вопросами (15 вопросов к лекции). Эти вопросы являются основой вопросов для зачета и экзамена.

V Тестирующая система.

Курс поддерживается тестирующей системой на компьютере, позволяющей проводить тестирование, как по отдельным темам, так и по курсу в целом.

Литература

Основная.

1.      Дж. Рихтер.  Программирование на платформе Microsoft. NET Framework (+CD). Питер.

2.      Мейер Б. Объектно-ориентированное конструирование программных систем (+CD).  Русская редакция, 2005.

3.      Петцольд Ч. Программирование для Microsoft Windows на С#.  Русская редакция, 2002.

4.      Петцольд Ч. �Программирование в тональности C#�. Русская Редакция, Москва 2004 г. 

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

1.   В.А. Биллиг �Основы программирования на языке C#�. Интернет-Университет Информационных технологий. Москва 2005 г.

5.      Н. Вирт �Алгоритмы и структуры данных� Мир, Москва, 1989 г. (доступна современная электронная версия этой книги).

6.      А. Ахо, Дж Хопкрофт, Дж. Ульман �Построение и анализ вычислительных алгоритмов�, Мир, Москва, 1989 г. (доступна современная электронная версия этой книги).

Лекция 1. Visual Studio. Net, Framework .Net

Бренд .Net. Visual Studio .Net � открытая среда разработки. Каркас Framework .Net. Библиотека классов FCL � статический компонент каркаса. Общеязыковая исполнительная среда CLR � динамический компонент каркаса. Управляемый код. Общеязыковые спецификации CLS и совместимые модули.

Ключевые понятия: Visual Studio .Net; MSN Messenger .Net; каркас среды � Framework .Net; открытость языков; MSN Messenger .Net; открытость каркаса; открытость языков; библиотека классов FCL; единство каркаса; примитивные типы; встроенные примитивные типы; структурные типы; модульность; среда CLR; MSIL (Microsoft Intermediate Language); управляемый модуль; управляемый код; двухэтапная компиляция; дизассемблер; ассемблер; метаданные; сборщик мусора; выбрасывать исключение; исключительные ситуации; общие системы типов CTS; события; делегаты; управляемые данные; неуправляемые данные; набор общеязыковых спецификаций � CLS; CLS-совместимость; совместимые модули.

Лекция 2. Язык C# и первые проекты

Создание языка. Его особенности. Решения, проекты, пространства имен. Консольные и Windows-приложения C#, построенные по умолчанию.

Ключевые слова: решение (solution); проект (project); пространство имен (namespace); сборка (assembly); стартовый проект; зависимые и независимые проекты; структурированные проекты; консольное приложение; комментарии; теги; атрибуты; экземплярный метод.

Лекция 3. Система типов языка С#

Общий взгляд. Система типов. Типы-значения и ссылочные типы. Встроенные типы. Сравнение с типами C++. Типы или классы? И типы и классы! Преобразования переменных в объекты и vice versa. Операции �упаковать� и �распаковать�. Преобразования типов. Преобразования внутри арифметического типа. Преобразования строкового типа. Класс Convert и его методы. Проверяемые преобразования. Управление проверкой арифметических преобразований.

Ключевые понятия: класс; простой тип; сложный тип; тип, определенный пользователем; статический тип; динамический тип; встроенные типы; типы-значения; значимые типы; ссылочные типы; система типов; фундаментальные типы: логический, символьный, целый, с плавающей точкой, void, указатели, ссылки, массивы, перечисления, структуры, классы; преобразования типов: упаковать; распаковать; неявное преобразование; явное преобразование; проверяемый блок; непроверяемый блок; проверяемое выражение; непроверяемое выражение; отношение наследования; родительский класс; базовый класс; object; потомки; метод; свойства; тэги summary; XML-отчет; согласование по присваиванию; согласование типов; цель; источник; класс Convert; библиотека FCL; исключения; охраняемые блоки; класс Exception.

Лекция 4. Преобразования типов

Преобразования типов. Преобразования внутри арифметического типа. Преобразования строкового типа. Класс Convert и его методы. Проверяемые преобразования. Управление проверкой арифметических преобразований.

Ключевые понятия: неявное преобразование; явное преобразование; проверяемый блок; непроверяемый блок; проверяемое выражение; непроверяемое выражение; отношение наследования; родительский класс; базовый класс; object; потомки; метод; свойства; тэги summary; XML-отчет; согласование по присваиванию; согласование типов; цель; источник; класс Convert; библиотека FCL; исключения; охраняемые блоки; класс Exception, Преобразования значимых типов

Лекция 5. Переменные и выражения

Объявление переменных. Синтаксис объявления. Инициализация. Время жизни и область видимости. Где объявляются переменные? Локальные и глобальные переменные. Есть ли глобальные переменные в C#? Константы.

Ключевые слова: переменная; синтаксис объявления; объявитель; инициализация; объявление с отложенной инициализацией; время жизни; область видимости; поля; глобальные переменные; локальные переменные; конфликт имен; константы.

Лекция 6. Выражения. Операции в выражениях

Построение выражений. Операции и их приоритеты. Описание операций.

Ключевые слова: выражение; приоритет операций; таблица приоритетов; перегрузка операций; операция увеличить; операция уменьшить; операция sizeof; операция typeof; метод Parse; операция new; арифметические операции; операции отношения; операции сдвига; логические выражения; логические операции; условное выражение; приведение к типу.

Лекция 7. Присваивание и встроенные функции

Присваивание. Новинка C# � определенное присваивание. Классы Math, Random и встроенные функции.

Ключевые слова: присваивание; определенное присваивание; встроенные классы; встроенные функции; класс Math; класс Random.

Лекция 8. Операторы языка C#

Операторы языка C#. Оператор присваивания. Составной оператор. Пустой оператор. Операторы выбора. If-оператор. Switch-оператор. Операторы перехода. Оператор goto. Операторы break, continue. Операторы цикла. For-оператор. Циклы while. Цикл foreach.

Ключевые слова: присваивание; оператор присваивания; блок; составной оператор; пустой оператор; операторы выбора; оператор if; оператор switch; операторы перехода; оператор goto; операторы цикла; оператор for; циклы While; цикл foreach.

Лекция 9. Процедуры и функции � методы класса

Процедуры и функции � две формы функционального модуля. Чем отличаются эти формы? Процедуры и функции � это методы класса. Описание методов (процедур и функций). Синтаксис. Атрибуты доступа. Статические и динамические методы. Формальные аргументы. Статус аргументов. Тело методов. Вызов процедур и функций. Фактические аргументы. Семантика вызова. Поля класса или аргументы метода? Поля класса или функции без аргументов? Проектирование класса Account. Функции с побочным эффектом. Перегрузка методов.

Ключевые слова: процедуры; функции; класс; библиотеки классов; отсутствие результата; входные и выходные аргументы; описание заголовка; описание тела; сигнатура метода; метод открыт; метод закрыт; произвольное число фактических аргументов; params; входные, выходные и обновляемые параметры; блок; return(выражение); вызов метода; соответствие списков формальных и фактических аргументов; ref; out вызов по ссылке; вызов по значению; поля класса или функции без аргументов; функция с побочным эффектом; перегрузка.

Лекция 10. Корректность методов. Рекурсия

Корректность метода. Спецификации. Триады Хоара. Предусловие метода. Постусловие метода. Корректность метода по отношению к предусловию и постусловию. Частичная корректность. Завершаемость. Полная корректность. Инвариант цикла. Вариант цикла. Подходящий инвариант. Корректность циклов. Рекурсия. Прямая и косвенная рекурсия. Стратегия �разделяй и властвуй�. Сложность рекурсивных алгоритмов. Задача �Ханойские башни�. Быстрая сортировка Хоара.

Ключевые слова: корректность; частичная корректность; полная корректность; доказательство корректности; инвариант; вариант цикла; корректность цикла; рекурсия; рекурсивный метод.

Лекция 11. Массивы языка C#

Общий взгляд на массивы. Сравнение с массивами C++. Почему массивы C# лучше, чем массивы C++. Виды массивов � одномерные, многомерные и изрезанные. Динамические массивы.

Ключевые слова: массив; размерность массива; граничная пара; нижняя граница; верхняя граница; 0-базирование; статические массивы; динамические массивы; класс-массив; многомерный массив; массив массивов; общий взгляд; изрезанные массивы.

Лекция 12. Класс Array и новые возможности массивов

Семейство классов-массивов. Родительский класс Array и наследуемые им интерфейсы. Новые возможности массивов в C#. Как корректно работать с массивами объектов?

Ключевые слова: класс System.Array; интерфейсы: ICloneable, IList, ICollection, IENumerable; коллекция; отношение наследования; статические методы: Copy, IndexOf, LastIndexOf, Reverse, Sort, BinarySearch; сортировка и поиск; преобразования; массивы объектов;

Лекция 13. Символы и строки постоянной длины в C#

Общий взгляд. Строки в C++. Строки в C#. Строки постоянной и переменной длины. Классы char, char[].

Ключевые слова: строки. С; символьный класс char; класс char[]; строки постоянной длины; тип char*.

Лекция 14. Строки C#. Классы String и StringBuilder

Строки C#. Класс String. Изменяемые и неизменяемые строковые классы. Классы Net Framework, расширяющие строковый тип. Класс StringBuilder.

Ключевые слова: класс string; @-константы; неизменяемый (immutable) класс; метод Format; формат; динамический метод Split; статический метод Join; строковый класс StringBuilder; емкость объекта.

Лекция 15. Регулярные выражения

Регулярные выражения. Пространство RegularExpressions и его классы. Регулярные выражения и языки. Теория регулярных выражений. Практика применения регулярных выражений. Разбор текстов и поиск по образцу. Свойства и методы класса Regex и других классов, связанных с регулярными выражениями. Примеры применения регулярных выражений.

Ключевые слова: регулярные выражения; пространство имен RegularExpression; итерация языка; регулярное множество; класс Regex; метод Match; коллекция MatchCollection; класс Match; группы; класс Group.

Лекция 16. Классы

Две роли класса в ООП. Синтаксис описания класса. Поля и методы класса. Конструкторы и деструкторы. Статические поля и методы. Статические конструкторы. Поля только для чтения. Закрытые поля. Стратегии доступа к полям класса. Процедуры свойства. Индексаторы. Примеры.

Ключевые слова: класс � это тип данных; класс � это модуль; проектирование от данных; синтаксис описания класса; поля класса; свойства объектов класса; модификатор доступа; методы класса; закрытые методы; методы-свойства; синтаксис методов-свойств; индексатор; операции; бинарная или унарная операция; статические поля; статические методы; константы; конструкторы класса; деструкторы класса; атрибут readonly.

Вопросы для экзамена по курсу �Алгоритмизация и языки программирования�

1.      Языки программирования Visual Studio .Net

2.      Библиотека FCL как статический элемент каркаса Framework .Net

3.      Исполнительная среда CLR как статический элемент каркаса Framework .Net

4.      Cборщик мусора � Garbage Collector

5.      Типы проектов, создаваемых в среде Visual Studio .Net

6.      Структура проекта. Консольные проекты и Windows-проекты.

7.      Классификации типов в языке C#

8.      Значимые и ссылочные типы

9.      Преобразования типов

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

11.  Синтаксис и семантика объявления переменных

12.  Область видимости и время жизни переменных

13.  Глобальные и локальные переменные

14.  Построение выражений, вычисление выражений, преобразования в выражениях

15.  Классы Math и Random

16.  Методы класса. Синтаксис и семантика

17.  Замена формальных параметров метода фактическими. Семантика замены

18.  Спецификации и корректность программ

19.  Триады Хоара

20.  Статические и динамические массивы. Класс Array

21.  Массивы массивов. Инициализация массивов

22.  Операции над массивами

23.  Символьный тип char

24.  Строки переменной длины. Класс string

25.  Регулярные выражения

26.  Структуры как частный случай класса

27.  Классы. Свойства и методы класса

28.  Классы. Конструкторы класса.

29.  Классы и объекты. Динамическое создание объектов

30.  Классы и события.

31.  Алгоритмы работы над числами.

32.  Алгоритмы работы над строками.

33.  Поиск в массивах.

34.  Методы сортировки со сложностью O(n*n)

35.  Методы сортировки со сложностью O(n*log(n))

36.  Рекурсия. Рекурсивные алгоритмы. Примеры