Список вопросов:

CS101. Основы программирования

Данный курс заимствован из тома по информатике (CCCS).

Описание курса:

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

Требования к слушателям: Не требуется никакого предварительного опыта в области программирования или информатики. Студенты должны иметь достаточный объем математических знаний для решения простых линейных уравнений и уметь пользоваться математической нотацией и формализмами.

Список вопросов:

1. Базовые конструкции программирования: синтаксис и семантика языков высокого уровня; переменные, типы, выражения и присваивания; простейший ввод/вывод;
2. Условные предложения и итеративные конструкции
3. Функции и передача параметров; структурная декомпозиция.
4. Алгоритмы и решение задач: стратегии решения задач, роль алгоритмов в решении задач, стратегии реализации алгоритмов, стратегии отладки, понятие алгоритма, свойства алгоритмов.
5. Базовые структуры данных: примитивные типы; массивы; структуры;
6. Базовые структуры данных: строки и операции над строками.
7. Представление данных в памяти компьютера: биты, байты, слова; представление символьных данных.
8. Представление числовых данных и системы счисления;
9. Обзор операционных систем: роль и задачи операционных систем; простое управление файлами.
10. Введение в распределенные вычисления: предпосылки возникновения и история сетей и Интернета.
11. Человеко-машинное взаимодействие: введение в вопросы проектирования.
12. Методология разработки программного обеспечения: основные понятия и принципы проектирования; структурная декомпозиция; стратегии тестирования и отладки; разработка сценариев тестирования (test cases);
13. Среды разработки; инструменты тестирования и отладки.
14. Социальный контекст компьютинга: история компьютинга и компьютеров; эволюция идей и компьютеров; социальный эффект компьютеров и Интернета; профессионализм, кодекс этики и ответственное поведение; авторские права, интеллектуальная собственность и компьютерное пиратство.

 

CS102. Объектно-ориентированная парадигма

Данный курс заимствован из тома по информатике (CCCS).

Описание курса:

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

Требования к слушателям: CS101.

 Список вопросов:

1. Объектно-ориентированное программирование: объектно-ориентированное проектирование, инкапсуляция и скрытие информации; разделение интерфейса и реализации; классы, наследники и наследование; полиморфизм; иерархии классов.
2. Основные вычислительные алгоритмы: алгоритмы поиска и сортировки (линейный и дихотомический поиск, сортировка вставкой и выбором наименьшего элемента).
3. Основы программирования, основанного на событиях.
4. Введение в компьютерную графику: использование простых графических API.
5. Обзор языков программирования: история языков программирования; краткий обзор парадигм программирования.
6. Виртуальные машины: понятие виртуальной машины; иерархия виртуальных машин; промежуточные языки.
7. Введение в теорию трансляции: сравнение интерпретаторов и компиляторов; стадии трансляции; машинно-зависимая и машинно-независимая части транслятора.
8. Введение в СУБД: история и причины возникновения систем баз данных, использование языков запросов базы данных.
9. Эволюция программ: сопровождение программ, характеристики удобного для сопровождения программного обеспечения, реинжиниринг, унаследованные системы, повторное использование программного обеспечения.

 

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

Данный курс заимствован из тома по информатике (CCCS).

Описание курса:

Данный курс является логическим продолжением курсов CS101-102 и знакомит студентов с базовыми концепциями структур данных и связанных с ними алгоритмов. Темы курса включают рекурсию, философию объектно-ориентированного программирования, базовые структуры данных (включая стеки, очереди, связанные списки, хэш-таблицы, деревья и графы), основы анализа алгоритмов и введение в принципы трансляции.

Требования к слушателям:  CS102; желательно также знание дискретной математики в объеме курса CS105.

Список вопросов:

1. Базовые структуры данных: стеки, очереди, связанные списки, хэш-таблицы, деревья, графы.
2. Основные вычислительные алгоритмы: алгоритмы сортировки со сложностью O(NlogN), хэш-таблицы и алгоритмы избежания коллизий
3. Двоичные деревья поиска, представления графов, обходы в глубину и в ширину.
4. Рекурсия: понятие рекурсии, рекурсивные математические функции, простые рекурсивные процедуры, стратегия «разделяй и властвуй», ре- курсивный перебор с возвратами, реализация рекурсии.
5. Базовый анализ алгоритмов: асимптотический анализ максимальной и средней сложности; установление различий между лучшим, средним и худшим случаями; нотации «О-большое» и «о-маленькое», «омега» и «тета»; стандартные классы сложности.
6. Эмпирические измерения производительности; затраты по времени и объему памяти; использование рекуррентных соотношений для анализа рекурсивных алгоритмов.
7. Алгоритмические стратегии: методы «грубой силы»; «жадные» алгоритмы; «разделяй и властвуй»; алгоритмы с возвратами; метод ветвей и грани.
8. Эвристики; сопоставление с образцом; алгоритмы обработки строк и текстов; алгоритмы численной аппроксимации.
9. Программная инженерия: аттестация программного обеспечения; основы тестирования, включая создание плана тестирования и генерации тестовых сценариев; объектно-ориентированное тестирование.