Информатика для первого курса CS101-103

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

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. Программная инженерия: аттестация программного обеспечения; основы тестирования, включая создание плана тестирования и генерации тестовых сценариев; объектно-ориентированное тестирование.