Хакер

Пешо-хакера обича да хаква отдалечени компютри през telnet. През ръцете му са минали какви ли не сървъри и операционни системи. Веднъж Пешо успял в обикновена чат-сесия под съвсем тъп предлог да получи паролата на наивен потребител на отдалечена мрежа. Въпросната мрежа била много странна. Работела под операционна система, силно напомняща ДОС. Имената на файловете се състояли само от главни латински букви и цифри и имали дължина до 20 символа. Освен това Пешо открил, че имала много странни права на достъп, позволяващи изпълнение на не повече от 100 команди от промпта на сесия. Така поне било за потребителя, от чието име се включвал. Пешо разгледал внимателно мрежата и скоро открил, че тя е пълно дърво и че процесорът често се претоварва, поради което всички, с изключение на администратора имали право на ограничен брой команди. Пешо-хакера много се подразнил от това. Проучил още малко мрежата и скоро установил кои са жизненоважните й файлове, след което естествено му се поискало да ги търне, та да отърве света от дървото…

Имало обаче проблем. Пешо ценял труда на обикновените потребители и никога не повреждал файловете им, като си позволявал да скапва само системните файлове. За съжаление въпросната система била голямо дърво и не поддържала дървовидна структура и директориите. Всичките файлове (не били много — няколко хиляди) се намирали в една и съща директория. Пешо разбрал, че командата за изтриване е DEL и че операционната система поддържа стандартните символи ? и *. Първият замествал произволен символ (буква или цифра), а вторият — последователност от 0,1, или повече символа. Символът * можел да се поставя само в края на маската. Пешо бил мързелив човек пък, мързяло го да пише много, бил ограничен от операционната система по отношение на броя разрешени команди на сесия, пък и си падал маниак. Решил да покаже колко е умен на администратора и да изтрие файловете с минимален брой команди DEL.

За целта изготвил два отделни списъка. В първия записал имената на всички файлове по едно на ред и го запазил под името FILES.TXT. Във втория записал номерата на тези файлове от FILES.TXT, които трябва да бъдат изтрити, като ги разделил с поне един интервал или знак за нов ред. След това седнал да пише проста програмка, която да му подготви нужния скрипт (последователност от команди DEL по една на ред) и да го запише във файла HACKER.OUT. Проблемът е, че макар и велик хакер, Пешо е малко скаран с алгоритмите. Помогнете му да си напише нужната програма!

ПРИМЕР:

FILES.TXT

PRESLAV

PRESLI

BRESLAV

BRESLA

PRESLATA

PROST

PARASIT

PARAVAN

PRASKAM

PASCAL

DELETE.TXT

1 3 4 5 6 9

HACKER.OUT

DEL PROST

DEL ?R?S?A*

Решение:

Задачата може да се разглежда като обобщение на задачата за минимизация на булева функция и по специално на задачата за намиране на минималната дизюнктивна нормална форма. Стандартен подход към решението на задачата е намиране на простите импликанти по алгоритъма на Куайн-МакКласки, след което се избира минимална част от тях, така че да покриват изцяло единиците на функцията. Последното на практика се свежда до решаване на задача за минимални покрития. [1]

Без да навлизаме в излишни подробности и ненужни математически формализми, по-долу ще се опитаме да скицираме идеята. Задачата за минимизиране на булева функция е разгледана подробно от Манев в [1]. Целта е получаване на запис на булевата функция, съдържащ минимален брой букви на променливи. Пак там е разгледан и частният случай на задачата за намиране на минималната дизюнктивна нормална форма. Алгоритъмът протича на две стъпки: на първата стъпка се търсят простите импликанти по алгоритъма на Куайн-МакКласки. Започва се от списък на всички дизюнкти на съвършената дизюнктивна форма. След това се търсят всички двойки измежду дизюнктите, които се отличават в точно една позиция (променлива): в единия дизюнкт променливата е с черта, а в другия — без. За всяка такава двойка дизюнкти се получава нов дизюнкт, в който въпросната променлива отпада. Той покрива единиците и на двата дизюнкта, от които се получава. Дизюнктите, които са се комбинирали успешно с поне един друг дизюнкт се отбелязват с *. На следващата стъпка се опитва аналогично комбинирано, но между дизюнктите, произлезли в резултат на комбинация на предходната стъпка. Процесът продължава до получаване на 0 или една импликанти. Всички неотбелязани с * дизюнкти са прости импликанти на функцията (т.е. премахването на коя да е буква от тях води до получаване на дизюнкт, който не принадлежи на ДНФ на функцията).

На втората стъпка на алгоритъма се избират част от неотбелязаните с * дизюнкти (те образуват така наречената Съкратена ДНФ), така че да покриват изцяло функцията и същевременно броят на буквите в тях да бъде минимален. За целта се решава задачата за минималните покрития, в резултат на което се намират всички неприводими ДНФ на функцията. Измежду тях се избират тези, които съдържат минимален брой букви на променливи.

Как стоят нещата в нашия случай и как горните алгоритми могат да се използват за решаване на нашата задача? Оказва се, че идеята на алгоритъма на Куайн-Макласки се пренася почти директно. На първата стъпка се инициализират няколко списъка:

    1. списък на файловете за изтриване: D;

    2. списък на останалите файлове: R;

    3. празен списък C на комбинациите между елементи на D, невлизащи в конфликт с тези от R;

    4. празен списък F на “простите импликанти”.

На всяка стъпка на алгоритъма се комбинират (в нов списък C) всички възможни двойки имена на файлове от D, за които получената в резултат на комбинацията маска (букви и специални знаци) не покрива нито един файл от R. Елементите, които не са се комбинирали с никой друг, следва да се считат за “прости импликанти” и попадат в крайния списък F. Останалите се покриват от маските от C. На следващата стъпка D се инициализира с елементите на C, C се инициализира с празния списък и се прави опит за комбиниране между маските от D. Процесът продължава докато при поредната стъпка в C попада поне един елемент. В този момент F ще съдържа всички “прости импликанти” на изходното множество от файлове за изтриване.

Как става комбинирането на двойка файлове в обща маска? Алгоритъмът е прост: Двата низа се сканират последователно и едновременно. Ако съответните символи съвпадат, то маската ще съдържа същия символ. В противен случай ще съдържа ? на съответната позиция. Ако единият от символите завършва на *, то и унифицираният низ ще завършва на *. Ако единият низ е по-дълъг от другия, то маската ще съдържа * в края си. Остава да се провери дали получената маска m не се унифицира с някой от файловете, които не бива да се изтриват, в който случай следва да се отхвърли. Проверката за конкретен файл f става като се унифицира f с m. Ако в резултат се получи отново m, то f се покрива от m и следователно m трябва да се отхвърли.

Така получаваме списък от “прости импликанти”. Остава да изхвърлим някои от тях, така че останалите да бъдат минимален брой и да покриват цялото множество от изтривани файлове. Тази задача е трудно решима, т.е. няма полиномиално решение. Съществува лакомо решение, при което човек на всяка стъпка се опитва да прибави тази маска, която покрива максимален брой непокрити файлове. [2]

В приложената програма задачата се решава по метода на търсенето с връщане назад. На всяка стъпка се прави опит за добавяне на следващата маска, но само ако трие поне един неизтрит до момента файл за изтриване. След включването на новата маска се прави проверка дали някоя от маските, включени на предходните стъпки, няма да се окаже излишна. Задачата може да се реши и с поток.

Алгоритъмът може да се ускори, в някои случаи значително, ако предварително се отстранят ядровите маски (виж [1]), т.е. тези, които единствени трият някой от файловете за изтриване.

Следва резултат от изпълнението на програмата върху примерен вход.

Файлове:

PRESLAV

PRESLI

BRESLAV

BRESLA

PRESLATA

PROST

PARASIT

PARAVAN

PRASKAM

PASCAL

BORLANDC

BARBADOS

BANICA

PANICA

PERKA

PERKO

PERALNJA

KANDILO

KARAMBOL

KASKADA

KARAMFIL

KROKODIL

KILIM

FROST

LOST

DELETE

PELETI

PELENI

Трием:

1 3 4 5 6 9 10 11 12 15 16 17 19 20 25 27 28

Резултат:

Step 1:

PRESLAV + BRESLAV = ?RESLAV

PRESLAV + BRESLA = ?RESLA*

PRESLAV + PRESLATA = PRESLA?*

PRESLAV + PRASKAM = PR?S?A?

PRESLAV + PERALNJA = P???L??*

BRESLAV + BRESLA = BRESLA*

BRESLAV + PRESLATA = ?RESLA?*

BRESLAV + PRASKAM = ?R?S?A?

BRESLAV + BORLANDC = B??????*

BRESLAV + PERALNJA = ????L??*

BRESLA + PRASKAM = ?R?S?A*

PRESLATA + PRASKAM = PR?S?A?*

PRESLATA + PERALNJA = P???L??A

PROST + PERKA = P????

PROST + PELETI = P???T*

PASCAL + BORLANDC = ????A?*

PASCAL + BARBADOS = ?A??A?*

PASCAL + PERKA = P???A*

PASCAL + KASKADA = ?AS?A?*

PASCAL + LOST = ??S?*

BORLANDC + BARBADOS = B?R?A???

BORLANDC + PERKA = ??R?A*

BORLANDC + PERALNJA = ??R??N??

BORLANDC + KASKADA = ????A??*

BORLANDC + LOST = ?O??*

BARBADOS + KARAMBOL = ?AR???O?

BARBADOS + KASKADA = ?A??AD?*

PERKA + PERKO = PERK?

PERKA + PERALNJA = PER??*

PERKA + KASKADA = ???KA*

PERKA + PELETI = PE???*

PERALNJA + PELETI = PE????*

PELETI + PELENI = PELE?I

Step 2:

?RESLAV + ?RESLA* = ?RESLA*

?RESLAV + PRESLA?* = ?RESLA?*

?RESLAV + PR?S?A? = ?R?S?A?

?RESLAV + P???L??* = ????L??*

?RESLAV + ?R?S?A* = ?R?S?A*

?RESLAV + PR?S?A?* = ?R?S?A?*

PRESLA?* + PR?S?A? = PR?S?A?*

PRESLA?* + P???L??* = P???L??*

B??????* + B?R?A??? = B??????*

P???? + PERK? = P????

????A?* + ?A??A?* = ????A?*

????A?* + P???A* = ????A*

?A??A?* + ?AS?A?* = ?A??A?*

?AS?A?* + ??S?* = ??S?*

B?R?A??? + ??R?A* = ??R?A*

B?R?A??? + ????A??* = ????A??*

PERK? + PER??* = PER??*

PERK? + PE???* = PE???*

PE????* + PELE?I = PE????*

Step 3:

?RESLA* + ?RESLA?* = ?RESLA*

?RESLA* + ?R?S?A? = ?R?S?A*

?RESLA?* + ?R?S?A? = ?R?S?A?*

?RESLA?* + ????L??* = ????L??*

????A?* + ????A* = ????A*

????A?* + ?A??A?* = ????A?*

PER??* + PE???* = PE???*

Step 4:

?RESLA* + ?R?S?A* = ?R?S?A*

????A* + ????A?* = ????A*

Step 5:

File list to minimize now...:

DEL P???T*

DEL ??R??N??

DEL ?O??*

DEL ?AR???O?

DEL B??????*

DEL P????

DEL ??S?*

DEL ????L??*

DEL PE???*

DEL ?R?S?A*

DEL ????A*

You must perform the following delete operations:

DEL P???T*

DEL ??R??N??

DEL ?AR???O?

DEL ??S?*

DEL PE???*

DEL ?R?S?A*

DEL ????A*

Предложената програма на C++ очаква като вход два файла: един, съдържащ имената на файловете, и втори — съдържащ индексите на файловете за изтриване. Резултатът се извежда на екрана, като се извеждат и междинните резултати от всяка стъпка на алгоритъма на Куайн-МакКласки.

Литература:

  1. Манев Кр., “Увод в дискретната математика”, Нов български университет, София, 1996.

  2. Skiena S., “The algorithm design manual”, Springer-Verlag, New York, 1998.

#define MAX 1000

#define MAX_FNAME_LEN 100

#define INPUT_FILE "files.txt"

#define DELETE_FILE "delete.txt"

// Boolean constants

#define TRUE 1

#define FALSE 0

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

struct {

char *fname;

int toDel;

} files[MAX]; // List of file names to do NOT delete

unsigned int fcnt; // Count of file names to do NOT delete

struct {

char *fname;

int used;

} del[MAX]; // Strings to delete

unsigned int dcnt; // Strings to delete count

char *toDel[MAX]; // Strings to delete

unsigned int toDelCnt;

char *unif[MAX*MAX]; // Unified strings

unsigned int ucnt; // Unified strings count

char *final[MAX]; // Final strings

unsigned int finalCnt = 0; // Final strings count

 

void readInputFile() // Get the file names

{

FILE *fp;

char s[MAX_FNAME_LEN];

if ((fp = fopen(INPUT_FILE,"rt")) == NULL) {

fprintf(stderr,"\nError while trying to open %s for reading!",INPUT_FILE);

exit(-1);

}

fcnt = 0;

while (!feof(fp)) {

fscanf(fp,"%s",s);

files[fcnt].fname = strdup(s);

files[fcnt++].toDel = FALSE;

}

fclose(fp);

}

void readDeleteFile() // Get the file names

{

unsigned int i,ind;

FILE *fp;

if ((fp = fopen(DELETE_FILE,"rt")) == NULL) {

fprintf(stderr,"\nError while trying to open %s for reading!",DELETE_FILE);

exit(-1);

}

// Get the files to delete

for (dcnt = 0; !feof(fp); dcnt++) {

unsigned int ind;

fscanf(fp,"%u",&ind);

files[ind-1].toDel = TRUE;

del[dcnt].fname = strdup(files[ind-1].fname);

toDel[dcnt] = strdup(files[ind-1].fname);

del[dcnt].used = FALSE;

}

toDelCnt = dcnt;

// Remove them from the files list

for (i = ind = 0; i < fcnt; i++)

if (!files[i].toDel && i != ind)

files[ind++].fname = files[i].fname;

fcnt = ind;

fclose(fp);

}

char *unify(char *s1, char *s2, char *result) // Unify two strings

{

char *res = result;

if (s1 == NULL || s2 == NULL) return NULL;

while (*s1 && *s2) {

if (*s1 == '*' || *s2 == '*') *result++ = '*';

else *result++ = (*s1 == *s2) ? *s1 : '?';

*s1++; *s2++;

}

if (*s1 != *s2 && *(result-1) != '*') *result++ = '*';

*result = '\0';

return res;

}

void doUnify()

{

char s[MAX_FNAME_LEN], s2[MAX_FNAME_LEN];

unsigned int i,j,k;

int flag;

ucnt = 0;

for (i = 0; i < dcnt-1; i++)

for (j = i+1; j < dcnt; j++) {

unify(del[i].fname,del[j].fname,s); // Get the unified code

// Check if it matches a non-delete file name

for (k = 0, flag = FALSE; k < fcnt; k++)

if (strcmp(s,unify(files[k].fname,s,s2)) == 0)

{ flag = TRUE; break; }

if (!flag) {

del[i].used = del[j].used = TRUE;

// Check if it does exist already

for (k = 0, flag = FALSE; k < ucnt; k++)

if (strcmp(s,unif[k]) == 0) { flag = TRUE; break; }

}

if (!flag) {

unif[ucnt++] = strdup(s);

printf("%s + %s = %s\n",del[i].fname,del[j].fname,s);

}

}

}

void getFinals() // Get the finals

{

for (unsigned int i = 0; i < dcnt; i++)

if (!del[i].used)

final[finalCnt++] = strdup(del[i].fname);

}

void prepareNextStep() // Prepare the next iteration step

{

unsigned int i;

// Free the memory allocated by the old file names

for (i = 0; i < dcnt; i++) free(del[i].fname);

// Put in the new files

dcnt = ucnt;

for (i = 0; i < ucnt; i++) {

del[i].fname = unif[i];

del[i].used = FALSE;

}

}

void printResults() // Output the results

{

printf("\nFile list to minimize now...:\n");

for (unsigned int i = 0; i < finalCnt; i++)

printf("DEL %s\n",final[i]);

}

// ---------------------------------------------------------------------

// ---------------------------------------------------------------------

// ---------------------------------------------------------------------

unsigned int *puiCnt; // How much times is the element covered

unsigned char *pa; // The spanning matrix

unsigned char *curChoice, *bestChoice; // The family of sets chosen

unsigned int minSets = 100000; // Minimum sets used

unsigned int elemsCovered = 0; // Elements covered count

void buildSetCoverMatrix()

{

unsigned int i,j;

char s[1000];

puiCnt = new unsigned int [toDelCnt];

memset(puiCnt,0,toDelCnt*sizeof(unsigned int));

curChoice = new unsigned char [finalCnt];

memset(curChoice,0,finalCnt*sizeof(unsigned char));

bestChoice = new unsigned char [finalCnt];

pa = new unsigned char [toDelCnt*finalCnt];

for (i = 0; i < finalCnt; i++)

for (j = 0; j < toDelCnt; j++)

pa[i*toDelCnt+j] = !strcmp(final[i],unify(final[i],toDel[j],s));

}

void cover(unsigned ind)

{

unsigned int i,j;

unsigned char found;

if (ind == finalCnt) return;

found = FALSE;

for (j = 0; j < toDelCnt; j++)

if (!puiCnt[j] && pa[ind*toDelCnt+j]) { found = TRUE; break; }

// Try to include the set into the cover family

if (found) {

for (i = 0; i < ind && found; i++) {

// Check if the set is obsolete?

found = FALSE;

for (j = 0; j < toDelCnt; j++)

if (pa[i*toDelCnt+j] && !pa[ind*toDelCnt+j]) { found = TRUE; break; }

}

if (found) { // Try to include the set

for (j = 0; j < toDelCnt; j++)

if (pa[ind*toDelCnt+j]) {

if (!puiCnt[j]) elemsCovered++;

puiCnt[j]++;

}

curChoice[ind] = TRUE;

// Check if a solution has been found

if (elemsCovered == toDelCnt) {

unsigned int cnt = 0;

for (i = 0; i <= ind; i++) if (curChoice[i]) cnt++;

if (cnt < minSets) {

minSets = cnt;

for (i = 0; i <= ind; i++) bestChoice[i] = curChoice[i];

}

}

else cover(ind+1);

curChoice[ind] = FALSE;

for (j = 0; j < toDelCnt; j++)

if (pa[ind*toDelCnt+j]) {

puiCnt[j]--;

if (!puiCnt[j]) elemsCovered--;

}

}

}

// Try to skip the set

cover(ind+1);

}

// ---------------------------------------------------------------------

// ---------------------------------------------------------------------

// ---------------------------------------------------------------------

void main() {

unsigned long step = 0;

readInputFile();

readDeleteFile();

do {

printf("Step %lu:\n",++step);

doUnify();

getFinals();

prepareNextStep();

} while (ucnt > 0);

printResults();

// Solve the minimum set cover

buildSetCoverMatrix();

cover(0);

printf("\nYou must perform the following delete operations:\n");

for (unsigned int i = 0; i < finalCnt; i++)

if (bestChoice[i])

printf("DEL %s\n",final[i]);

return;

}