Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.astro.spbu.ru/staff/ilin2/EDU/kurs1.html
Дата изменения: Fri Nov 19 16:15:04 2010
Дата индексирования: Mon Oct 1 23:02:40 2012
Кодировка: Windows-1251
Введение в информатику для астрономов

Введение в информатику для астрономов

Конспект лекций: 
    часть 1   --   лекции 1-5:   PostScriptPDF;   
    части 2-3   --   лекции 6-15:   PostScriptPDF .


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


Last modified: 20/12/03 by V.I.