Введение в информатику для астрономов
Конспект лекций:
План курса:
- Информация
- Введение. Сообщение и информация.
Связь сообщения и информации, их интерпретация и обработка.
Дискретные сообщения. Знаки. Алфавит.
Наборы двоичных знаков. Слова. Коды. Символы.
Шенноновские сообщения. Количество информации. Теорема кодирования Шеннона.
Обработка сообщений.
- Простейшие данные.
Биты. Булевы алгебры. Операции.
Байты. Символы. Кодирование.
Целые числа. Позиционные системы счисления. Дополнительный и обратный коды. Переполение.
Вещественные числа. Способы представления, стандарт IEE754. Потеря точности.
- Организация данных
Массивы. Одномерные и многомерные массивы.
Хэши. Хэш-функции.
Списки. Связанные списки. Стэки, очереди, дэки.
Деревья. Бинарные деревья. Сбалансированные (АВЛ) деревья.
Графы.
Тексты. Логическая структура. Язык XML.
Файлы и их форматы.
- Алгоритмы
- Введение в теорию алгоритмов. Этапы решения задач на компьютере.
Алгоритм, блок схема и мета язык.
- Машина Тьюринга. Полиномиальные задачи.
Недетерминированные полиномиальные задачи.
- Оценка ресурсоемкости алгоритмов.
- Перебор, рекурсия, конечные автоматы (регулярные выражения).
Алгоритмы с возвратом. Алгоритмы с оценочной функцией.
Динамическое программирование. "Жадные" алгоритмы.
- Некоторые важные алгоритмы.
Алгоритм генерации случайных чисел.
Алгоритмы сортировки.
HeapSort. Quicksort.
Хеширование.
Алгоритмы сжатия. Избыточное кодирование. Статистические,
словарные и контекстные методы.
Генерация кодов: префиксное кодирование (алгоритм Хаффмана),
арифметическое кодирование.
SZ-алгоритмы.
Операции с символьными строками. Обратная польская запись.
- Алгоритмы и струкутры данных в астрономических задачах.
Работа со списками. Построение оптимального по Парето
множества в задачах оптимизации полета КА.
Работа с деревьями и ее использование в Treecode.
Построение синтаксического графа.
Сортировка и поиск объектов на примере звездных каталогов.
Сжатие данных.
- Языки программирования и программное обеспечение
- Процедурные языки программирования, связь с моделью фон Неймана.
Элементы алгоритмов (оператор, ветвление, цикл).
Пример характерных особенностей Fortran и C.
- Программирование на многопроцессорных системах.
Архитектура МПС. SMP, MPP, кластеры. Средства программирования
на МПС. MPI. Синхронное и асинхронное взаимодействие процессов.
Примеры программ на Fortan и C.
- Декларативные языки.
Функциональные языки. LISP, Reduce.
Символьное программирование.
Задачи искусственного интеллекта.
Логические языки. Prolog.
- Объектно-ориентированное программирование.
Понятие инкапсуляции, встраивания и наследования.
Классы и объекты. Динамическое размещение объектов.
Конструкторы и деструкторы.
Семейства классов. Виртуальные функции. Абстрактные классы.
- Специализированные языки. Языки управления базами данных.
- Программное обеспечение.
Операционные системы. Трансляторы. Интерпретаторы.
Командные языки. Утилиты и приложения, библиотеки
и специализированные системы.
Специальные средства разработки программ.
|