1. Алгоритмы и структуры данных. Введение

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

Программирование – это конструирование. Как вообще можно учить изобретательному конструированию? Можно было бы попытаться из анализа многих примеров выделить элементарные композиционные принципы и представить их систематическим образом.


Структуры данных

Данные предшествуют алгоритмам: нужно иметь некоторые объекты до того, как можно будет что-то с ними делать. Несколько основных структур данных, называемых фундаментальными:
  • запись;
  • массив (с фиксированным размером);
  • множество.
Переменные, принадлежащие одному из таких фундаментальных видов структур, меняют только свое значение, но никогда не меняют ни свое строение, ни множество своих допустимых значений. Как следствие – размер занимаемой ими области памяти фиксирован.

«Сложные» структуры, на против, характеризуются изменением во время выполнения программы как своих значений, так и строения. Структуры данных строение которых меняется во время выполнения программы называются динамическими.

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

"Приоритетные деревья поиска" допускают экономное представление и позволяют выполнять быстрый поиск по множествам точек на плоскости.

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

  • сортировка;
  • поиск;
  • рекурсия (рекурсия есть обобщение понятия цикла (итерации), класс алгоритмов с возвратом - отличное применение рекурсии);
  • динамические структуры данных.  

Нотация

Оберон/Компонентный Паскаль

Оберон/Компонентный Паскаль = 
лучшие черты старого доброго Паскаля +
промышленный опыт Модулы-2 +
минимум средств объектно-ориентированного программирования

Оберон/Компонентный Паскаль - наиболее совершенный потомок старого Паскаля по прямой линии. В нем отражено более полное понимание проблематики эффективного программирования:
  • Паскаль (1970);
  • Модула-2 (1980) // на которой программируются, например, российские спутники связи;
  • Оберон (1988, 2007).
В Модуле-2 нет встроенного файлового типа.

Диапазон эффективного применения Оберона:
  • вычислительные приложения;
  • системы управления любого масштаба (от беспилотников весом в 1 кг до грандиозных каскадов ГЭС);
  • задачи символической алгебры с предельно динамичными структурами данных.

Популярный вариант Оберона - система Блэкбокс. 

В Oberon-07 обеспечена полная явная поддержка цикла Дейкстры.
Также в Оберон-07 есть многоветочный вариант цикла WHILE. Пример:
WHILE m > n DO m := m - n
ELSIF n > m DO n := n - m
END

Система типов является герметичной, т.е. ее нельзя обойти средствами языка даже при работе с указателями. Это обеспечило возможность автоматического управления памятью (сбор мусора).

XDS Oberon - оптимизирующий компилятор.

OberonScript - аналог JavaScript для использования в Web-приложениях. Небольшой пример на Oberon Script с использованием HTML5 <canvas>.

Ссылки:

Теги: