Новости :

Linux для пользователя amigaos

LINUX ДЛЯ ПОЛЬЗОВАТЕЛЯ AMIGAOS

(ц) Eugene Sobolev aka aGGreSSor (Санкт-Петербург)
email: eugene_sobolev#mail.spbnit.ru
Источник: PowerAmiga #7

Времени ушло много, сделано ничтожно мало и желающих что-то делать уже не осталось. Я не буду углубляться в историю Linux, объяснять, зачем он нужен когда есть самая замечательная OS на свете — AmigaOS, доказывать, что на Amiga пингвин работает ничем не хуже, чем на всех остальных платформах (а местами и лучше)… Просто есть такое млекопитающие, которые вы можете попробовать приручить, а затем (если вас на это хватит), ещё и попробовать выдоить из него некоторую прибавку к пенсии. Возможно, кому-то захочется от игры в бирюльки, перейти к серьезной игре тяжёлыми чугунными предметами. А если это любовь? Кака любовь? Попробуй — полюбишь… Просто для информации скажу, что специалисты "по иксам" на рынке труда (Санкт-Петербург, Москва — это те города за которые я могу отвечать) местами потеснили "сертифицированных специалистов 1С:", а ценятся линуксоиды просто на вес золота. Я отдаю себе отчёт в том, что ваши пляски с бубном (у 50% читателей, вторая половина просто не станет этим заниматься) будут происходить на классической амиге. Если вы являетесь гордым обладателем PPC-акселлератора или новой амиги (Pegasos, AmigaONE) — вам же хуже. В этой статье речь пойдёт только об одном конкретном дистрибутиве (debian) и под одну конкретную линейку(m68k).

/ Технический редактор /

ПРИГОТОВЛЕНИЕ К КАЗНИ
ПЕРВЫЕ ШАГИ НА ЭШАФОТ
ПРИГОВОРЕННЫЙ УМИРАЕТ В ПОЛДЕНЬ
ДОБРО ПОЖАЛОВАТЬ В АД
ПО ТУ СТОРОНУ КОМАНДНОЙ СТРОКИ
АНАТОМИЧЕСКИЙ ТЕАТР



o ПРИГОТОВЛЕНИЕ К КАЗНИ o

Не удивляйтесь. Речь идёт о вашей собственной голове т.к. если она у вас есть — можете смело с ней распрощаться, ежели нет… На нет и суда нет…

"Иксов" для амиг существует множество, в частности существуют практически все дистрибутивы Linux, которые можно встретить на полках лотков по продаже CD и радиорынках страны. Исключая, конечно ASPLinux. Разумеется большинство из наших амижных дистрибутивов морально устарело, но в принципе для любой из существующих амиг, есть специально адаптированные дистрибутивы первых официальных версий ядра. Именно дистрибутивы, а не Minix, как подумалось некоторым. Официально классическую амигу (я специально не говорю о Pegasos/AmigaONE) поддерживает только debian community, поэтому только один дистрибутив m68k/Debian GNU/Linux запоздало, но обновляется. Также необходимо упомянуть RedHat 68k CD подготовленный F0lken^RamPage. На этом список современных пингвинов на классической амиге заканчивается. Для инсталляции дистрибутива debian вам потребуется (минимально): 020, MMU, 2Mb Fast, 42Mb для основной партиции на винчестере и 20Mb для файла-подкачки. В этих условиях Linux будет еле ворочаться. Приемлемые же условия для нормальной работы: 030, MMU, 8-16Mb Fast, 200-400Mb для основной партиции и объём Fast-памяти помноженный на 2 для файла-подкачки. Больше — лучше, причём наиболее значительное влияние на скорость окажут улучшения по критериям: процессора, памяти, объёма доступного дискового пространства.

Первое китайское предупреждение собравшимся ставить Linux: сделайте копию всей вашей системы (а то и всего винта) куда-нибудь на CD-RW или ещё дальше.

Страшно? А то! Так написано во всех руководствах и поверьте — систему (AmigaOS) вы угробите. Потому что если её не угробите вы, то её угробит инсталлятор. Если её не угробит инсталлятор, то обязательно упадёт файловая система. На худой конец, пингвины обязательно нагадят на рядом лежащие партиции или превратят rdb винчестера в нечто неудобоваримое.

Второе китайское предупреждение: крайне желательно перед установкой Linux ликвидировать обычную мешанину из разных файловых систем на разных партициях.

Дело в том, что мир находящийся снаружи от amiga community, уверен, что единственная файловая система которой могут пользоваться амижники — FFS, как составляющая AmigaOS. И кстати, единственная кодировка возможная для русских на амиге, это DM (она же Amiga-R). Такова сила стандарта. Бороться с этим уже поздно т.к. те люди, которые должны были отвечать за освещение данных вопросов, просто не работали, как следует. Для нас это значит, что из-под Linux возможным будет смонтировать только те партиции, которые отформатированы под FFS (можно 44.5 и лучше). В принципе, если на винчестере есть партиции с файловыми системами родственными FFS (AFS, отчасти первые версии SFS), то их можно попробовать оставить, как есть.

Третье китайское предупреждение: вам необходимо скачать много-много документации и прежде чем вы возьмётесь ставить Linux вам придётся много-много читать. Впоследствии придётся читать ещё больше.

Данная статья предназначена только для первоначального введения в курс дела. Для того чтобы нормально поставить Linux и затем ещё и пользоваться им, пересобирать ядро системы и выполнять тысячу других обычных для линуксоида дел, вам придётся по настоящему много читать. По настоящему учиться, в первую очередь столь редкому у амижников качеству — скромности. Можете заказать себе плакат с изображением пингвина Тукса и большими буквами RTFM — своеобразный девиз каждого опингвиненного (я уже давно проделал это, подумываю ещё об одном таком же =). На самом деле я не имею ничего против AmigaOS (lite Unix, между прочим), но на каждой платформе, каждой операционной системе, есть люди которым просто не дано пользоваться "иксами". Чаще всего не хватает чисто человеческих качеств: упорства и скромности. На вопрос же: "зачем всё это надо?", хорошо и очень тонко отвечал Эммануил Кант. "Иксы" не обладают свойствами "чтойности" и "зачемности", на вопросы "Что?" и "Зачем?" они не отвечают...

o ПЕРВЫЕ ШАГИ НА ЭШАФОТ o

1. Выбор способа инсталляции.

Основные способы инсталляции: с локального CDROM, партиции на винчестере, набора дискет (ala AmigaOS 3.1), удалённого сервера (ftp, http, etc). Последний способ на m68k-системах (Mac, Atari, Amiga) традиционно плохо поддержан и практически не используется. Первый способ будет вам доступен только если вы закажете дистрибутив debian 2.2 (6 CD, это так называемый Official Amiga CD Set) или скачаете образы CD содержащих дистрибутив с сервера (недёшево) и нарежете их самостоятельно. Можно воспользоваться образами дискет (720k, 1.2m, 1.44m), которые можно скачать там же и получить нечто подобное Minix. Для инсталляции с партиции на винчестере необходимо сходить на один из общедоступных ftp-архивов (таких как ftp.debian.org, ftp.de.debian.org, etc) и выкачать оттуда два файла: amigainstall.tgz и base2_2.tgz. Полный список зеркал можно без труда лицезреть на http://www.debian.org/distrib/ftplist. Вне зависимости от того, каким зеркалом вы решите воспользоваться, путь к этим файлам будет одним и тем же: "pub/debian/dists/potato/main/disks-m68k/".

2. Переразбиение винчестера.

Конкретный выбранный нами дистрибутив не поддерживает винчестеры объёмом более 4G (на PC с ядром 2.2 та же история — не ставится на партиции за чертой 4G). На амигах, партиции за чертой 4G debian 2.2, будет не в состоянии смонтировать, а также не в состоянии будет загрузиться с такой партиции. Необходимо обеспечить три партиции:

  • порядка 200-400Mb (я впрочем, предпочитаю 1,2G) для размещения самого Linux. Эта партиция называется основной.
  • размером равным объёму Fast-памяти x 2 (но не меньше 20Mb) для размещения файла-подкачки (виртуальная память, swap).
  • размером около 25Mb (и больше). Партиция для инсталляции Linux и последующего обмена данными с AmigaOS.

Все три партиции должны находиться в пределах первых 4G от физического начала винчестера и отформатированы под FFS. Даже если вам вдруг приснилось, что вы полностью "переползёте" под Linux, загрузочная партиция AmigaOS у вас должна быть. Все без исключения дистрибутивы m68k linux рассчитаны на запуск из-под "родной" OS. Выполнив всё сказанное выше, необходимо внести некоторые изменения для основной и swap партиций.

Запустите HDToolBox, выберите партицию, которую намереваетесь сделать стартовой (основной), установите флажок "Advanced Options" и нажмите на кнопку "Change". Далее выберите в выпадающем списке "Custom Filesystem" или "Reserved Filesystem" (зависит от версии HDToolBox которой вы пользуетесь), наберите в поле "Inditifier" число "0x4c4e5800" (что соответствует LNX

  • Маску подсети (например, 255.255.255.0)
  • Адрес broadcast'а
  • IP-адрес шлюза по умолчанию
  • IP-адрес первичного dns-сервера
  • Тип соединения (Ethernet, PPP, Slip)
  • 8) Install the Base System

    Также как на шаге 5 (Install Operating System Kernel and Modules) от вас потребуется указать путь к инсталляционному файлу. На этот раз "/hda?/debian", где ? — порядковый номер вашей основной партиции. По этому пути инсталлятор будет искать файл base2_2.tgz. Конечно, если у вас есть debian CD set, то вы можете просто выбрать "cdrom: CD-ROM drive" из списка и ввести "/install" вместо пути. Вам придётся подождать до нескольких минут (в зависимости от производительности вашего процессора и трансфера с винчестером) пока базовый архив будет разархивирован на основную (теперь уже Linux root) партицию.

    9) Configure the Base System

    Здесь вас попросят выбрать временную зону. Если вы хотите, чтобы в будущем не было заморочек с часами под Linux — не устанавливайте, пожалуйста, GMT (гринвичский мередиан). Выберите соответствующий вашей местности часовой пояс из списка. Так, для жителей Москвы и Санкт-Петербурга надо выбрать Europe/Moscow. В списке присутствуют пояса для всех местностей России (и бывшего СССР).

    10) Reboot the system

    Таким образом, мы успешно проинсталлировали Linux и нам осталось только пропустить (!) следующий шаг (Make Linux bootable directly from hard disk) и выбрать альтернативный шаг 2: "Reboot the system". На некоторых акселераторах сброс окажется невозможным, а сама амига потребует кратковременного выключения питания. Это неприятная особенность серии ядер 2.2.x debian GNU/Linux, которую разработчики обещали исправить в будущих релизах для амиг.

    o ДОБРО ПОЖАЛОВАТЬ В АД! o

    Сейчас мы запустим Linux в первый раз! Для этого загружаемся, идём в известную нам директорию и открываем в любимом текстовом редакторе файл того сценария, который вы только что использовали для инсталляции. Этот файл будет содержать строчку следующего вида:

      amiboot-x.x -k linux root=/dev/yyyy ro
    
    

    , где "x.x" — номер версии amiboot (для 2.2, обычно amiboot-5.6);
    "yyyy" — имя основной (root) партиции (sda1, hda3, etc),
    для инсталляционного сценарии здесь будет ram и не будет атрибута ro.

    Исправьте значение "yyyy" на своё, добавьте после него ro (read-only) и сохраните получившийся файл в той же директории под именем LinuxGO!. Далее добавьте файлу иконку (готовую можно взять из приложения к журналу), вынесите её (для удобства) на рабочий стол и запустите Linux. Откроется shell-окно в которое будет выводиться информация примерно следующего содержания:

    Linux/m68k Amiga Bootstrap version 5.6
    Copyright 1993,1994 by Hamish Macdonald and Greg Harp

    Amiga model identification:
    Resource `draco.resource': not present
    Chipset: AGA
    Module `A1000 Bonus': not present
    Module `A4000 bonus': not present
    Resource `card.resource': 0x78008e38

    Amiga 1200 CPU: 68030 without FPU, AGA chipset

    Command line is 'root=/dev/hda2 ro'
    Vertical Blank Frequency: 50Hz
    Power Supply Frequency: 50Hz
    EClock Frequency: 709379Hz

    Found 3 AutoConfig Devices
    Device 0: addr = 0x00ea0000
    Device 1: addr = 0x00ec0000
    Device 2: addr = 0x00200000

    Found 1 Block of Memory
    Block 0: 0x78000000 to 0x79f80000 (32256K)
    2048K of CHIP memory

    The kernel will be located at 0x78000000
    Kernel is compressed
    Uncompressing kernel image ...............................................done

    Loading ELF Linux/m68k kernel...
    Bootstrap's bootinfo version: 2.0
    Kernel's bootinfo version : 2.0

    RAM disk at 0x788bf4a2, size is 854K

    Kernel segment 0 at 0x78001000, size 1455584
    Kernel segment 1 at 0x781645e0, size 80416
    Boot info at 0x78178000

    Kernel entry is 0x00002000
    ramdisk dest is 0x79eaa5af
    ramdisk lower limit is 0x788bf4a2
    ramdisk src top is 0x78994ef3

    Type a key to continue the Linux/m68k boot...

    После нажатия любой клавиши будет открыт экран 640x480x8 и… Процесс инсталляции продолжится. О принципах действия затенённых паролей, настройке APT, использовании программ slink, dselect и aptitude вы прочитаете самостоятельно и из других источников. Моя же задача провести вас через процесс инсталляции максимально быстро. Вам будут задаваться следующие вопросы:

    • Использовать (или нет) пароли MD5 (больше 8 символов) "MD5 passwords"?
      (рекомендация: да, используйте их!)
    • Использовать (или нет) затенённые пароли "Shadow passwords"?
      (рекомендация: да, используйте их!)
    • Задать пароль для привилегированного пользователя "root"?
      (рекомендация: обязательно, и пароль не меньше 6 символов)
    • Создать счёт (account) для ещё одного (непривилегированного) пользователя?
      (рекомендация: не пропускайте и этот шаг!)
    • Удалить поддержку PCMCIA-устройств из ядра?
      (если вы ранее установили соответствующий модуль, то поддержка всё равно будет работать, даже если вы ответите, что её надо удалить)
    • Хотите ли вы продолжить инсталляцию системы из internet через PPP-интерфейс?
      (Авторы утверждают, что эта возможность не тестировалась.
      Да, она действительно не работает. =( ).
    • Выбрать источник пакетов программ (*.deb) откуда они будут браться для последующей инсталляции в Linux Debian через его универсальную систему инсталляции APT. Также здесь можно указать какую часть дистрибутива вы хотите инсталлировать (проприетарную "non-US", шараверную "non-free" или дополнительную "contrib").
    • Выбрать способ инсталляции пакетов. Выбирать можно между упрощённым "simple" и продвинутым "advanced".

    Простой способ будет использовать программу "tasksel", которой вы можете воспользоваться и позже, и которая служит для инсталляции так называемых мета-пакетов, например среды разработчика для C или игр. Каждый мета-пакет может быть составлен из некоторого числа обыкновенных пакетов *.deb необходимых для его нормального функционирования.

    Продвинутый способ заключается в использовании программы "dselect", которая является основным средством обновления и инсталляции пакетов в дистрибутиве Linux Debian.

    Не рекомендуется использовать для инсталляции программу "dpkg", если вы не уверены что вы совершенно точно сделаете всё правильно. Оба способа (tasksel и dselect) по умолчанию используют команду "apt" (или "apt-get"), которая позволяет очень легко и быстро инсталлировать пакеты (в случае если вы, конечно имеете некоторый опыт в использовании slink и dselect).

    o ПО ТУ СТОРОНУ КОМАНДНОЙ СТРОКИ o

    Итак, вы прошли все препитии инсталляции Linux, благополучно ответили на запросы login (например, root) и password (причём, я надеюсь, вас позабавило отсутствие привычных звёздочек при вводе — привыкайте =). До сих пор вы следовали одной единственной инструкции и иногда включали голову. Сейчас же вам необходимо будет познакомиться с базовой пользовательской средой — командной строкой. Интерфейс командной строки в случае "иксов" это — самый непосредственный способ выполнения задач администрирования системы. А в вашей системе на данный момент по большому счёту пусто. Отсуствует даже намёк на команды работы с документацией apropos, info, man. Поэтому вам придется выкачать c какого-нибудь зеркала ftp.debian.org соответствующие пакеты (файлы с расширением deb) этих программ для Debian/m68k и поставить их ручками. У меня, например стоят "/doc/info_4.0-4.deb" и "/doc/man-db_2.3.16-4.deb", и надо сказать, что я вполне ими доволен. =)

    Следуя традиции ОС UNIX, Linux поставляется, по крайней мере, с тремя интерпретаторами командной строки: Bourne-Again shell ("/bin/bash") — аналог "/bin/sh" в UNIX, "/bin/tcsh" — аналог С Shell ("/bin/csh") в UNIX и "/bin/zsh" — аналог Korn Shell ("bin/ksh") в UNIX. Переключение между терминалами производиться комбинацией клавиш "Alt + F1…F10". Количество терминалов в принципе не ограничено, но по умолчанию активировано всего 6, а линуксоиды, как правило уменьшают впоследствии это количество до двух-трёх.

    Работа пользователя в Linux всегда начинается с запуска сценария терминала. Сначала создаётся процесс getty, который является сервером терминала и запускает программу login, которая в свою очередь, запрашивает у пользователя имя (login) и пароль (password). Если пользователь зарегистрирован в системе и ввёл правильный пароль, то login запускает программу, указанную в последней строке файла "/etc/passwd". В принципе, это может быть любая программа. Но как правило здесь указывается любимый интерпретатор командной строки.

    Всё вводимое в командной строке различают на функции определённые пользователем, встроенные команды интерпретатора и исполняемые файлы — прикладные программы и утилиты. В любом случае, синтаксис их вызова одинаков, и вам, на первых порах можно об этом не задумываться. Для получения списка аргументов используется ключ --help, для получения версии — ключ --version.

    Попробуйте ввести следующие команды и посмотреть на результаты их работы:

    # arch
    # date
    # df -TPa
    # du -ch
    # dir
    # ls -alF --color=yes
    # echo "We are testing the shell!!"
    # find / -name amiga
    # ps -a
    # sleep 3
    # type $SHELL

    Если вы пользовались раньше командной строкой, то результаты выполнения большинства приведённых выше команд вам должны быть в общих чертах понятны. Если же нет… Что же, теперь вам по крайней мере есть чем заняться. Рассмотрим возможность последовательного исполнения команд:

    # pwd; date

    Заметим, что сначала выполниться команда pwd, которая выведет имя текущей директории, а затем date, которая покажет дату и время. Рассмотрим другое средство командной строки — выполнение команд в фоновом режиме. В этом случае интерпретатор не будет ждать завершения выполнения команды, а сразу после ввода выведет приглашение, и вы сможете продолжить работу. Для этого введённую строку необходимо завершать символом &.

    # find / -name issue &

    Пока утилита find производит поиск файла issue (содержащего, кстати, текст выводимый на экран перед запуском программы login) и сканирует файловую систему, вы можете, например, скачать почту или распечатать документ на принтере. Существует также возможность условного исполнения команд:

    # find / name bash && type $SHELL

    Здесь, переменная среды $SHELL (содержащая путь к текущему интерпретатору командной строки), будет выведена только в том случае, если команда find найдёт файл bash (интерпретатор Bourne-Again Shell). Можно назначить выполнение команды, только в случае неудачного завершения предыдущей. Делается это так:

    # find / name qwerty || echo "It's filename not found!"

    Возможно, приведённые примеры показались вам не слишком жизненными? Тогда рассмотрим поиск имени пользователя в файле паролей, и в случае успеха — поиск его имени в файле групп:

    # grep eugene /etc/passwd && grep eugene /etc/group

    Признаком успешного исполнения считается нулевой код возврата, неудачей (ошибкой исполнения) — все другие значения. Каждая исполняемая команда получает от интерпретатора три открытых потока ввода/вывода: стандартный ввод, стандартный вывод и стандартный вывод ошибок. По умолчанию все эти потоки ассоциированы с терминалом, однако их можно успешно перенаправлять. Например, подавить вывод сообщений об ошибках, установить ввод и вывод из файла и даже передать вывод одной программы на ввод другой. Синтаксис перенаправления ввода/вывода следующий:

    >file — Перенаправление потока вывода в файл file
    >>file — Добавление в конец файла file данных из потока вывода
    — Получение потока ввода из файла file
    p1 | p2 — Передача потока вывода программы p1 в поток ввода программы p2
    n>file — Переключение n-го потока вывода из файла в файл file
    n>>file — То же, но записи добавляются в конец файла file
    n>&m — Слияние n-го и m-го потоков
    < — Ситуация "Ввод здесь": используется стандартный поток ввода до подстроки str. При этом выполняются подстановки метасимволов интерпретатора командной строки.
    < — То же, но подстановки не выполняются.

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

    * ? [ ] — Метасимволы. Позволяют указывать сокращённые имена файлов, например, при поиске по маске.
    — Косая (обратный слэш). Отменяет специальное значение символов, таких как: *, ?, [, ], &, ;, <, >.
    '' — Одиночные кавычки. Отменяют значение пробела, как разделителя и специальное значение для всех символов.
    "" — Двойные кавычки. Отменяют значение пробела, как разделителя и специальное значение для всех символов, кроме $ и .

    Необходимо сразу заметить, что если вы думаете, что всё рассказанное выше не будет вами применяться, то вы глубоко в этом заблуждаетесь. Рассказанное является лишь надводной частью большого айсберга навыков работы с командной строкой (читай: навыков администрирования Unix-ориентированных OS). Для тех кому не дано этому научиться, как уже неоднократно говорилось свободны вакансии операторов, дизайнеров и прочей чёрной компьютерной работы. Каждый же нормальный пользователь иксов — программист. Напоследок я перечислю наиболее часто употребимые команды и ключи, чтобы те, кто всё-таки проникся описанной здесь идеологией могли получить необходимый старт.

    mount — служит для монтирования устройств, обратная операция выполняется командой umount. Наиболее важны здесь понятие файловой системы и точки монтирования. Точка монтирования — это путь, по которому можно будет найти файлы смонтированного устройства. Например, если вы создадите директорию "/ami" и выполните команду "mount -t affs /hda? /ami" (из корневой директории), то в директории "/ami" появятся файлы партиции "hda?" (где ? — порядковый номер партиции). Таким образом, вы можете получить доступ к вашей инсталляционной партиции и установить с неё предварительно записанные туда пакеты программ для debian (Файлы с расширением #?.deb, существует также конвертор пакетов #?.rpm из-под дистрибутива RedHat (Mandrake/AltLinux/ASPLinux и прочих rpm-ориентированных) в Debian. Конвертор называется alien.). Аналогично происходит монтирование cdrom: "mount -t iso9660 /hdb /cdrom".

    dpkg — служит для инсталляции пакетов "руками". Все остальные средства автоматизации установки пакетов (apt, dselect, slink, aptitude) так или иначе используют эту команду. Её использование целесообразно для установки пакетов имеющих малое число зависимостей, в особенности если все требуемые пакеты уже имеются в системе. Синтаксис прост: "dpkg -I [путь]" — получить информацию о пакете; "dpkg -i [путь]" — установить пакет.

    clear — Очистка текущего терминала.

    pwd — Вывод имени текущей директории.

    cd [путь] — Смена текущей директории. Вместо пути можно использовать:
    ~ — домашняя директория пользователя;
    / — корневая директория;
    . — текущая директория;
    .. — предыдущая директория.

    ls — Вывод содержимого текущей директории.
    -a — показывать все файлы (включая начинающиеся с точки);
    -l — показ полной информации (режим доступа, количество ссылок на файл,
    имена владельца и группы, размер в байтах и время последнего изменения);
    -F — показывать идентификаторы (/ - директория, * - исполняемый файл, @ - ссылка).

    cat [путь или список путей] — Вывод содержимого файла(-ов).

    zcat [путь или список путей] — Вывод содержимого файла(-ов) сжатого(-ых) gzip.

    find [директория с которой начинается поиск] [образец поиска] — Поиск файлов, ссылок и директорий.
    -name — поиск по имени
    -perm — поиск с заданным режимом доступа
    -type — поиск по типу (f-файл, d-директория, l-ссылка)
    -user — поиск по владельцу
    -group — поиск по группе
    -size — поиск по размеру

    cp [исходный путь] [целевой путь] — Копирование файлов, ссылок и директорий.
    -f — безусловное копирование;
    -r — копирование директории вместе с вложенными в неё;
    -i — задавать вопрос о перезаписи если файл существует;
    -b — создание дубликата вместо перезаписи существующего файла;
    -l — создание прямых ссылок вместо копирования.

    mv [исходный путь] [целевой путь] — Перенесение файлов, ссылок и директорий.
    -f — безусловное перенесение;
    -i — запрос на подтверждение перед удалением;
    -b — создание резервных копий удаляемых файлов.

    rm [путь] — Удаление файлов, ссылок и директорий.
    -r — удаление директории со всем содержимым;
    -i — запрос на подтверждение перед удалением;

    df — Вывод информации о накопителях.
    -a — вывод информации для всех файловых систем;
    -T — вывод названия каждой файловой системы.

    du — Вывод информации о использованном дисковом пространстве.
    -h — вывод в читабельном формате;
    -k — вывод размеров в килобайтах.

    o АНАТОМИЧЕСКИЙ ТЕАТР o

    Как уже было не раз сказано — пингвины жутко популярны. И это не случайно. Во первых, система академического образования большинства стран (и в первую очередь США) включает в себя обязательное изучение Unix-ориентированных систем. Ни о каких Win или MacOS там речи не идёт и идти не может. На национальном компьютере Америки — Apple Macintosh, находящемся в каком-нибудь коледжском кампусе, будет стоять UNIX FreeBSD. И все Кевины Митники совершали свои подвиги из под иксов. Linux здесь выступает, как наиболее дружественная пользователю среда, отвечающая нормам системы образования. Поэтому, он легко проникает туда, куда другим операционкам не было и не будет дороги. Во вторых, с появлением под Linux популярных СУБД и общезначимых компиляторов (в дополнение к тем десяткам которые были заимствованы из UNIX), возросла его роль в создании автоматизированных рабочих мест, ни в пример более защищённых, нежели в случае решений от Wintel. И наконец, в третьих, на русском языке Linux уже документирован ничуть не хуже чем Win. А раз есть русская документация и вырос значительный контингент пользователей, то операционка живёт полнокровной жизнью и в русскоязычной среде. Её холят, лелеют и интересуются её внутренностями уже миллионы Россиян (два года назад был зарегестрирован миллионный пользователь дистрибутива RedHat). Разумеется, на просторах internet существует и обширный анатомический театр посвящённый внутренностям и нутрянным проблемам Linux. Я предлагая вам отправиться на небольшую экскурсию...

    LINUX.RU

    Это первый сайт который обычно приходит в голову. Здесь публикуются ежедневные и еженедельные новости, хранятся переводы Linux HOW TO, Linux User/ Admin/Developer Guide и другая документация. Также существует форум, публикуются статьи и подборки посвящённые вопросам безопасности.

    РУССКАЯ ИНФОРМАЦИЯ ОБ ОС LINUX

    Сайт публикует новости из мира Linux, к которым можно оставлять свои комментарии. Проводятся опросы посетителей на животрепещущие темы. Имеется свой хит-парад desktop'ов. Множество различных цветовых схем для сайта (по умолчанию фон чёрный). Хранится пачка полезной документации и общехвалебных текстов посвящённых пингвиньим прелестям.

    LINUX INFORMATION CENTER

    Аналог AiC для линуксоидов. Самое главное достоинство сайта — наличие постоянно пополняющейся виртуальной энциклопедии Linux. Если бы что-то подобное существовало для русскоязычных пользователей Амиги, возможно амижники не чувствовали бы себя такими ушибленными.

    LINUX START!

    Перевод на русский язык известного буржуйского сайта LinuxStart!. Имеет web-чат, поисковую систему и возможность получение бесплатного почтового ящика. Основное достоинство — пошаговый учебник по Linux и каталог ресурсов сети посвящённых Linux.

    О ЛИНУКС ПО-РУССКИ

    Очень хороший сайт. Я выкачал отсюда тонны документации на русском языке и столько же ещё осталось. Это один из моих самых любимых сайтов.

    UNIX WARE — ДЛЯ ТЕХ У КОГО ЕСТЬ КОМПЬЮТЕР

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

    INTERFACE ENHANCEMENT

    Сайт целиком посвящённый темам рабочего стола и разнообразныс скинам для пользователей Linux. Здесь есть скины практически для любого менеджера окон: от AfterStep, до WM. Предлагается для перенятия амижниками.

    Комментарии: (0) | Linux | 2006-06-02

    Графы


    Материал подготовил(и): virt

    Графы можно представлять в виде множества вершин и множества соединяющих их ребер. (Города и дороги их соединяющие)

    1. Просмотр вершин графа в некотором фиксированном порядке.

    общие структуры данных :
    Код
    const Maxn=100;
    var a:array[1..Maxn,1..Maxn]of integer;
    Nnew:array[1..Maxn]of boolean;
    n,i,j:integer;


    поиск в глубину :
    Код

    { рекурсивный вариант }
    procedure Pg(v:integer);
    var i:integer;
    begin
    Nnew[v]:=false;
    write(v:2);
    for i:=1 to n do
    if (a[v,i]<>0) and Nnew[i] then Pg(i);
    end;

    { нерекурсивный вариант }
    procedure Pg_nonrec(v:integer);
    var St:array[1..Maxn]of integer;
    yk:integer;
    t,j:integer;
    pp:boolean;
    begin
    fillchar(St,sizeof(St),0);
    yk:=1;
    St[yk]:=v;Nnew[v]:=false;
    write(v:2);
    while yk <> 0 do
    begin
    t:=St[yk];j:=0;pp:=false;
    repeat
    if (a[t,j+1] <> 0) and Nnew[j+1] then pp:=true
    else inc(j);
    until pp or (j >= n);
    if pp then
    begin
    inc(yk);St[yk]:=j+1;Nnew[j+1]:=false;
    write(j+1:2);
    end else
    dec(yk);
    end;
    end;


    Поиск в ширину:
    Код
    procedure Pw(v:integer);
    var Og:array[1..Maxn]of 0..Maxn;
    yk1,yk2:integer;
    j:integer;
    begin
    fillchar(Og,sizeof(Og),0);yk2:=0;
    yk1:=1;Og[yk1]:=v;Nnew[v]:=false;
    while yk2 < yk1 do
    begin
    inc(yk2);v:=Og[yk2];
    write(v:2);
    for j:=1 to n do
    if (a[v,j] <> 0) and Nnew[j] then
    begin
    inc(yk1);Og[yk1]:=j;Nnew[j]:=false;
    end;
    end;
    end;



    2. Каркасы (стягивающие деревья)

    Код
    const Maxn=100;
    var a:array[1..Maxn,1..Maxn]of byte;
    Nnew:array[1..Maxn]of boolean;
    Tree:array[1..2,1..Maxn]of integer;
    n,i,j:integer;
    yk:integer;


    Построение стягивающего дерева поиском в глубину:
    Код
    procedure Tree_Depth(v:integer);
    var i:integer;
    begin
    Nnew[v]:=false;
    for i:=1 to n do
    if (a[v,i] <> 0) and Nnew[i] then
    begin
    inc(yk);Tree[1,yk]:=v;Tree[2,yk]:=i;
    Tree_Depth(i);
    end;
    end;


    Построение стягивающего дерева поиском в ширину:
    Код
    procedure Tree_Width(v:integer);
    var Turn:array[1..Maxn]of integer;
    yr,yw,i:integer;
    begin
    fillchar(Turn,sizeof(Turn),0);yr:=0;
    yw:=1;Turn[yw]:=v;Nnew[v]:=false;
    while yw <> yr do
    begin
    inc(yr);v:=Turn[yr];
    for i:=1 to n do
    if (a[i,j] <> 0) and Nnew[i] then
    begin
    inc(yw);Turn[yw]:=i;Nnew[i]:=false;
    inc(yk);Tree[1,yk]:=v;Tree[2,yk]:=i;
    end;
    end;
    end;


    Построение всех каркасов графа:
    Код
    const Maxn=100;
    var a:array[1..Maxn,1..Maxn]of byte;
    Nnew:array[1..Maxn]of boolean;
    Tree:array[1..2,1..Maxn]of integer;
    Turn:array[1..maxn]of integer;
    n,i,j:integer;
    numb:integer;
    down,up:integer;

    ..............

    procedure solve(v,q:integer);
    var j:integer;
    begin
    if down >= up then exit;
    j:=q;
    while (j <= n) and (numb < n-1) do
    begin
    if (a[v,j] <> 0) and Nnew[j] then
    begin
    Nnew[j]:=false;
    inc(numb);
    Tree[1,numb]:=v;Tree[2,numb]:=j;
    Turn[up]:=j;inc(up);
    solve(v,j+1);
    dec(up);Nnew[j]:=true;dec(numb);
    end;
    inc(j);
    end;
    if numb = n-1 then
    begin
    writeln;
    for i:=1 to numb do
    write(Tree[1,i],' ',Tree[2,i],' ');
    exit;
    end;
    if j = n+1 then
    begin
    inc(down);
    solve(Turn[down],1);
    dec(down);
    end;
    end;


    Построение минимального каркаса методом Краскала:

    Граф задан списком ребер с указанием их весов:
    Код
    program minim_tree_kraskal;
    const maxn=100;
    var p:array[1..3,1..maxn*(maxn-1) div 2]of integer;
    Mark:array[1..maxn]of integer;
    k,i,t:integer;
    m,n:integer;{m - rebra;n - vershini }

    procedure Change_Mark(l,m:integer);
    var i,t:integer;
    begin
    if m < l then
    begin
    t:=l;l:=m;m:=t;
    end;
    for i:=1 to n do
    if Mark[i]=m then Mark[i]:=l;
    end;

    begin
    readln(n,m);
    for i:=1 to m do
    read(p[1,i],p[2,i],p[3,i]);
    for i:=1 to m-1 do
    for t:=i+1 to m do
    if p[3,i] > p[3,t] then
    begin
    k:=p[1,i];p[1,i]:=p[1,t];p[1,t]:=k;
    k:=p[2,i];p[2,i]:=p[2,t];p[2,t]:=k;
    k:=p[3,i];p[3,i]:=p[3,t];p[3,t]:=k;
    end;
    for i:=1 to n do mark[i]:=i;
    k:=0;t:=m;
    while k < n-1 do
    begin
    i:=1;
    while (i <= t) and (Mark[p[1,i]] = Mark[p[2,i]]) and (p[1,i] <> 0) do inc(i);
    inc(k);
    write(p[1,i],' ',p[2,i],' ');
    change_Mark(Mark[p[1,i]],Mark[p[2,i]]);
    end;
    end.


    Построение минимального каркаса методом Прима:
    Код
    procedure solve;
    var sm,sp:set of 1..maxn;
    min,i,j,l,t:integer;
    begin
    min:=maxint;
    sm:=[1..n];sp:=[];
    for i:=1 to n-1 do
    for j:=i+1 to n do
    if (a[i,j] < min) and (a[i,j] <> 0) then
    begin
    min:=a[i,j];
    l:=i;t:=j;
    end;
    sp:=[l,t];sm:=sm-[l,t];
    write(l,' ',t ,' ');
    while sm <> [] do
    begin
    min:=maxint;
    l:=0;t:=0;
    for i:=1 to n do
    if not (i in sp) then
    for j:=1 to n do
    if (j in sp) and (a[i,j] < min) and (a[i,j] <> 0) then
    begin
    min:=a[i,j];
    l:=i;t:=j;
    end;
    sp:=sp+[l];sm:=sm-[l];
    write(l,' ',t,' ');
    end;
    end;


    Материал подготовил(и): Altair

    Поиск кратчайших путей.

    Алгоритм Флойда

    Описание алгоритма:
    Над матрицей A (NxN) выполняется n итераций. После k-ой итерации, A[i,j] содержит значение наименьшей длинны путей из вершины i в вершину j, которые не проходят через вершины с номером, большим k.
    На k-ой итерации для вычисления матрицы A, используется слудующая формула:
    [CODEfaq]Ak[i,j] = min (Ak-1[i,j], Ak-1[i,k]+ Ak-1[k,j]).[/CODEfaq]
    Графическая интерпретация формулы:
    [attachmentid=726]

    Сложность алгоритма
    Время выполнения программы, имеетпорядок O(n3), так как в ней нет практически ничего, кроче 3 вложенных друг в друга циклов.

    Сохранение маршрутов.
    Что бы сохранять маршруты, от одной вершины кдругой, следует, ввести еще одну матрицу, в которой каждому элементу P[I,j]присваивать вершину K (номер), полученную при нахождении наименьшего значения a[I,j].


    Код
    Const
    NN=100;
    Type
    Graph = array[1..nn,1..nn] of longint; {граф задан матрицей смежности}
    Var
    n:integer;
    Procedure Floyd (var a:graph; c:graph; var p:graph);
    var i,j,k:integer;
    begin
    for i:=1 to n do
    for j:=1 to n do begin a[i,j]:=c[i,j]; p[i,j]:=0; end;
    for i:=1 to n do a[i,i]:=0;
    for k:=1 to n do
    for i:=1 to n do
    for j:=1 to n do
    If (a[i,k]+a[k,j] begin
    a[i,j]:=a[i,k]+a[k,j];
    p[i,j]:=k;
    end;
    end;

    procedure ReadGraph(var a:graph);
    var
    i,j:integer;
    begin
    write('n= ');readln(n);
    For i:=1 to n do for j:=1 to n do
    begin write('G',i,',',j,'= ');readln(a[i,j]); end;
    writeln;
    end;

    procedure ReadFileGraph(var a:graph);
    var
    i,j:integer; filename:string; f:text;
    begin
    Write('Enter file name:'); readln(filename);
    Assign (f,filename); reset(f);
    Readln(f,N);
    For i:=1 to n do for j:=1 to n do read(f,a[i,j]); close(f);
    end;

    var
    a,c,p:graph;
    i,j:integer;
    begin
    { ReadGraph( c );}
    ReadFileGraph( c );
    floyd(a,c,p);
    writeln('---------------------------');
    for i:=1 to n do {
    begin
    for j:=1 to n do write(a[i,j]:3);
    writeln
    end;
    writeln('---------------------------');
    for i:=1 to n do
    begin
    for j:=1 to n do write(p[i,j]:3);
    writeln
    end;
    readln;
    end.[/PASCODE]

    В программе C-граф, заданный матрицей смежности.
    A- матрица содержащая кратчайшие пути.
    P - матрица, сохраняющая маршруты.

    Материал подготовил(и): Altair

    Поиск кратчайшего пути. Алгоритм Дейкстры
    Процедура
    Код

    procedure Deikstr(n:integer; W:graph; u1,u2:integer;
    var length:integer; var Weight:real; var Path: array of integer);

    находит путь минимального веса в графе G, заданном весовой матрицей (матрица смежности) -W.
    При этом предполагается, что все элементы Wij неотрицательны.
    Путь ищется из вершины номер u1 к вершине номер u2 .
    Для представления веса, равного бесконечности (машинная бесконечность), используется число GM,
    передаваемое в алгоритм.
    Это число можно задавать в зависимости от конкретной задачи...
    модуль
    Код

    UNIT Dijkstra;
    Interface
    Const
    NN=30;
    Type
    graph=array [1..nn,1..nn] of integer;

    procedure Deikstr(n:integer; W:graph; u1,u2:integer;
    var length:integer; var Weight:real; var Path: array of integer);
    Implementation
    procedure Deikstr(n:integer; W:graph; u1,u2:integer;
    var length:integer; var Weight:real; var Path: array of integer);
    var
    i,k,j:integer;
    GM:real;
    d,m:array[1..nn] of real;
    p:array[1..nn] of integer;
    t:integer;
    dd,min:real;
    begin
    GM:=10000;{бесконечность}
    length:=0;
    if u1<>u2 then
    begin
    i:=1;
    repeat
    d[i]:=GM; p[i]:=0; m[i]:=0; i:=i+1
    until not(i<=n);
    d[u1]:=0; t:=u1;
    while length=0 do
    begin
    i:=1;
    repeat
    if w[t,i] begin
    dd:=d[t]+w[t,i];
    if d[i]>dd then begin d[i]:=dd; p[i]:=t end;
    end;
    i:=i+1
    until not(i<=n);
    Min:=GM; i:=1; k:=0;
    repeat
    if m[i]=0 then
    begin
    if d[i] end;
    i:=i+1
    until not(i<=n);
    if k<>0 then begin
    m[k]:=1; t:=k;
    if t=u2 then begin length:=1; end;
    end else begin length:=-1 end;
    end;
    if length=1 then
    begin
    Path[1]:=u2; length:=2; j:=u2;
    repeat
    Path[length]:=P[j]; j:=P[j]; length:=length+1
    until not(j<>u1);
    i:=1; k:=trunc(length/2);
    repeat
    t:=Path[i]; Path[i]:=Path[length-i]; Path[length-i]:=t; i:=i+1
    until not(i<=k);
    length:=length-1
    end;
    Weight:=d[u2]
    end;
    end;
    end.



    демонстрационная программа
    компилятор BP7 (target windows)
    Код

    uses wincrt,dijkstra;
    var
    i,u1,u2,n,l:integer;
    G:Graph;
    w:real;
    path:array[0..100] of integer;

    procedure ReadFileGraph(var a:graph);
    var
    i,j:integer; filename:string; f:text;
    begin
    Write('Enter file name:'); readln(filename);
    Assign (f,filename); reset(f);
    Readln(f,N);
    For i:=1 to n do for j:=1 to n do read(f,a[i,j]); close(f);
    end;

    begin
    readfilegraph(G); {читаем из файла граф.}
    write('u1 = '); readln(u1); {вводим первую вершину}
    write('u2 = '); readln(u2); {...и конечную..}
    Deikstr(n,G,u1,u2, L,w,path);
    writeln('w=',w:1:2); {выводим минимальный путь (вес)}
    writeln('path'); {выводим путь ....}
    for i:=1 to l do write(path[i],' - ');
    readkey;
    end.

    В программе,граф считывается из файла. Вот для такого графа:
    [attachmentid=878]
    файл должен иметь вид (за машинную бесконечность берется 10000):
    CODE

    20
    0 3 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000
    3 0 10000 10000 10000 3 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000
    10000 10000 0 2 10000 5 1 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000
    10000 10000 2 0 3 10000 10000 5 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000
    10000 10000 10000 3 0 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000
    10000 3 5 10000 10000 0 10000 10000 3 10000 10000 4 10000 10000 10000 10000 10000 10000 10000 10000
    10000 10000 1 10000 10000 10000 0 10000 2 2 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000
    10000 10000 10000 5 10000 10000 10000 0 10000 10000 4 10000 10000 10000 10000 10000 10000 10000 10000 10000
    10000 10000 10000 10000 10000 3 2 10000 0 2 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000
    10000 10000 10000 10000 10000 10000 2 10000 2 0 3 10000 10000 10000 10000 10000 10000 10000 10000 10000
    10000 10000 10000 10000 10000 10000 10000 4 10000 3 0 10000 4 10000 10000 5 10000 10000 10000 10000
    10000 10000 10000 10000 10000 4 10000 10000 10000 10000 10000 0 4 10000 10000 10000 10000 10000 10000 10000
    10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 4 4 0 4 3 10000 10000 10000 10000 10000
    10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 4 0 10000 10000 3 10000 10000 10000
    10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 3 10000 0 10000 10000 3 10000 10000
    10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 5 10000 10000 10000 10000 0 10000 4 7 10000
    10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 3 10000 10000 0 10000 10000 10000
    10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 3 4 10000 0 10000 6
    10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 7 10000 10000 0 10000
    10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 6 10000 0



    Материал подготовил(и): Altair

    Эйлеров цикл.

    Дадим теперь строгое определение эйлерову циклу и эйлерову графу. Если граф имеет цикл (не обязательно простой), содержащий все ребра графа по одному разу, то такой цикл называется эйлеровым циклом, а граф называется эйлеровым графом. Если граф имеет цепь (не обязательно простую), содержащую все вершины по одному разу, то такая цепь называется эйлеровой цепью, а граф называется полу-эйлеровым графом.
    Ясно, что эйлеров цикл содержит не только все ребра по одному разу, но и все вершины графа (возможно, по несколько раз). Очевидно также, что эйлеровым может быть только связный граф.


    Программа, строящая Эйлеров цикл, представленна ниже. (граф задается матрицей смежности, причем 0ставим если ребра нет, и один если есть).

    Код

    Uses CRT;

    var
    N :integer;
    M: array [1..20, 1..20] of boolean ;

    Type
    list = ^node;
    node = record
    i: integer;
    next: list;
    end;
    Var
    stack1, stack2: list;
    v, u, x, i, j: integer;
    count: array [1..20] of byte;
    procedure readfile;
    var
    filename:string;
    f:text; i,j:integer;
    b:byte;
    begin
    writeln('Введите имя файла:');
    readln( filename );
    assign(f, filename);
    reset(F);
    readln(f , n );
    for i:=1 to n do for j:=1 to n do begin
    read( f , B );
    if b=1 then m[i,j]:=true else m[i,j]:=false;
    end;
    close(F);
    end;

    Procedure Push(x: integer; var stack: list);
    Var
    temp: list;
    Begin
    New(temp);
    temp^.i:=x;
    temp^.next:=stack;
    stack:=temp;
    End;
    Procedure Pop(var x: integer; var stack: list);
    Begin
    x:=stack^.i;
    stack:=stack^.next
    End;
    Function Peek(stack: list): integer;
    Begin
    Peek:=stack^.i
    End;
    Procedure PrintList(l: list);
    Begin
    If l=nil then
    begin
    writeln('Ошибка!');
    exit;
    end;
    write('Эйлеров цикл: ');
    While l<>nil do
    Begin
    Write(l^.i,'-');
    l:=l^.next;
    End;
    End;
    Begin
    readfile;
    for i:=1 to N do
    begin
    count[i]:=0;
    for j:=1 to N do if m[i,j] = True then inc(count[i]);
    if (count[i] mod 2)<>0 then
    begin
    writeln('Нет цикла');
    readkey;
    halt;
    end;
    end;
    stack1:=nil;
    stack2:=nil;
    Write('Начальная вершина: '); readln(v);
    if (v<=N) then Push(v, stack1);
    While stack1<>NIL do
    Begin
    v:=peek(stack1);
    i:=1;
    While (i<=n) and not m[v,i] do inc(i);
    If i<=n then
    Begin
    u:=i;
    Push(u, stack1);
    m[v,u]:=False;
    m[u,v]:=False;
    End
    else
    Begin
    pop(x,stack1);
    push(x,stack2)
    End;
    End;
    PrintList(stack2);
    readkey;
    End.


    Материал взят с сайта Всё о Паскале

    Комментарии: (0) | Pascal & Delphi | 2006-06-02

    Комбинаторика


    Материал подготовил(и): Altair

    CODE
    Function Accomodations(N,K:Longint):Longint;
    var i,Result:longint;
    begin
    Result:=1;
    For i:=n downto (n-k+1) do result:=result*i;
    Accomodations:=result
    end;

    Function Transpositions(N:longint):Longint;
    begin
    Transpositions:=Accomodations(N,N)
    end;

    Function Combination(N,K:Longint):Longint;
    var numerator,denominator,i:longint;
    begin
    numerator:=1; denominator:=1;
    for i:=N downto (N-K+1) do numerator:=numerator*i;
    for i:=1 to K do denominator:=denominator*i;
    Combination:=numerator div denominator
    end;

    procedure BinomialTheorum(N:longint);
    var K,T,SA,SB:Longint;
    begin
    writeln;
    for K:=0 to n do
    begin
    SA:=n-k; SB:=k;
    T:=Combination(N,K);
    If T>1 then write(T);
    If SA=1 then write('A');
    If SA>1 then write('A^',SA);
    If SB=1 then write('B');
    If SB>1 then write('B^',SB);
    If k<>n then write(' + ');
    end;
    writeln
    end;

    begin
    BinomialTheorum(3);
    writeln(Combination(14,7));
    writeln(Accomodations(14,5));
    writeln(Transpositions(3));
    end.

    Function Accomodations(N,K:Longint):Longint;
    Вычисление размещений из N по К.
    (число размещений из N по K есть число к элементных упорядоченных подмножеств множества, содержащего N элементов.)
    Function Transpositions(N:longint):Longint;
    Вычисление числа перестановок. (A из n по n)
    Function Combination(N,K:Longint):Longint;
    Вычисление сочетаний из N по K. (k элементные подмножества множетсва содержащего N элементов.)
    procedure BinomialTheorum(N:longint);
    Выводит на экран разложение (a+b)^n.по формуле Ньютона.
    Входной паарметр - N.

    Материал подготовил(и): volvo

    При решении задач на практике часто приходится выбирать из некоторого множества объектов какие-либо подмножества, обладающие заданными свойствами, размещать элементы в определенном порядке и т.д. Такие задачи называются комбинаторными. Классическими задачами комбинаторики являются задачи о перестановках, выборках, сочетаниях.

    Перестановки
    Перестановки описывают, сколькими способами можно расставить N различных предметов на N различных позиций.

    Число перестановок принято обозначать Pn. N различных элементов можно расставить на N различных мест N! способами. Следовательно, Pn = N! = 1*2*… *(N-1)*N.

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

    Рассмотрим задачу генерации всех перестановок N-элементного множества в лексикографическом порядке. В качестве примера рассмотрим перестановку для N=3

                
                1 2 3
    1 3 2
    2 1 3
    2 3 1
    3 1 2
    3 2 1

    Алгоритм генерации следующей перестановки таков: начиная с конца перестановки находим такой элемент a[i]: a[i-1]
    CODE
    { программа генерации перестановок N элементного
    множества в лексикографическом порядке }

    Program perms;
    var
    i, j, h, n, k: integer;
    a:array[0 .. 100] of integer; { массив для хранения перестановки }

    {процедура вывода полученной перестановки}
    procedure output;
    var i: integer;
    begin
    writeln;
    for i:=1 to n do write(a[i],' ');
    end;

    begin
    write('количество элементов перестановки: '); readln(n);
    fillchar(a, sizeof(a), 0);

    { ввод элементов начальной перестановки }
    for i:=1 to n do a[i]:=i;

    repeat
    output; { вывод текущей перестановки }
    i:=n;
    while a[i-1]>a[i] do dec(i); { поиск скачка }
    j:=i-1;
    h:=a[j];
    while a[i+1]>h do inc(i); { поиск первого меньшего элемента }
    a[j]:=a[i]; a[i]:=h;
    i:=j+1; k:=n;
    while i h:=a[i]; a[i]:=a[k]; a[k]:=h;
    inc(i); dec(k)
    end
    until j=0;
    end.

    Для получения всех n! перестановок необходимо, чтобы начальная перестановка образовывала возрастающую последовательность (то есть была первой в лексикографическом порядке). Следует прокомментировать следующие два момента: почему условием окончания работы программы является выполнение равенства j=0 и почему для упорядочивания хвоста перестановки используется простой цикл без всяких сравнений.

    1. Следуя логике алгоритма, последняя перестановка представляет собой убывающую последовательность. Следовательно, позиция скачка будет равна 1 и соответственно j=0. Ни в каком другом случае равенство j=0 не выполняется, так как тогда перестановка не будет убывающей последовательностью, то есть не является последней.

    2. Об упорядочивании хвоста следует сказать только одно: хвост всегда представляет убывающую последовательность, поэтому требуется его только инвертировать.


    Сочетания
    Задачи о сочетаниях решают вопрос о том, сколькими способами можно выбрать M элементов из заданного N элементного множества и генерации всех возможных выборок. Число выборок вычисляется следующей формулой С=n!/(m!(n - m)!).

    Рассмотрим задачу о генерации сочетаний в лексикографическом порядке.
    Для примера рассмотрим начальные данные N=6 и M=4. Тогда число сочетаний равно 15. Начальное сочетание образует последовательность 1, 2, .. m, а последнее n-m+1, … , n.

                
                1234 1256 2345
    1235 1345 2346
    1236 1346 2356
    1245 1356 2456
    1246 1456 3456

    Переход к следующему сочетанию осуществляется по следующему правилу: требуется просмотреть текущее сочетание с конца и найти элемент, который можно увеличить. То есть такой элемент что a[i] <> n-k+i. Далее увеличиваем этот элемент на 1, а оставшуюся часть сочетания заполняем числами натурального ряда большими измененного элемента в порядке их следования.

    CODE
    program sochets;
    var
    i, j, n, m: integer;
    a: array[0 .. 100] of integer;

    { процедура вывода текущего сочетания }
    procedure use;
    var i: integer;
    begin
    writeln;
    for i:=1 to m do write(a[i]:3)
    end;

    begin
    write('ввод N и M: '); read(n, m);

    { формирование первого сочетания }
    for i:=0 to m do a[i]:=i;

    repeat
    use;
    i:=m;
    while a[i]=n-m+i do dec(i); { поиск элемента для изменения }
    inc(a[i]);
    for j:=i+1 to m do a[j]:=a[j-1]+1; { изменение правой части сочетания }
    until i=0;
    end.

    Рекурсивный алгоритм генерации сочетаний (с повторениями):
    const
    n = 3;
    k = 2;

    Код
    procedure s_pov(s: string);
    var i: integer;
    begin
    if length(s) = n then begin
    for i := 1 to length(s) do
    write(s[i] + ' ');
    writeln;
    end
    else
    for i := k downto 1 do
    s_pov(s+chr(ord('0') + i));
    end;

    begin
    s_pov('');
    end.


    Подмножества
    Для генерации всех подмножеств N-элементного множества: введем массив b[1..n] такой, что если b[i]=1 то i-й элемент входит в подмножество и если b[i]=0, то иначе. Тогда пустому подмножеству будет соответствовать набор из 0, а n-элементному подмножеству набор из 1. Поэтому здесь явно заметна связь с двоичным представление чисел в интервале 0 … 2N–1.

    Будем находить двоичное представление числа и формировать характеристические вектора подмножеств. Изначально положим b[i]=0 для всех I, что соответствует пустому подмножеству. Введем массив a[1..n] соответствующий двоичному представлению числа. Будем моделировать операцию сложения этого числа с 1. Для этого просмотрим число справа налево, заменяя единичные биты на нулевые до тех пор, пока не найдем нулевой бит, который заменим на 1.

    CODE
    program subsets;
    var
    i, n: integer;
    a, b: array[0..100] of integer;

    procedure output;
    var i : integer;
    begin
    { вывод двоичного числа }
    for i:=1 to n do write(' ',a[i]);
    write(' ');

    { вывод характеристического вектора подмножества }
    for i:=1 to n do write(' ',b[i]);
    write(' ');

    { вывод подмножества }
    for i:=1 to n do
    if(b[i]=1) then write(' ',i);
    end;

    begin
    readln(n);
    fillchar(a,sizeof(a),0);
    fillchar(b,sizeof(b),0);
    repeat
    output;
    i:=n;
    while a[i]=1 do begin
    a[i]:=0; dec(i); { перенос в следующий разряд }
    end;
    a[i]:=1;
    b[i]:=1-b[i] { b[i] = (1+b[i]) mod 2 }
    until i=0;
    end.

    Материал взят с сайта Всё о Паскале

    Комментарии: (0) | Pascal & Delphi | 2006-06-01

    Множества


    Материал подготовил(и): volvo

    Множества

    В математике под множеством понимается некоторый неупорядоченный набор элементов. Например, множество целых чисел или множество букв латинского алфавита. К множествам применимы следующие операции:
    • объединение множеств: A U B;
    • пересечение множеств: A П B;
    • разность (дополнение) двух множеств: A \ B.
    Например:
    {1, 2} U {3, 2, 4} = {1, 2, 3, 4}
    {1, 2} П {3, 2, 4} = {2}
    {1, 2} \ {3, 2, 4} = {1}

    Понятие множествав языке Паскаль основывается на математическом представлении о конечных множествах: это ограниченная совокупность различных элементов. Для построения конкретного множественного типа используется перечисляемый или интервальный тип данных. Тип элементов, составляющих множество, называется базовым типом.

    Множественный тип описывается с помощью служебных слов Set Of, например:
    CODE

    Type SetType = Set Of BaseType;

    где SetType - множественный тип, ВaseType - базовый тип.

    Пример описания переменной множественного типа:
    CODE

    Type SetType = Set Of 'A'..'D';
    Var
     mySet: SetType;


    Принадлежность переменных к множественному типу может быть определена прямо в разделе описания переменных:
    CODE

    Var otherSet: Set Of 0..7;


    Константы множественного типа записываются в виде заключенной в квадратные скобки последовательности элементов или интервалов базового типа, разделенных запятыми, например:
    ['A', 'C'] [0, 2, 7] [3, 7, 11..14]

    Константа вида [ ] означает пустое подмножество.

    Количество базовых элементов не должно превышать 256.

    Инициализация величин множественного типа может производиться с помощью типизированных констант:
    CODE

    Const seLit: Set Of 'A'..'D' = [];

    Порядок перечисления элементов базового типа в константах безразличен.

    Множество включает в себя набор элементов базового типа, все подмножества данного множества, а также пустое подмножество. Так, переменная Т множественного типа
    CODE
    Var T: Set Of 1..3;

    может принимать восемь различных значений:
    [ ] [1] [2] [3] [1,2] [1,3] [2,3] [1,2,3]

    К переменным и константам множественного типа применимы операции присваивания(:=), объединения(+), пересечения(*) и вычитания(-). Результат выполнения этих операций есть величина множественного типа.

    Примеры операций над множествами
    Пусть заданы 3 множества с одинаковым базовым типом: A, B и C...
    • 1. Объединение множеств (C := A + B).
      Результат - множество, которое состоит из элементов, принадлежащих хотя бы одному из множеств.
      A = ['A', 'B'] и B = ['A', 'D']
      C = ['A', 'B', 'D']
    • 2. Пересечение множеств (C := A * B)
      Результат - множество, состоящее из элементов, принадлежащих каждому из множеств
      A = ['A','D'] и B = ['A','B','C']
      C = ['A']
    • 3. Разность множеств (C := A - B)
      Результат - множество, состоящее из тех элементов первого множества, которые не принадлежат второму
      A = ['A','B','C'] и B = ['A','B']
      C = ['C']
    К множественным величинам применимы операции:
    • тождественность (=): проверка на эквивалентность двух множеств
      ['A','B'] = ['A','C'] вернет False
    • нетождественность (<>): проверка на неэквивалентность двух множеств
      ['A','B'] <> ['A','C'] вернет True
    • содержится в (<=): проверка того, является ли левое множество подмножеством правого
      ['B'] <= ['B','C'] вернет True
    • содержит (=>): проверка того, является ли правое множество подмножеством левого
      ['C','D'] >= ['A'] вернет False
    • In: проверка принадлежности элемента базового типа, стоящего слева от знака операции, множеству, стоящему справа от знака операции. Результат выполнения этой операции - булевский.
      Операция проверки принадлежности элемента множеству часто используется вместо операций отношения, например:
      'A' In ['A', 'B'] вернет True,
      2 In [1, 3, 6] вернет False.
    В качестве примера работы с множествами можно рассмотреть моделирование “лототрона (5 из 36)” т.е. случайную выборку 5 шаров из контейнера, содержащего 36 шаров, пронумерованных от единицы до 36. Множество шаров в этом случае удобно представить описаниями вида:
    CODE

    Type
     Number = 1 .. 36;
     Container = Set Of Number;
    Var
     Selection: Container;
     Ball: Number;


    Решение задачи сводится к генерации случайного числа (номера шара) в интервале от 1 до 36 с проверкой условия принадлежности очередного шара множеству ранее выбранных, причем на первом шаге это множество пустое. Выбору шара соответствует вывод его номера на экран. Для генерации случайных чисел используется стандартная функция Random(n).
    CODE

    Uses Crt;
    Const
     n = 36; { общее количество шаров }
     m = 5; { количество шаров в выборке }
    Type
     Number = 1 .. 36;
     Container = Set Of Number;
    Var
     Selection: Container;
     i, Ball : Number;
    Begin
     ClrScr;
     Selection := [];
     Randomize;

     For i := 1 To m Do
       Begin
         Repeat
           Ball := Random(36)+1;
         Until not (Ball in Selection);
         Selection := Selection + [Ball];
         Write(Ball: 3)
       End;
     ReadLn
    End.


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

    В качестве еще одного примера использования типа set рассмотрим задачу поиска простых чисел в диапазоне 2, ... , 255.

    Из-за простоты решения (не используются операции умножения и деления) в основу поиска положен метод, известный под названием ”решето Эратосфена”. Тогда алгоритм поиска простых чисел сводится к следующему.
    • Поместить все числа заданного диапазона в решето (Sieve).
    • Изъять из решета наименьшее среди оставшихся в нем чисел и поместить его среди простых (Primes).
    • Удалить из решета все числа, кратные данному.
    • Если решето не пустое, то вернуться к пункту 2, иначе вычисления прекратить.
    Решето и множество простых чисел можно описать как:
    CODE

    Var Sieve, Primes : Set Of 2 .. 255;


    и, учитывая, что простые числа (кроме двойки) есть нечетные числа, представить фрагмент программы их поиска в виде:
    CODE

    Uses Crt;
    Const n = 255;
    Type
     number = 2 .. n;
    Var
     Sieve, Primes : Set Of number;
     i, n1, next: Word;
    Begin
     ClrScr;
     Sieve := [2 .. n];
     Primes := [ ];
     next := 2;

     While Sieve <> [] Do
       Begin
         n1 := next;
         While n1 <= n Do
           Begin
             Sieve := Sieve - [n1];
             Inc(n1, next)
           End;
         Primes := Primes + [next];

         Repeat
           Inc(next)
         Until (next in Sieve) or (next > n)

       End;

     For i := 2 To 255 Do
       If i In Primes Then Write(i:5);
     ReadLn;
    End.

    Материал взят с сайта Всё о Паскале

    Комментарии: (0) | Pascal & Delphi | 2006-06-01

    Раздел программирование

    Создан новый раздел в статьях по программированию, начал потихоньку его забивать полезной информацией, надеюсь нашим студентам будет приятно! Пока добавляю в раздел о Паскале материалы
    с сайта Всё о Паскале с разрешения его администратора Altair'a.

    Комментарии: (0) | Новости сайта | 2006-06-01


    Страница 13 из 51Первая«10111213141516 »Последняя